Рандомизированный алгоритм - Википедия - Randomized algorithm

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

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

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

Мотивация

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

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

Выход: Найдите "а’В массиве.

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

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

findA_LV(множество А, п)начинать    повторение        Случайно Выбрать один элемент из из п элементы.    до того как 'а' является найденныйконец

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

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

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

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

поискA_MC(множество А, п, k)начинать    я=0    повторение        Случайно Выбрать один элемент из из п элементы.        я = я + 1    до того как я=k или же 'а' является найденныйконец

Если 'а’, Алгоритм работает, иначе алгоритм не работает. После k итераций, вероятность нахождения "а' является:

${ Displaystyle Pr [ mathrm {найти ~ а}] = 1- (1/2) ^ {k}}$

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

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

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

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

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

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

История

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

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

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

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

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

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

Примеры

Быстрая сортировка

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

Рандомизированные инкрементальные построения в геометрии

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

Мин вырез

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

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

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

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

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

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

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

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

Лемма 1: Позволять k быть минимальным размером разреза, и пусть $C = {е 1, е 2,..., е k}$ быть минимальным сокращением. Если во время итерации я, без края $е \in C$ выбирается для сжатия, то $C я = C$ .

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

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

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

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

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

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

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

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

Таким образом, по цепному правилу вероятность найти минимальный разрез 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 м = { гидроразрыва {п (п-1)} {2}} пер п}$ , это эквивалентно ${ displaystyle 1 - { frac {1} {n}}}$ . Алгоритм находит минимальный разрез с вероятностью ${ displaystyle 1 - { frac {1} {n}}}$ , во время ${ Displaystyle О (мн) = О (п ^ {3} журнал п)}$ .

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

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

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

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

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

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

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

Смотрите также

Примечания

^ Хоар, К. А. Р. (июль 1961 г.). «Алгоритм 64: Быстрая сортировка». Commun. ACM. 4 (7): 321–. Дои:10.1145/366622.366644. ISSN 0001-0782.
^ Куделич, Роберт (2016-04-01). «Рандомизированный алгоритм Монте-Карло для задачи о множестве дуг с минимальной обратной связью». Прикладные мягкие вычисления. 41: 235–246. Дои:10.1016 / j.asoc.2015.12.018.
^ "В проверка простоты случайным образом выбранных очень больших чисел, шанс наткнуться на значение, вводящее в заблуждение Тест Ферма меньше, чем шанс, что космическое излучение приведет к тому, что компьютер сделает ошибку при выполнении «правильного» алгоритма. Считая алгоритм неадекватным по первой причине, но не по второй, показывает разницу между математикой и инженерией ". Хэл Абельсон и Джеральд Дж. Сассман (1996). Структура и интерпретация компьютерных программ. MIT Press, раздел 1.2.
^ Смид, Мишель. Ближайшие точечные задачи вычислительной геометрии. Max-Planck-Institut für Informatik | год = 1995
^ Зайдель Р. Обратный анализ рандомизированных геометрических алгоритмов.
^ А. А. Цай, В. С. Лавджой, Дэвид Р. Каргер, Случайная выборка в задачах разреза, потока и проектирования сети, Математика исследования операций, 24 (2): 383–413, 1999.
^ Алиппи, Чезаре (2014), Интеллект для встраиваемых систем, Спрингер, ISBN 978-3-319-05278-6.
^ Кушилевиц, Эял; Нисан, Ноам (2006), Коммуникационная сложность, Издательство Кембриджского университета, ISBN 9780521029834. Детерминированную нижнюю оценку см. На стр. 11; относительно логарифмической рандомизированной верхней границы см. стр. 31–32.
^ Дайер, М .; Frieze, A .; Каннан, Р. (1991), «Случайный полиномиальный алгоритм аппроксимации объема выпуклых тел» (PDF), Журнал ACM, 38 (1): 1–17, Дои:10.1145/102782.102783
^ Фюреди, З.; Барань И. (1986), «Вычислить объем сложно», Proc. 18-й симпозиум ACM по теории вычислений (Беркли, Калифорния, 28–30 мая 1986 г.) (PDF), Нью-Йорк, Нью-Йорк: ACM, стр. 442–447, CiteSeerX 10.1.1.726.9448, Дои:10.1145/12130.12176, ISBN 0-89791-193-8
^ Шамир, А. (1992), "IP = PSPACE", Журнал ACM, 39 (4): 869–877, Дои:10.1145/146585.146609
^ Повар, Мэтью; Соловейчик, Давид; Винфри, Эрик; Брук, Иегошуа (2009), "Программируемость сетей химических реакций", в Кондон, Энн; Харел, Дэвид; Kok, Joost N .; Саломаа, Арто; Винфри, Эрик (ред.), Алгоритмические биопроцессы (PDF), Natural Computing Series, Springer-Verlag, стр. 543–584, Дои:10.1007/978-3-540-88869-7_27.