Т. Кормен, Ч. Лейзерсон, Р. Ривест, К. Штайн - Алгоритмы - Построение и анализ (2 изд.) (1123758), страница 29
Текст из файла (страница 29)
Теперь мы можем легко вычислить математическое ожидание количества выпадений орла: Таким образом, индикаторные случайные величины значительно упростили вычисления по сравнению с методом, использующимся в уравнении (В.Зб). Вы еще не раз встретитесь с этими величинами в данной книге. Анализ задачи о найме сотрудника с помощью индикаторных случайных величин Вернемся к задаче о найме сотрудника, в которой нужно вычислить математическое ожидание события, соответствующего найму нового менеджера. Чтобы провести вероятностный анализ, предположим, что кандидаты приходят на собеседование в случайном порядке (этот вопрос уже обсуждался в предыдущем разделе; в разделе 5.3 будет показано, каким образом можно обойтись без этого предположения).
Пусть Х вЂ” случайная величина, значение которой равно количеству наймов нового офис-менеджера. Далее можно воспользоваться определением Глава 5. Вероятностный анализ и рандомизированные алгоритмы 147 математического ожидания (уравнение В.19) и получить соотношение и Е[Х] = ,'~ хРг(Х = х), но эти вычисления окажутся слишком громоздкими. Вместо этого воспользуемся индикаторными случайными величинами, благодаря чему вычисления значительно упростятся. Чтобы воспользоваться индикаторными случайными величинами, вместо вычисления величины Е [Х] путем определения одного значения, связанного с числом наймов нового менеджера, определим п величин, связанных с наймом конкретных кандидатов. В частности, пусть Х; — индикаторная случайная величина, связанная с событием найма г-го кандидата.
Таким образом, ['1 Х; = 1(1-й кандидат нанят) = ~[0 если г-й кандидат нанят, (5.2) если 1-й кандидат отклонен, и Х = Х1+Хз+ ° ° +Х„. (5.3) Из леммы 5.1 следует, что Е [Х,] = Рг (1-й кандидат нанят), и теперь нам надо вычислить вероятность выполнения строк 5 и б процедуры Н1кю Азязтлхт. Работодатель нанимает кандидата под номером г' (строка 5), только если он окажется лучше всех предыдущих (от 1-го до г — 1-го). Поскольку мы предположили, что кандидаты приходят на собеседование в случайном порядке, это означает, что первые г кандидатов также прибыли в случайном порядке. Любой из первых 1 кандидатов с равной вероятностью может оказаться лучшим. Поэтому вероятность того, что квалификация претендента с номером г выше квалификации претендентов с номерами от 1 до г — 1, и что он будет взят на работу, равна 1/1.
Пользуясь леммой 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 проявляется различие между вероятностным анализом и рандомизированными алгоритмами.
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
