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

«Рандомизированные алгоритмы» перенаправляются сюда. Не путать с алгоритмической случайностью .

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

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

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

Мотивация

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

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

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

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

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

findingA_LV(array A, n)
begin
    repeat
        Randomly select one element out of n elements.
    until 'a' is found
end

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

$\lim _{n\to \infty }\sum _{i=1}^{n}{\frac {i}{2^{i}}}=2$

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

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

findingA_MC(array A, n, k)
begin
    i := 0
    repeat
        Randomly select one element out of n elements.
        i := i + 1
    until i = k or 'a' is found
end

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

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

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

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

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

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

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

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

Ранняя история

Сортировка

Быстрая сортировка была открыта Тони Хоаром в 1959 году и впоследствии опубликована в 1961 году. В том же году Хоар опубликовал алгоритм быстрого выбора , который находит медианный элемент списка за линейное ожидаемое время. До 1973 года оставалось открытым вопрос, существует ли детерминированный алгоритм с линейным временем.

Теория чисел

В 1917 году Генри Кэборн Поклингтон представил рандомизированный алгоритм, известный как алгоритм Поклингтона, для эффективного поиска квадратных корней по модулю простых чисел. В 1970 году Элвин Берлекамп представил рандомизированный алгоритм для эффективного вычисления корней многочлена над конечным полем. В 1977 году Роберт М. Соловей и Фолькер Штрассен с полиномиальным временем открыли рандомизированный тест на простоту (т. е. определение простоты числа). Вскоре после этого Майкл О. Рабин продемонстрировал, что тест Миллера на простоту 1976 года также можно превратить в рандомизированный алгоритм с полиномиальным временем. В то время не было известно доказуемо полиномиальных детерминированных алгоритмов для проверки простоты.

Структуры данных

Одной из первых рандомизированных структур данных является хеш-таблица , которая была введена в 1953 году Хансом Петером Луном из IBM . Хэш-таблица Луна использовала цепочки для разрешения коллизий, а также была одним из первых приложений связанных списков . Впоследствии, в 1954 году, Джин Амдал , Элейн М. МакГроу , Натаниэль Рочестер и Артур Сэмюэл из IBM Research представили линейное зондирование , хотя у Андрея Ершова независимо в 1957 году была такая же идея. В 1962 году Дональд Кнут выполнил первый правильный анализ линейного зондирования. хотя меморандум, содержащий его анализ, был опубликован гораздо позже. Первый опубликованный анализ был сделан Конхеймом и Вайсом в 1966 году.

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

Ранние работы над рандомизированными структурами данных также выходили за рамки хеш-таблиц. В 1970 году Бертон Ховард Блум представил структуру данных приблизительного членства, известную как фильтр Блума . В 1989 году Раймунд Зайдель и Сесилия Р. Арагон представили рандомизированное сбалансированное дерево поиска, известное как Treap . В том же году Уильям Пью представил еще одно рандомизированное дерево поиска, известное как список пропуска .

Неявное использование в комбинаторике

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

Примеры

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

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

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

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

Минимальный разрез

Основная статья: алгоритм Каргера

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

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

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

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

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

Каргера основной алгоритм:

begin
    i = 1
    repeat
        repeat
            Take a random edge (u,v) ∈ E in G
            replace u and v with the contraction u'
        until only 2 nodes remain
        obtain the corresponding cut result Ci
        i = i + 1
    until i = m
    output the minimum cut among C1, C2, ..., Cm.
end

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

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

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

Доказательство

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

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

Вероятность того, что алгоритм увенчается успехом, равна 1 — вероятность того, что все попытки потерпят неудачу. В силу независимости вероятность того, что все попытки потерпят неудачу, равна $$\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-{\frac {k}{|E(G_{j})|}}$. Обратите внимание, что G _j по-прежнему имеет минимальный разрез размера k , поэтому по лемме 2 он все еще имеет по крайней мере ${\frac {(n-j)k}{2}}$ края.

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

Таким образом, согласно цепному правилу, вероятность найти минимальный разрез C равна $$\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 {\frac {2}{n(n-1)}}$. Таким образом, вероятность успеха алгоритма равна как минимум $1-\left(1-{\frac {2}{n(n-1)}}\right)^{m}$. Для $m={\frac {n(n-1)}{2}}\ln n$, это эквивалентно $1-{\frac {1}{n}}$. Алгоритм находит минимальный разрез с вероятностью $1-{\frac {1}{n}}$, во времени $O(mn)=O(n^{3}\log n)$.

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

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

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

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

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

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

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

См. также

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

Ссылки

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