Т. Кормен, Ч. Лейсерзон, Р. Риверст, К. Штайн - Алгоритмы. Построение и анализ (2013) (1162189), страница 31
Текст из файла (страница 31)
Любой из первых л кандидатов с равной вероятностью может оказаться лучшим. Поэтому вероятность того, что квалификация претендента с номером 1 выше квалификации претендентов с номерами от 1 до 1 — 1 и что он будет взят на работу, равна 1/1. Пользуясь леммой 5.1, можно заключить, что Е[Х,] = 1/1. (5.3) Теперь можно вычислить Е [Х]: Е[Х] = Е ~~ Х, (согласно (5.2)) (5.4) (согласно (5.3)) (согласно (АЛ)) . (5.5) Даже если проведено интервью с и кандидатами, в среднем будет нанято только 1п и из них.
Этот результат подытожен в приведенной ниже лемме. Лемма 5.2 В случае собеседования с кандидатами в случайном порядке полная стоимость найма при использовании алгоритма Н1кн-Азз1зтл1чт равна 0(сь 1п и). Доказательство. Эта граница следует непосредственно из нашего определения стоимости найма и уравнения (5.5), которое показывает, что математическое ожидание количества наймов приближенно равно 1п и. Стоимость найма в среднем случае существенно лучше, чем в наихудшем случае, когда она равна 0(сап). Е [Х;] ив 1 1/( 1=1 1пп+ 0(1) (в силу линейности математического ожидания) часть я Осноею !4я Упражнения 5.2.1 Чему равна вероятность того, что в процедуре Нин-Азз1зтлнт будет нанят ровно один кандидат, если предполагается, что собеседование с кандидатами проводится в случайном порядке? А вероятность того, что будут наняты п кандидатов? 5.2.2 Чему равна вероятность того, что в процедуре Ншн-Азз1зтлнт будет нанято ровно два кандидата, если предполагается, что собеседование с кандидатами проводится в случайном порядке? Вычислите математическое ожидание суммы очков на и игральных костях с по- мощью индикаторных случайных величин.
Решите с помощью индикаторных случайных величин задачу, известную как задача о гардеробщике. Каждый из п посетителей ресторана сдает свою шляпу в гардероб. Гардеробщик возврашает шляпы случайным образом. Чему равно математическое ожидание количества посетителей, получивших обратно свои собственные шляпы? 5.3.5 Пусть А~1..
п~ — массив, состоящий из и различных чисел. Если з < 5, а АЯ > АЦ, то пара (1,5) называется янвелсией массива А (более детальную информацию об инверсиях можно найти в задаче 24). Предположим, что элементы массива А образуют равномерную случайную перестановку чисел (1, 2,..., и). Воспользуйтесь индикаторными случайными величинами для поиска математического ожидания количества инверсий в массиве. 5.3. Раидомизироваииые алгоритмы В предыдущем разделе было показано, как знание информации о распределении входных данных может помочь проанализировать поведение алгоритма в среднем случае.
Однако часто встречаются ситуации, когда такими знаниями мы не располагаем, и анализ среднего поведения невозможен. Но, как упоминалось в разделе 5.1, иногда есть возможность использовать рандомизированные алгоритмы. В задачах наподобие задачи о найме, в которой важную роль играет предположение о равновероятности всех перестановок входных данных, вероятностный анализ приводит к разработке рандомизнрованного алгоритма.
Вместо того чтобы предполагать то или иное распределение входных данных, мы попросту его навязываем. В частности, перед запуском алгоритма мы производим случайную Глава 5. Вералтлоетлый анализ и рендал|изороланные алгоритмы ы9 перестановку кандидатов, чтобы добиться выполнения условий равновероятности всех перестановок. Хотя при этом происходит модификация алгоритма, она не влияет на величину математического ожидания найма сотрудника, примерно равную !и и.
Но теперь мы можем ожидать это значение при любых входных данных независимо от их конкретного распределения. Давайте рассмотрим отличия вероятностного анализа от рандомизированных алгоритмов. В разделе 5.2 мы выяснили, что если кандидаты приходят на собеседование в случайном порядке, то математическое ожидание количества наймов новых менеджеров приблизительно равно 1п и. Обратите внимание на то, что представленный алгоритм является детерминированным, т.е.
для любых конкретных входных данных количество наймов новых менеджеров всегда будет одним и тем же. Кроме того, эта величина различна для разных входных данных и зависит от распределения рангов кандидатов. Поскольку количество наймов зависит только от рангов кандидатов, каждый отдельно взятый набор входных данных можно представить в виде перечисления рангов кандидатов в порядке нумерации последних, т.е.
в виде последовательности (гап!с(1), гоп|с(2),..., ганзе(п)). В случае списка рангов Аз = (1, 2, 3, 4, б, 6, 7, 8, 9, 10) новый менеджер будет всегда наниматься !О раз, поскольку каждый очередной кандидат лучше предыдущего, и строки 5 и б будут выполняться при каждой итерации алгоритма. Если же список рангов имеет вид Аз = (10, 9, 8, 7, 6, 5, 4, 3, 2, 1), то новый менеджер будет нанят только один раз, во время первой итерации.
Список Аз = (5, 2, 1, 8, 4, 7, 10, 9, 3, 6) дает три найма после интервью с кандидатами, имеющими ранг 5, 8 и 10. Напомним, что стоимость алгоритма зависит от того, сколько раз происходит наем нового сотрудника. Легко убедиться в том, что есть дорогостоящие входные данные (такие, как Аз), дешевые входные данные (такие, как Аз) и входные данные средней стоимости (такие, как Аз). С другой стороны, рассмотрим теперь рандомизированный алгоритм, в котором сначала выполняется перестановка кандидатов на должность и только после этого определяется, кто из них самый лучший. В этом случае рандомизация представляет собой часть алгоритма, а не входных данных. При этом для отдельно взятого набора входных данных, например для представленного выше массива Аз, нельзя заранее сказать, сколько наймов будет выполнено, поскольку эта величина изменяется при каждом запуске алгоритма.
При первом запуске алгоритма с входными данными Аз в результате перестановки могут получиться входные данные Аы и наем произойдет десять раз, а при втором запуске перестановка может дать входные данные Аз, и наем будет только один. Запустив алгоритм третий раз, можно получить еще какое-нибудь количество наймов. При каждом запуске алгоритма стоимость его работы зависит от случайного выбора и, скорее всего, будет отличаться от стоимости предыдущего запуска. В этом и во многих других рандомизированных алгоритмах никакие входные данные не лзогузн вызванзь наихудшее поведение алгоритма. Даже ваш злейший враг не сможет подобрать плохой входной массив, поскольку дальнейшая случайная перестановка приводит к тому, что порядок входных элементов становится несущественным.
Рандомизированные алгоритмы плохо ведут себя лишь тогда, когда генератор случайных чисел выдает "неудачную" перестановку. Часть Е Основы !50 Единственное изменение, которое нужно внести в алгоритм найма для рандомизации, — это добавить код случайной перестановки.
нАх 00 м12е0-Н1ке-А ее!зтАхт (и) 1 Случайная перестановка списка кандидатов 2 Ьев1=0 // Кандидат Π— фиктивный 3 Тог 1 = 1 то п // неквалифицированный кандидат 4 Беседа с кандидатом 1 5 !Т кандидат 1 лучше кандидата бев1 б бев1 = г 7 Нанять кандидата 1 С помощью этого простого изменения создается рандомизированный алгоритм, производительность которого такая же, как и в случае предположения о том, что собеседование с кандидатами производится в случайном порядке. Лемма 5.3 Математическое ожидание стоимости найма в процедуре КА1чпом12еп-Н1ке- Аее1етА1чт равно 0(сь 1п и). Докезатепьетво. После перестановки элементов входного массива возникает ситуация, идентичная рассмотренной при вероятностном анализе ашоритма Н!ке-Аез!зтАхт.
Сравнение лемм 5.2 и 5.3 выявляет различие между вероятностным анализом и рандомизированными алгоритмами. В лемме 5.2 делается предположение о виде входных данных. В лемме 5.3 такие предположения отсутствуют, хотя для рандомизации входных величин требуется дополнительное время. Для согласованности используемой терминологии в лемме 5.2 говорится о стоимости в среднем случае, а в лемме 5.3 — о математическом ожидании (ожидаемой) стоимости. В оставшейся части настоящего раздела обсуждаются некоторые вопросы, связанные с входными данными, которые подверглись случайной перестановке.
Массивы после случайной перестановки Во многих алгоритмах входные данные рандомизируются путем перестановки элементов исходного входного массива (существуют и другие способы рандомизации). Мы рассмотрим два метода, позволяющие выполнить эту операцию. Будем считать, что у нас имеется массив А, который содержит элементы от 1 до и. Наша цель — получить случайную перестановку массива. Один из распространенных методов заключается в том, чтобы присвоить каждому элементу АЯ массива случайный приоритет Р(г), а затем отсортировать элементы массива А в соответствии с их приоритетами.
Например, если исходный массив имеет вид А = (1, 2, 3, 4) и выбраны случайные приоритеты Р = (36, 3, 62, 19), то в результате будет получен массив В = (2, 4, 1, 3), поскольку приоритет второго элемента самый низкий, за ним по приоритету идет 15! Глава 5. Вероятностный анализ и ггандаиизированные алгорииииы четвертый элемент, после него — первый и наконец — третий. Назовем эту про- цедуру Рекм15те-Вт-ВОкт11нб.
Рекм15те-ВУ-БОкт!ЫО(А) 1 и = А.!ендй 2 Пусть Р[1 .. н] — новый массив 3 Тог ! = 1 го и 4 Р[1] = клнООм(1,пз) 5 Отсортировать А, используя Р в качестве ключей сортировки В строке 4 выбирается случайное число от 1 до пз. Такой интервал выбран для того, чтобы снизить вероятность наличия одинаковых приоритетов в массиве Р. (В упр. 5.3.5 требуется доказать, что вероятность отсутствия в массиве одинаковых приоритетов составляет по меньшей мере 1 — 1/н, а в упр. 5.3.6 — реализовать алгоритм, даже если несколько приоритетов могут иметь одинаковые значения.) Будем считать, что одинаковых приоритетов в массиве нет.
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
