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

Тип рандомизированного алгоритма

В вычислительной технике алгоритм Лас-Вегаса — это рандомизированный алгоритм , который всегда выдает правильные результаты; то есть он всегда выдает правильный результат или сообщает об ошибке. Однако время выполнения алгоритма Лас-Вегаса различается в зависимости от входных данных. Обычное определение алгоритма Лас-Вегаса включает ограничение, что ожидаемое время выполнения должно быть конечным, где ожидание выполняется в пространстве случайной информации или энтропии, используемой в алгоритме. Альтернативное определение требует, чтобы алгоритм Лас-Вегаса всегда завершался (был эффективным ), но мог выводить символ, не являющийся частью пространства решений, чтобы указать на неудачу в поиске решения. ^[1] Природа алгоритмов Лас-Вегаса делает их подходящими в ситуациях, когда число возможных решений ограничено, и когда проверка правильности потенциального решения относительно проста, а поиск решения сложен.

Методы систематического поиска для вычислительно сложных задач, такие как некоторые варианты алгоритма Дэвиса-Патнэма для пропозициональной выполнимости (SAT), также используют недетерминированные решения и, таким образом, могут также считаться алгоритмами Лас-Вегаса. ^[2]

История

Алгоритмы Лас-Вегаса были введены Ласло Бабаем в 1979 году в контексте проблемы изоморфизма графов как двойственные алгоритмам Монте-Карло . ^[3] Бабай ^[4] ввел термин «алгоритм Лас-Вегаса» вместе с примером, включающим подбрасывание монеты: алгоритм зависит от серии независимых подбрасываний монеты, и существует небольшая вероятность неудачи (отсутствия результата). Однако, в отличие от алгоритмов Монте-Карло, алгоритм Лас-Вегаса может гарантировать правильность любого сообщенного результата.

Пример

// Алгоритм Лас-Вегасаповторить : k = СлучайИнт ( n )   если А [ к ] == 1 ,    вернуть к ; 

Как упоминалось выше, алгоритмы Лас-Вегаса всегда возвращают правильные результаты. Приведенный выше код иллюстрирует это свойство. Переменная k генерируется случайным образом; после генерации k используется для индексации массива A. Если этот индекс содержит значение 1, то возвращается k ; в противном случае алгоритм повторяет этот процесс, пока не найдет 1. Хотя этот алгоритм Лас-Вегаса гарантированно найдет правильный ответ, у него нет фиксированного времени выполнения; из-за рандомизации (в строке 3 приведенного выше кода) может пройти сколь угодно много времени, прежде чем алгоритм завершит работу.

Определение

В этом разделе приводятся условия, характеризующие принадлежность алгоритма к типу Лас-Вегаса.

Алгоритм A является алгоритмом Лас-Вегаса для класса задач X, если ^[5]

1. всякий раз, когда для заданного экземпляра задачи x∈X возвращается решение s, s гарантированно является допустимым решением x
2. для каждого заданного экземпляра x время выполнения A является случайной величиной RT _A,x

Для алгоритмов Лас-Вегаса существует три понятия полноты :

• Полные алгоритмы Лас-Вегаса могут гарантированно решить каждую разрешимую задачу в течение времени выполнения t max, где t max — константа, зависящая от экземпляра.

Пусть P(RT _A,x ≤ t) обозначает вероятность того, что A находит решение для разрешимого примера x за время в пределах t, тогда A является полным в точности, если для каждого x существует

некоторое t max такое, что P(RT _A,x ≤ t _max ) = 1.

• Приблизительно полные алгоритмы Лас-Вегаса решают каждую задачу с вероятностью, стремящейся к 1, когда время выполнения стремится к бесконечности. Таким образом, A является приблизительно полным, если для каждого экземпляра x, lim _t→∞ P(RT _A,x ≤ t) = 1.
• По сути неполные алгоритмы Лас-Вегаса — это алгоритмы Лас-Вегаса, которые не являются приблизительно полными.

Приблизительная полнота представляет в первую очередь теоретический интерес, поскольку временные рамки поиска решений обычно слишком велики, чтобы иметь практическое применение.

Сценарии применения

Алгоритмы Лас-Вегаса имеют различные критерии оценки, основанные на постановке задачи. Эти критерии делятся на три категории с различными временными ограничениями, поскольку алгоритмы Лас-Вегаса не имеют заданной временной сложности. Вот некоторые возможные сценарии применения:

• Тип 1: Ограничений по времени нет, то есть алгоритм работает до тех пор, пока не найдет решение.
• Тип 2: Существует ограничение по времени t _max для нахождения результата.
• Тип 3: Полезность решения определяется временем, необходимым для его поиска.

(Тип 1 и Тип 2 являются частными случаями Типа 3.)

Для типа 1, где нет ограничения по времени, среднее время выполнения может представлять поведение во время выполнения. Это не то же самое для типа 2.

Здесь P ( RT ≤ t _max ), представляющая собой вероятность нахождения решения в течение времени, описывает его поведение во время выполнения.

В случае типа 3 его поведение во время выполнения может быть представлено только функцией распределения во время выполнения rtd : R → [0,1], определяемой как rtd ( t ) = P ( RT ≤ t ) или ее приближением.

Распределение времени выполнения (RTD) — это особый способ описания поведения алгоритма Лас-Вегаса во время выполнения.

Используя эти данные, мы можем легко получить другие критерии, такие как среднее время выполнения, стандартное отклонение, медиана, процентили или вероятности успеха P ( RT ≤ t ) для произвольных временных ограничений t .

Приложения

Аналогия

Алгоритмы Лас-Вегаса часто возникают в задачах поиска . Например, тот, кто ищет информацию в Интернете, может искать нужную информацию на связанных веб-сайтах. Таким образом, временная сложность варьируется от «повезет» и немедленного нахождения контента до «не повезет» и траты большого количества времени. Как только нужный веб-сайт найден, возможность ошибки исключается. ^[6]

Рандомизированная быстрая сортировка

ВХОД :  # A — массив из n элементов def  randomized_quicksort ( A ):  if  n  ==  1 :  return  A  # A отсортирован.  else :  i  =  random . randrange ( 1 ,  n )  # Возьмет случайное число в диапазоне 1~n  X  =  A [ i ]  # Опорный элемент """Разбить A на элементы < x, x и >x # как показано на рисунке выше.  Выполнить быструю сортировку для A[1 to i-1] и A[i+1 to n].  Объединить ответы, чтобы получить отсортированный массив.""" 

Простым примером является рандомизированная быстрая сортировка , где опорный элемент выбирается случайным образом и делит элементы на три части: элементы, меньшие опорного элемента, элементы, равные опорному элементу, и элементы, большие опорного элемента. Быстрая сортировка всегда генерирует решение, которым в данном случае является отсортированный массив. К сожалению, временная сложность не так очевидна. Оказывается, время выполнения зависит от того, какой элемент мы выбираем в качестве опорного элемента.

• Наихудший случай Θ( n ² ), когда опорный элемент является наименьшим или наибольшим элементом.

${\displaystyle T(n)=T(0)+T(n-1)+\Theta (n)}$

${\displaystyle T(n)=\Theta (1)+T(n-1)+\Theta (n)}$

${\displaystyle T(n)=T(n-1)+\Theta (n)}$

${\displaystyle T(n)=\Theta (n^{2})}$

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

${\displaystyle T(n)\leq 2*T(n/2)+\Theta (n)}$

${\displaystyle T(n)=\Theta (n\log(n))}$

Время выполнения быстрой сортировки во многом зависит от того, насколько хорошо выбран опорный элемент. Если значение опорного элемента слишком велико или слишком мало, разделение будет несбалансированным, что приведет к низкой эффективности выполнения. Однако, если значение опорного элемента находится близко к середине массива, то разделение будет достаточно хорошо сбалансированным, что приведет к более быстрому выполнению. Поскольку опорный элемент выбирается случайным образом, время выполнения будет хорошим большую часть времени и плохим иногда.

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

Хотя худшее время выполнения составляет Θ( n ² ), среднее время выполнения составляет Θ( n log n ). Оказывается, что худший случай случается нечасто. Для больших значений n время выполнения составляет Θ( n log n ) с высокой вероятностью.

Обратите внимание, что вероятность того, что опорный элемент является элементом со средним значением, каждый раз составляет одно из n чисел, что случается очень редко. Однако это все равно то же самое время выполнения, когда разделение составляет 10%-90% вместо 50%-50%, поскольку глубина дерева рекурсии все еще будет O (log n ) с O ( n ) раз, взятыми на каждом уровне рекурсии.

Рандомизированный жадный алгоритм для задачи о восьми ферзях

Задача о восьми ферзях обычно решается с помощью алгоритма обратного отслеживания. Однако можно применить алгоритм Лас-Вегаса; на самом деле, он более эффективен, чем обратное отслеживание.

Расположите 8 ферзей на шахматной доске так, чтобы никто не атаковал другого. Помните, что ферзь атакует другие фигуры в той же строке, столбце и диагонали.

Предположим, что k рядов, 0 ≤ k ≤ 8, успешно заняты ферзями.

Если k = 8, то останавливаемся с успехом. В противном случае продолжаем занимать строку k + 1.

Подсчитать все позиции в этом ряду, не атакованные существующими ферзями. Если их нет, то неудача. В противном случае выбрать одну наугад, увеличить k и повторить.

Обратите внимание, что алгоритм просто терпит неудачу, если ферзя нельзя разместить. Но процесс можно повторить, и каждый раз будет генерироваться другая расстановка. ^[7]

Класс сложности

Класс сложности задач принятия решений , имеющих алгоритмы Лас-Вегаса с ожидаемым полиномиальным временем выполнения, — ZPP .

Оказывается, что

${\displaystyle {\textsf {ZPP}}={\textsf {RP}}\cap {\textsf {co-RP}}}$

что тесно связано с тем, как иногда строятся алгоритмы Лас-Вегаса. А именно, класс RP состоит из всех задач принятия решений, для которых существует рандомизированный алгоритм полиномиального времени, который всегда отвечает правильно, когда правильный ответ «нет», но может быть неправильным с определенной вероятностью, ограниченной единицей, когда ответ «да». Когда такой алгоритм существует как для задачи, так и для ее дополнения (с поменянными ответами «да» и «нет»), два алгоритма могут быть запущены одновременно и многократно: запустить каждый для постоянного числа шагов, по очереди, пока один из них не вернет окончательный ответ. Это стандартный способ построения алгоритма Лас-Вегаса, который работает за ожидаемое полиномиальное время. Обратите внимание, что в общем случае не существует верхней границы наихудшего случая для времени выполнения алгоритма Лас-Вегаса.

Оптимальный алгоритм Лас-Вегаса

Чтобы сделать алгоритм Лас-Вегаса оптимальным, ожидаемое время выполнения должно быть минимизировано. Это можно сделать следующим образом:

1. Алгоритм Лас-Вегаса A ( x ) выполняется многократно в течение некоторого числа шагов t _{1. Если} A ( x ) останавливается во время выполнения, то A ( x ) завершается; в противном случае повторяем процесс с начала еще для t ₂ шагов и так далее.
2. Разработка стратегии, которая является оптимальной среди всех стратегий для A ( x ), учитывая полную информацию о распределении T _A ( x ).

Существование оптимальной стратегии может быть увлекательным теоретическим наблюдением. Однако это непрактично в реальной жизни, поскольку нелегко найти информацию о распределении T _A ( x ). Более того, нет смысла проводить эксперимент повторно, чтобы получить информацию о распределении, поскольку в большинстве случаев ответ нужен только один раз для любого x . ^[8]

Связь с алгоритмами Монте-Карло

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

Вот таблица сравнения алгоритмов Лас-Вегаса и Монте-Карло: ^[9]

Если доступен детерминированный способ проверки корректности, то можно превратить алгоритм Монте-Карло в алгоритм Лас-Вегаса. Однако сложно преобразовать алгоритм Монте-Карло в алгоритм Лас-Вегаса без способа проверки алгоритма. С другой стороны, изменить алгоритм Лас-Вегаса на алгоритм Монте-Карло легко. Это можно сделать, запустив алгоритм Лас-Вегаса на определенный период времени, заданный параметром уверенности. Если алгоритм находит решение в течение этого времени, то это успех, а если нет, то вывод может быть просто «извините».

Вот пример алгоритмов Лас-Вегаса и Монте-Карло для сравнения: ^[10]

Предположим, что есть массив длиной четного n . Половина элементов массива — 0, а оставшаяся половина — 1. Цель здесь — найти индекс, содержащий 1.

// Повтор алгоритма Лас-Вегаса : k = RandInt ( n ) если A [ k ] == 1 , вернуть k ; // Повтор алгоритма Монте-Карло 300 раз : k = RandInt ( n ) если A [ k ] == 1 , вернуть k вернуть "Failed"                      

Поскольку Las Vegas не заканчивается, пока не найдет 1 в массиве, он играет не с правильностью, а со временем выполнения. С другой стороны, Monte Carlo запускается 300 раз, что означает, что невозможно знать, что Monte Carlo найдет "1" в массиве в течение 300 циклов, пока он фактически не выполнит код. Он может найти решение или нет. Поэтому, в отличие от Las Vegas, Monte Carlo играет не со временем выполнения, а с правильностью.

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

• Алгоритм Монте-Карло
• Алгоритм Атлантик-Сити
• Случайность

Ссылки

Цитаты

1. Стивен Д. Гэлбрейт (2012). Математика криптографии с открытым ключом . Cambridge University Press. стр. 16. ISBN 978-1-107-01392-6.
2. Хус, Хольгер Х.. «Об эмпирической оценке алгоритмов Лас-Вегаса — Аналитическая статья». (1998).
3. * Ласло Бабай , Алгоритмы Монте-Карло для проверки изоморфизма графов, Университет Монреаля, DMS № 79-10.
   • Леонид Левин , Сказка об односторонних функциях, Проблемы передачи информации , т. 39 (2003), 92-103.
   • Дэн Гранди, Концепции и вычисления в криптографии. Архивировано 12 апреля 2016 г. в Wayback Machine , Кентский университет, докторская диссертация, 2008 г.
4. Бабай, Ласло. «Алгоритмы Монте-Карло в тестировании изоморфизма графов». (1979).
5. HH Hoos и T. Stützle. Оценка алгоритмов Лас-Вегаса — подводные камни и средства их устранения. В трудах четырнадцатой конференции по неопределенности в искусственном интеллекте (UAI-98), страницы 238–245. Morgan Kaufmann Publishers, Сан-Франциско, Калифорния, 1998.
6. Рандомизированные алгоритмы. Brilliant.org . Получено 23:54, 24 октября 2018 г. с https://brilliant.org/wiki/Las_Vegas_algorithm/randomized-algorithms-overview/
7. Барринджер, Ховард (декабрь 2010 г.). «Рандомизированные алгоритмы — краткое введение» (PDF) . www.cs.man.ac.uk . Получено 08.12.2018 .
8. Luby, Michael (27 сентября 1993 г.). «Оптимальное ускорение алгоритмов Лас-Вегаса». Information Processing Letters . 47 (4): 173–180. doi :10.1016/0020-0190(93)90029-9.
9. Гудрич, Майкл. Разработка и применение алгоритмов: рандомизированные алгоритмы. Wiley, 2015 , https://nscpolteksby.ac.id/ebook/files/Ebook/Computer%20Engineering/Algorithm%20Design%20and%20Applications%20A4%20(2015)/20.%20Chapter%2019%20-%20Randomized%20Algorithms.pdf. 23 октября 2018 г.
10. Прокачча, Ариэль (5 ноября 2015 г.). «Великие теоретические идеи в информатике» (PDF) . www.cs.cmu.edu ( PowerPoint ) . Получено 3 ноября 2018 г. .

Источники

• Справочник по алгоритмам и теории вычислений , CRC Press LLC, 1999.
• «Алгоритм Лас-Вегаса», в Словаре алгоритмов и структур данных [онлайн], Пол Э. Блэк, редактор, Национальный институт стандартов и технологий США . 17 июля 2006 г. (дата обращения: 9 мая 2009 г.) Доступно с: [1]