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

редактировать

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

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

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

Содержание

1 Мотивация
2 Вычислительная сложность
3 История
4 Примеры
- 4.1 Quicksort
- 4.2 Рандомизированные инкрементные конструкции в геометрии
- 4.3 Min cut
5 Дерандомизация
6 Где помогает случайность
7 См. Также
8 Примечания
9 Ссылки

Мотивация

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

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

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

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

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

findA_LV (array A, n) begin repeat Случайно выбрать один элемент из n элементов. пока не будет найдено 'a' end

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

lim n → ∞ ∑ i = ⁡ 1 ni 2 i = 2 {\ displaystyle \ lim _ {n \ to \ infty} \ sum _ {i \ mathop {=} 1} ^ {n} {\ frac {i} {2 ^ {i}}} = 2}

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

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

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

findA_MC (array A, n, k) begin i = 0 repeat Случайно выберите один элемент из n элементов. I = i + 1, пока i = k или найдено 'a' end

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

$Pr [finda] = 1 - (1/2) k {\ displaystyle \ Pr [\ mathrm {find ~ a}] = 1- (1/2) ^ {k}}$ $\ Pr [{\ mathrm {find ~ a}}] = 1- (1/2) ^ {k}$

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

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

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

Вычислительная сложность

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

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

История

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

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

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

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

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

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

Примеры

Quicksort

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

Рандомизированные инкрементные конструкции в геометрии

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

Min cut

Input : A graph G (V, E)

Output : A cut разбиение вершин на L и R с минимальным количеством ребер между L и R.

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

Рис. 2: Успешный запуск алгоритма Каргера на 10-вершинном графе. Минимальный разрез имеет размер 3 и обозначен цветами вершин.

Рисунок 1: Сокращение вершин A и B

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

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

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

Лемма 1 : Пусть k будет минимальным размером разреза, и пусть C = {e 1,e2,..., e k } быть минимальным сокращением. Если во время итерации i ни одно ребро e ∈ C не выбрано для сжатия, то C i = 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 - различные вершины. Пока мы выбираем край $f ≠ e {\ displaystyle f \ neq e}$ ${\ displaystyle f \ neq e}$ , u и v не объединяются. Таким образом, в конце алгоритма у нас есть два составных узла, покрывающих весь граф, один из которых состоит из вершин L, а другой - из вершин R. Как и на рисунке 2, размер минимального разреза равен 1, и С = {(А, В)}. Если мы не выберем (A, B) для сокращения, мы можем получить минимальное сокращение.

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

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

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

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

$i = 1 m Pr (C i ≠ C) = ∏ i = 1 m (1 - Pr (C i = C)). {\ Displaystyle \ prod _ {я = 1} ^ {m} \ Pr (C_ {i} \ neq C) = \ prod _ {i = 1} ^ {m} (1- \ Pr (C_ {i} = C)).}$ $\ prod _ {{i = 1}} ^ {m} \ Pr (C_ {i} \ neq C) = \ prod _ {{i = 1}} ^ {m} (1- \ Pr (C_ {i} = C)).$

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

Таким образом, $1 - k | E (G j) | ≥ 1-2 N - J = N - J - 2 N - J {\ Displaystyle 1 - {\ frac {k} {| E (G_ {j}) |}} \ geq 1 - {\ frac {2} { nj}} = {\ frac {nj-2} {nj}}}$ $1 - {\ frac {k} { | E (G_ {j}) |}} \ geq 1 - {\ frac {2} {nj}} = {\ frac {nj-2} {nj}}$ .

Итак, по цепному правилу вероятность нахождения минимального разреза C составляет $P r [C i = C] ≥ (n - 2 n) (n - 3 n - 1) (n - 4 n - 2)… (3 5) (2 4) (1 3). {\ 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).}$ $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).$

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

Дерандомизация

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

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

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

Там, где случайность помогает

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

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

См. Также

Примечания

Ссылки

Томас Х. Кормен, Чарльз Э. Лейзерсон, Рональд Л. Ривест и Клиффорд Стейн. Введение в алгоритмы, второе издание. 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.
M. Митценмахер и Э. Упфал. Вероятность и вычисления: рандомизированные алгоритмы и вероятностный анализ. Издательство Кембриджского университета, Нью-Йорк (Нью-Йорк), 2005.
Раджив Мотвани и П. Рагхаван. Рандомизированные алгоритмы. Издательство Кембриджского университета, Нью-Йорк (Нью-Йорк), 1995.
Раджив Мотвани и П. Рагхаван. Рандомизированные алгоритмы. Обзор рандомизированных алгоритмов.
Христос Пападимитриу (1993), Computational Complexity (1-е изд.), Эддисон Уэсли, ISBN 978- 0-201-53082-7 Глава 11: Случайные вычисления, стр. 241–278.
Рабин, Майкл О. (1980). «Вероятностный алгоритм проверки простоты». Журнал теории чисел. 12 : 128–138. doi : 10.1016 / 0022-314X (80) 90084-0.
A. А. Цай, В. С. Лавджой, Дэвид Р. Каргер, Случайная выборка в задачах вырезания, потока и проектирования сети, Математика исследования операций, 24 (2): 383–413, 1999.