Рандомизированный алгоритм

алгоритм, который использует некоторую степень случайности как часть своей логики. Алгоритм обычно использует равномерно случайные биты в качестве вспомогательных входных данных для управления своим поведением в надежде на достижение хорошей производительности в «среднем случае» по всем возможным вариантам случайного выбора, определяемым случайными битами; таким образом, либо время выполнения, либо выход (или оба) являются случайными величинами.

Следует различать алгоритмы, которые используют случайный ввод, чтобы они всегда заканчивались правильным ответом, но где ожидаемое время выполнения конечно ( алгоритмы Лас-Вегаса , например Quicksort ^[1] ), и алгоритмы, которые могут дать неверный результат ( алгоритмы Монте-Карло , например, алгоритм Монте-Карло для задачи MFAS ^[2] ) или не дают результата, либо сигнализируя об ошибке, либо не завершая работу. В некоторых случаях вероятностные алгоритмы являются единственным практическим средством решения проблемы. ^[3]

В обычной практике рандомизированные алгоритмы аппроксимируются с использованием генератора псевдослучайных чисел вместо истинного источника случайных битов; такая реализация может отклоняться от ожидаемого теоретического поведения.

Мотивация [ править ]

В качестве мотивирующего примера рассмотрим задачу нахождения буквы « а » в массиве из n элементов.

Вход : массив из n ≥2 элементов, в котором половина - это буквы a , а другая половина - b .

Вывод : найдите « » в массиве.

Мы даем две версии алгоритма, один алгоритм Лас-Вегаса и один алгоритм Монте-Карло .

Алгоритм Лас-Вегаса:

findingA_LV ( массив  , п ) начинают повтор Произвольно выберите один элемент из из п элементов . до «а» будет найден конец              

Этот алгоритм работает с вероятностью 1. Число итераций варьируется и может быть сколь угодно большим, но ожидаемое количество итераций равно

${\ displaystyle \ lim _ {п \ к \ infty} \ sum _ {я \ mathop {=} 1} ^ {n} {\ frac {i} {2 ^ {i}}} = 2}$

Поскольку он постоянен, ожидаемое время выполнения для многих вызовов равно . (См. Обозначение Big O )${\ Displaystyle \ Theta (1)}$

Алгоритм Монте-Карло:

findingA_MC ( массив  , п , к ) начинают я = 0 повтор Произвольно выберите один элемент из из п элементов . i = i + 1, пока не будет найдено i = k или 'a' конец                       

Если « » найден, алгоритм завершается успешно, в противном случае алгоритм не удается. После k итераций вероятность найти ' a ' равна:

Этот алгоритм не гарантирует успеха, но время выполнения ограничено. Количество итераций всегда меньше или равно k. Принимая k постоянным, время выполнения (ожидаемое и абсолютное) равно .${\ Displaystyle \ Theta (1)}$

Рандомизированные алгоритмы особенно полезны при столкновении со злонамеренным «противником» или злоумышленником, который намеренно пытается ввести неверный ввод в алгоритм (см. Сложность наихудшего случая и анализ конкуренции (онлайн-алгоритм) ), например, в дилемме заключенного . Именно по этой причине случайность повсеместна в криптографии . В криптографических приложениях нельзя использовать псевдослучайные числа, поскольку злоумышленник может их предсказать, что делает алгоритм эффективно детерминированным. Следовательно, требуется либо источник действительно случайных чисел, либо криптографически безопасный генератор псевдослучайных чисел . Другая область, которой присуща случайность, - этоквантовые вычисления .

В приведенном выше примере алгоритм Лас-Вегаса всегда возвращает правильный ответ, но время его выполнения является случайной величиной. Алгоритм Монте-Карло (связанный с методом Монте-Карло для моделирования) гарантированно завершится за время, которое может быть ограничено функцией размером входных данных и ее параметром k , но допускает небольшую вероятность ошибки . Обратите внимание, что любой алгоритм Лас-Вегаса можно преобразовать в алгоритм Монте-Карло (с помощью неравенства Маркова), выводя произвольный, возможно, неправильный ответ, если он не может быть выполнен в течение указанного времени. И наоборот, если существует эффективная процедура проверки для проверки правильности ответа, то алгоритм Монте-Карло может быть преобразован в алгоритм Лас-Вегаса путем повторного запуска алгоритма Монте-Карло до получения правильного ответа.

Вычислительная сложность [ править ]

Теория вычислительной сложности моделирует рандомизированные алгоритмы как вероятностные машины Тьюринга . И Лас - Вегас и Монте - Карло алгоритмы рассматриваются и некоторые классы сложности изучаются. Самым базовым классом рандомизированной сложности является RP , который представляет собой класс задач решения, для которых существует эффективный (полиномиальное время) рандомизированный алгоритм (или вероятностная машина Тьюринга), который распознает NO-экземпляры с абсолютной уверенностью и распознает YES-экземпляры с вероятностью не менее 1/2. Класс дополнения для RP - co-RP. Классы проблем, имеющие (возможно, не завершающие) алгоритмы с полиномиальным временемсреднее время работы случая, вывод которого всегда правильный, называется ZPP .

Класс проблем, для которых разрешено идентифицировать как YES, так и NO-экземпляры с некоторой ошибкой, называется BPP . Этот класс действует как рандомизированный эквивалент P , т.е. BPP представляет класс эффективных рандомизированных алгоритмов.

История [ править ]

Исторически первым рандомизированным алгоритмом был метод, разработанный Майклом О. Рабиным для задачи ближайшей пары в вычислительной геометрии . ^[4] Исследование рандомизированных алгоритмов было стимулировано открытием в 1977 году рандомизированного теста на простоту (т. Е. Определения простоты числа) Робертом М. Соловаем и Фолькером Штрассеном . Вскоре после этого Майкл О. Рабин продемонстрировал, что критерий простоты Миллера 1976 года можно превратить в рандомизированный алгоритм. В то время не было известно практического детерминированного алгоритма простоты.

Тест на простоту Миллера-Рабина основан на бинарном соотношении между двумя положительными целыми числами k и n, которое можно выразить, сказав, что k «является свидетелем составности» n . Можно показать, что

• Если есть свидетель составности n , то n составное (т. Е. N не простое ), и
• Если n составное, то по крайней мере три четверти натуральных чисел меньше n свидетельствуют о его составности, и
• Существует быстрый алгоритм, который по k и n определяет, является ли k свидетелем составности n .

Отметим, что это означает, что проблема простоты находится в Co- RP .

Если случайным образом выбирается на 100 чисел меньше составного числа n , тогда вероятность не найти такого «свидетеля» составляет (1/4) ^100, так что для большинства практических целей это хороший тест на простоту. Если n большое, может не быть другого практического теста. Вероятность ошибки можно снизить до произвольной степени, выполнив достаточно независимых тестов.

Следовательно, на практике нет никаких штрафов, связанных с принятием малой вероятности ошибки, так как с небольшой осторожностью вероятность ошибки может быть сделана астрономически малой. В самом деле, несмотря на то, что с тех пор был найден детерминированный тест на простоту за полиномиальное время (см. Тест на простоту AKS ), он не заменил старые вероятностные тесты в криптографическом программном обеспечении, и не ожидается, что он сделает это в обозримом будущем.

Примеры [ править ]

Быстрая сортировка [ править ]

Быстрая сортировка - это знакомый, часто используемый алгоритм, в котором может быть полезна случайность. Многие детерминированные версии этого алгоритма требуют времени O ( n ² ) для сортировки n чисел для некоторого четко определенного класса вырожденных входных данных (например, уже отсортированного массива) с конкретным классом входных данных, которые генерируют это поведение, определенное протоколом для поворотный выбор. Однако, если алгоритм выбирает поворотные элементы равномерно и случайным образом, он имеет доказуемо высокую вероятность завершения за время O ( n  log  n ) независимо от характеристик входных данных.

Рандомизированные инкрементальные конструкции в геометрии [ править ]

В вычислительной геометрии стандартный метод построения такой структуры, как выпуклая оболочка или триангуляция Делоне, состоит в том, чтобы случайным образом переставлять входные точки, а затем вставлять их одну за другой в существующую структуру. Рандомизация гарантирует, что ожидаемое количество изменений в структуре, вызванных вставкой, невелико, и поэтому ожидаемое время работы алгоритма может быть ограничено сверху. Этот метод известен как рандомизированное инкрементное строительство . ^[5]

Мин. Сокращение [ править ]

Вход : график G ( V , E ).

Выход : а вырезать разбиения вершин в L и R , с минимальным числом ребер между L и R .

Напомним, что сжатие двух узлов, u и v , в (мульти-) графе дает новый узел u 'с ребрами, которые являются объединением ребер, инцидентных либо u, либо v , за исключением любого ребра (ов), соединяющего u и v . На рисунке 1 приведен пример сжатия вершины A и B . После сжатия полученный граф может иметь параллельные ребра, но не содержать петель.

Базовый алгоритм Каргера ^[6] :

начинать я = 1 повторить  повторить Возьмем случайное ребро (u, v) ∈ E в G заменить u и v сокращением u ' пока не останется только 2 узла получить соответствующий результат разреза C i я = я + 1 пока я = м вывести минимальный разрез среди C 1 , C 2 , ..., C m .конец

При каждом выполнении внешнего цикла алгоритм повторяет внутренний цикл до тех пор, пока не останется только 2 узла, и будет получен соответствующий разрез. Время выполнения одного выполнения равно , а n обозначает количество вершин. После m раз выполнения внешнего цикла мы выводим минимальное сокращение среди всех результатов. На рисунке 2 приведен пример одного выполнения алгоритма. После выполнения у нас получается вырез 3 размера.${\ Displaystyle О (п)}$

Лемма 1. Пусть k - минимальный размер разреза, и пусть C = { e ₁ , e ₂ , ..., e _k } - минимальный размер разреза. Если во время итерации я , ни одно ребро е ∈ C выбран для сжатия, то С _я  =  С .

Доказательство : если G не связна, то G можно разбить на L и R без ребер между ними. Таким образом, минимальный разрез в несвязном графе равен 0. Теперь предположим, что G связан. Пусть V = L ∪ R - разбиение V, индуцированное C  : C = {{ u , v } ∈ E  : u ∈ L , v ∈ R } (корректно определено, поскольку G связна). Рассмотрим ребро { u ,v } из C . Изначально u , v - различные вершины. Пока мы выбираем ребро , u и v не сливаются.${\ displaystyle f \ neq e}$ Таким образом, в конце алгоритма, мы имеем два составных узлов , охватывающие весь граф, один из которых состоят из вершин L , а других , состоящих из вершин R . Как и на рисунке 2, размер минимального разреза равен 1, и C = {( A , B )}. Если мы не выберем ( A , B ) для сокращения, мы можем получить минимальное сокращение.

Лемма 2 : Если G - мультиграф с p вершинами и минимальный разрез которого имеет размер k , то G имеет не менее pk / 2 ребер.

Доказательство . Поскольку минимальный разрез равен k , каждая вершина v должна удовлетворять степени ( v ) ≥ k . Следовательно, сумма степеней не меньше pk . Но, как известно, сумма степеней вершин равна 2 | E |, Лемма следует.

Анализ алгоритма

Вероятность успеха алгоритма равна 1 - вероятность того, что все попытки потерпят неудачу. По независимости вероятность того, что все попытки потерпят неудачу, равна

По лемме 1 вероятность того, что C _i  =  C - это вероятность того, что ни одно ребро C не будет выбрано во время итерации i . Рассмотрим внутренний цикл и обозначим через G _j граф после j сжатий ребер, где j  ∈ {0,1, ..., n  - 3} . G _j имеет n  -  j вершин. Мы используем цепное правило условных возможностей . Вероятность того, что ребро, выбранное на итерации j , не входит в C , учитывая, что никакое ребро Cбыл выбран раньше, есть . Заметим, что G _j все еще имеет минимальный разрез размера k , поэтому по лемме 2 он все еще имеет не менее ребер.${\ displaystyle 1 - {\ frac {k} {| E (G_ {j}) |}}}$${\ displaystyle {\ frac {(nj) k} {2}}}$

Таким образом, .${\displaystyle 1-{\frac {k}{|E(G_{j})|}}\geq 1-{\frac {2}{n-j}}={\frac {n-j-2}{n-j}}}$

Таким образом, по цепному правилу вероятность найти минимальный разрез C равна${\displaystyle Pr[C_{i}=C]\geq \left({\frac {n-2}{n}}\right)\left({\frac {n-3}{n-1}}\right)\left({\frac {n-4}{n-2}}\right)\ldots \left({\frac {3}{5}}\right)\left({\frac {2}{4}}\right)\left({\frac {1}{3}}\right).}$

Аннулирование дает . Таким образом, вероятность успеха алгоритма не менее . Для это эквивалентно . Алгоритм находит минимальное сокращение с вероятностью во времени .${\displaystyle \Pr[C_{i}=C]\geq {\frac {2}{n(n-1)}}}$${\displaystyle 1-\left(1-{\frac {2}{n(n-1)}}\right)^{m}}$${\displaystyle m={\frac {n(n-1)}{2}}\ln n}$${\displaystyle 1-{\frac {1}{n}}}$${\displaystyle 1-{\frac {1}{n}}}$${\displaystyle O(mn)=O(n^{3}\log n)}$

Дерандомизация [ править ]

Случайность можно рассматривать как ресурс, как пространство и время. Дерандомизация - это процесс удаления случайности (или ее минимального использования). В настоящее время неизвестно, можно ли дерандомизировать все алгоритмы без значительного увеличения времени их работы. Например, с точки зрения вычислительной сложности неизвестно, является ли P = BPP , т. Е. Мы не знаем, можем ли мы взять произвольный рандомизированный алгоритм, который работает за полиномиальное время с небольшой вероятностью ошибки, и дерандомизировать его, чтобы он работал за полиномиальное время без использования случайности. .

Существуют определенные методы, которые можно использовать для дерандомизации определенных рандомизированных алгоритмов:

• метод условных вероятностей , и ее обобщение, пессимистические оценки
• теория несовпадений (которая используется для дерандомизации геометрических алгоритмов)
• использование ограниченной независимости случайных величин, используемых алгоритмом, например, парная независимость, используемая в универсальном хешировании
• использование расширяющих графов (или диспергаторов в целом) для усиления ограниченного количества начальной случайности (этот последний подход также называется генерацией псевдослучайных битов из случайного источника и ведет к связанной теме псевдослучайности)

Где помогает случайность [ править ]

Когда модель вычислений ограничивается машинами Тьюринга , в настоящее время остается открытым вопрос, позволяет ли способность делать случайный выбор решать некоторые задачи за полиномиальное время, которые не могут быть решены за полиномиальное время без этой возможности; это вопрос, является ли P = BPP. Однако в других контекстах есть конкретные примеры проблем, где рандомизация приводит к строгим улучшениям.

• Основываясь на начальном мотивирующем примере: учитывая экспоненциально длинную строку из 2 ^k символов, половину a и половину b, машине с произвольным доступом требуется 2 ^{k −1} поисков в худшем случае, чтобы найти индекс a ; если разрешено делать случайный выбор, он может решить эту проблему за ожидаемое полиномиальное число поисков.
• Естественный способ выполнения числовых вычислений во встроенных системах или киберфизических системах - обеспечить результат, который с высокой вероятностью приближается к правильному (или, вероятно, приблизительно правильному вычислению (PACC)). Сложная проблема, связанная с оценкой потери несоответствия между приближенным и правильным вычислением, может быть эффективно решена путем обращения к рандомизации ^[7]
• С точки зрения сложности связи равенство двух строк может быть проверено с некоторой надежностью, используя биты связи с рандомизированным протоколом. Любой детерминированный протокол требует битов при защите от сильного противника. ^[8]${\displaystyle \log n}$${\displaystyle \Theta (n)}$
• Объем выпуклого тела можно оценить с помощью рандомизированного алгоритма с произвольной точностью за полиномиальное время. ^[9] Барани и Фюреди показали, что ни один детерминированный алгоритм не может сделать то же самое. ^[10] Это верно безоговорочно, т.е. не полагаясь на какие-либо предположения теории сложности, предполагая, что выпуклое тело можно запросить только как черный ящик.
• Более теоретически сложный пример места, где случайность, кажется, помогает, - это класс IP . IP состоит из всех языков, которые могут быть приняты (с высокой вероятностью) полиномиально долгим взаимодействием между всемогущим доказывающим устройством и верификатором, реализующим алгоритм BPP. IP = PSPACE . ^[11] Однако, если требуется, чтобы верификатор был детерминированным, то IP = NP .
• В сети химических реакций (конечный набор реакций, таких как A + B → 2C + D, действующих на конечное число молекул), возможность когда-либо достичь заданного целевого состояния из начального состояния является разрешимой, при этом даже приближаясь к вероятности когда-либо достижение заданного целевого состояния (с использованием стандартной основанной на концентрации вероятности, для которой реакция произойдет дальше) неразрешимо. Более конкретно, ограниченная машина Тьюринга может быть смоделирована со сколь угодно высокой вероятностью правильной работы в течение всего времени, только если используется случайная сеть химических реакций. С простой недетерминированной сетью химических реакций (любая возможная реакция может произойти следующей) вычислительная мощность ограничена примитивными рекурсивными функциями . ^[12]

См. Также [ править ]

• Вероятностный анализ алгоритмов
• Алгоритм Атлантик-Сити
• Алгоритм Монте-Карло
• Алгоритм Лас-Вегаса
• Богосорт
• Принцип отложенного решения
• Рандомизированные алгоритмы как игры с нулевой суммой
• Вероятностная дорожная карта
• HyperLogLog
• count – min эскиз
• примерный алгоритм подсчета

Примечания [ править ]

Ссылки [ править ]

• Томас Х. Кормен , Чарльз Э. Лейзерсон , Рональд Л. Ривест и Клиффорд Штайн . Введение в алгоритмы , второе издание. MIT Press и McGraw – Hill, 1990. ISBN 0-262-03293-7 . Глава 5: Вероятностный анализ и рандомизированные алгоритмы, стр. 91–122. 
• Дирк Драхейм. « Семантика вероятностно-типизированного лямбда-исчисления (семантика цепи Маркова, поведение завершения и денотационная семантика) », Springer, 2017.
• Джон Кляйнберг и Ива Тардос . Разработка алгоритмов . Глава 13: «Рандомизированные алгоритмы».
• Фаллис, Д. (2000). «Надежность рандомизированных алгоритмов». Британский журнал философии науки . 51 (2): 255–271. DOI : 10.1093 / bjps / 51.2.255 .
• М. Митценмахер и Э. Упфаль . Вероятность и вычисления: рандомизированные алгоритмы и вероятностный анализ . Издательство Кембриджского университета, Нью-Йорк (Нью-Йорк), 2005.
• Раджив Мотвани и П. Рагхаван. Рандомизированные алгоритмы . Издательство Кембриджского университета, Нью-Йорк (Нью-Йорк), 1995.
• Раджив Мотвани и П. Рагхаван. Рандомизированные алгоритмы. Обзор рандомизированных алгоритмов.
• Христос Пападимитриу (1993), вычислительная сложность (1-е изд.), Эддисон Уэсли, ISBN 978-0-201-53082-7 Глава 11: Рандомизированные вычисления, стр. 241–278.
• Рабин, Майкл О. (1980). «Вероятностный алгоритм проверки простоты» . Журнал теории чисел . 12 : 128–138. DOI : 10.1016 / 0022-314X (80) 90084-0 .
• А.А. Цай, В.С. Лавджой, Дэвид Р. Каргер, Случайная выборка в задачах разрезания, потока и проектирования сети , Математика исследования операций, 24 (2): 383–413, 1999.