Алгоритмы - построение и анализ (1021735), страница 28
Текст из файла (страница 28)
Пользуясь леммой 5.1, можно прийти к заключению, что 148 Часть 1. Основы Теперь можно приступить к вычислению величины Е [Х[: Е [Х] = Е ~~) Х, = (согласно (5.3)) 1=1 (5.5) (согласно (5.4)) (согласно (А.?)) (5.6) Даже если проведено интервью с п кандидатами, в среднем будет нанято только 1п п из них. Этот результат подьпожен в приведенной ниже лемме. Лемма 5.2. В случае собеседования с кандидатами в случайном порядке полная стоимость найма при использовании алгоритма Нщв АяшзтАмт равна О (сь 1п и). Доказательство. Эта оценка непосредственно следует из определения стоимости найма и уравнения (5.6).
П Порядок роста представленной стоимости найма значительно ниже порядка роста функции О (сап), характеризующей стоимость найма в наихудшем случае. Упражнения 5.2-1. Чему равна вероятность того, что в процедуре Н1кв АзязтАмт будет нанят ровно один кандидат, если предполагается, что собеседование с кандидатамн проводится в случайном порядке? 5.2-2.
Чему равна вероятность того, что в процедуре Нав АзязтАнт будет нанято ровно два кандидата, если предполагается, что собеседование с кандидатами проводится в случайном порядке? Чему равна вероятность того, что будет нанято ровно п кандидатов? 5.2-3. Вычислите математическое ожидание суммы очков на п игральных костях с помощью индикаторных случайных величин.
5.2-4. Решите с помощью индикаторных случайных величин задачу, известную как задача о гардеробщике. Каждый из п посетителей ресторана сдает свою шляпу в гардероб. Гардеробщик возвращает шляпы случайным образом. Чему равно математическое ожидание количества посетителей, получивших обратно свои собственные шляпы? и Е[Х,] = 1=1 =Е-,= = 1пп+ О(1) (согласно линейности математического ожидания) Глава 5.
Вероятностный анализ н рандомнзнрованные алгоритмы 149 5.2-5. Пусть А [1..п] — массив, состоящий из п различных чисел. Если г < 1 и А [г] > А [т], то пара (г, з) называется ипверсией массива А (более детальную информацию об инверсиях можно найти в задаче 2-4). Предположим, что элементы массива А образуют равномерную случайную перестановку чисел (1,2,...,гт). Воспользуйтесь индикаторными случайными величинами для поиска математического ожидания количества инверсий в массиве. 5.3 Рандомизированные алгоритмы В предыдущем разделе было показано, как знание информации о распределении входных данных может помочь проанализировать поведение алгоритма в среднем случае. Однако часто встречаются ситуации, когда такими знаниями мы не располагаем, и анализ среднего поведения невозможен.
Но, как упоминалось в разделе 5.1, иногда есть возможность использовать рандомизированные алгоритмы. В задачах наподобие задачи о найме сотрудника, в которой важную роль играет предположение о равновероятности всех перестановок входных данных, вероятностный анализ приводит к разработке рандомизированного алгоритма. Вместо того чтобы предполагать то или иное распределение входных данных, мы попросту навязываем его. В частности, перед запуском алгоритма мы производим случайную перестановку кандидатов, чтобы добиться выполнения условий равновероятности всех перестановок.
Такая модификация алгоритма не влияет на величину математического ожидания найма сотрудника, примерно равную 1пп. Это означает, что такое поведение алгоритма присуще любому множеству входных данных, независимо от его конкретного распределения. Давайте рассмотрим отличия вероятностного анализа от рандомизированных алгоритмов.
В разделе 5.2 мы выяснили, что если кандидаты приходят на собеседование в случайном порядке, то математическое ожидание количества наймов новых менеджеров приблизительно равно 1п и. Обратите внимание на то, что представленный алгоритм является детерминированным, т.е. для любых конкретных входных данных количество наймов новых менеджеров всегда будет одним и тем же. Кроме того, эта величина различна для разных входных данных и зависит от распределения рангов кандидатов. Поскольку количество наймов зависит только от рангов кандидатов, каждый отдельно взятый набор входных данных можно представить в виде перечисления рангов кандидатов в порядке нумерации последних, т.е. в виде последовательности (гапИ (1), тапИ (2),..., тапИ (и)).
В случае списка рангов А1 = (1,2,3,4,5,б,7,8,9,10) новый менеджер будет всегда наниматься 10 раз, поскольку каждый очередной кандидат лучше предыдущего, и строки 5 — 6 будут выполняться при каждой итерации алгоритма. Если же список 150 Часть 1.
Основы рангов имеет вид Аз = (10,9,8,7,6,5,4,3,2,1), то новый менеджер будет нанят только один раз, во время первой итерации. Список Аз = (5, 2, 1,8, 4, 7, 10,9, 3,6) дает три найма, после интервью с кандидатами, имеющими ранг 5, 8 и 10. Напомним, что стоимость алгоритма зависит от того, сколько раз происходит найм нового сотрудника. Легко убедиться в том, что есть дорогостоящие входные данные (такие как А!), дешевые входные данные (такие как Аз), и входные данные средней стоимости, такие как Аз. Рассмотрим теперь ранломизированный алгоритм, в котором сначала выполняется перестановка кандидатов на должность и только после этого определяется, кто из них самый лучший.
В этом случае рандомизация представляет собой часть алгоритма, а не входных данных. При этом для отдельно взятого набора входных данных, например, для представленного выше массива Аз, нельзя заранее сказать, сколько наймов будет выполнено, поскольку эта величина изменяется при каждом запуске алгоритма. При первом запуске алгоритма с входными данными Аз в результате перестановки могут получиться входные данные А!, и найм произойдет 10 раз, а при втором запуске перестановка может дать входные данные Аз, и найм будет только один. Запустив алгоритм третий раз, можно получить еще какое- нибудь количество наймов.
При каждом запуске алгоритма стоимость его работы зависит от случайного выбора и, скорее всего, будет отличаться от стоимости предыдущего запуска. В этом н во многих других рандомизированных алгоритмах никакие входные данные не могут вызвать наихудшее поведение алгоритма. Даже ваш злейший враг не сможет подобрать плохой входной массив, поскольку дальнейшая случайная перестановка приводит к тому, что порядок входных элементов становится несущественным.
Рандомизированные алгоритмы плохо ведут себя лишь тогда, когда генератор случайных чисел выдаст "неудачную" перестановку. Единственное изменение, которое нужно внести в алгоритм найма сотрудника для рандомизации, — это добавить код случайной перестановки. кА!ч!70м!Ее!з Н!Ке Азз!БтАхт(п) 1 Случайная перестановка списка кандидатов. 2 ВеМ +- 0 с Кандидат 0 — наименее квалифицированный [> фиктивный кандидат 3 Гогз' — 1 гоп 4 йо собеседование с кандидатом г' 5 11' кандидат !' лучше кандидата Веет 6 Феп ВевФ вЂ” ! 7 Нанимаем кандидата ! С помощью этого простого изменения создается рандомизированный алгоритм, производительность которого такая же, как и в случае предположения о том, что собеседование с кандидатами производится в случайном порядке. Глава 5.
-Вероятностный анализ н рандомнзнрованные алгоритмы 151 Лемма 5.3. Математическое ожидание стоимости процедуры КЛЬЛЭОМ1ХЕП НГКЕ Азз1зтлнт равно О (сь !п и). Доказаигельсянво. После перестановки элементов входного массива возникает ситуация, идентичная рассмотренной при вероятностном анализе алгоритма Нике Азз!зтлхт. 6 При сравнении леммы 5.2 и леммы 5.3 проявляется различие между вероятностным анализом и рандомизированными алгоритмами. В лемме 5.2 делается предположение о виде входных данных. В лемме 5.3 такие предположения отсутствуют, хотя для рандомизацин входных величин требуется дополнительное время. В оставшейся части настоящего раздела обсуждаются некоторые вопросы, связанные с входными данными, которые подверглись случайной перестановке.
Массивы, полученные в результате случайной перестановки Во многих алгоритмах входные данные рандомизируются путем перестановки элементов исходного входного массива (впрочем, существуют и другие способы рандомизации). Мы рассмотрим два метода, позволяющие выполнить эту операцию. Будем считать, что у нас имеется массив А, который содержит элементы от 1 до п.
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
