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

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

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

Алгоритмы Лас-Вегаса широко используются в области искусственного интеллекта, а также в других областях компьютерных наук и исследований операций. В AI алгоритмы стохастического локального поиска (SLS) считаются алгоритмами типа Лас-Вегаса. В последнее время алгоритмы SLS использовались для решения NP-полных задач принятия решений и NP-сложных задач комбинаторной оптимизации. Однако некоторые методы систематического поиска, такие как современные варианты алгоритма Дэвиса – Патнэма для пропозициональной выполнимости (SAT), также используют недетерминированные решения и, таким образом, также могут считаться алгоритмами Лас-Вегаса.

Содержание

  • 1 История
  • 2 Пример
  • 3 Определение
    • 3.1 Сценарии приложений
  • 4 Приложения
    • 4.1 Аналогия
    • 4.2 Рандомизированный QuickSort
    • 4.3 Рандомизированный жадный алгоритм для задачи восьми ферзей
  • 5 Класс сложности
  • 6 Оптимальный алгоритм Лас-Вегаса
  • 7 Связь с алгоритмами Монте-Карло
  • 8 См. Также
  • 9 Ссылки
    • 9.1 Цитаты
    • 9.2 Источники

История

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

Пример

1 // Алгоритм Лас-Вегаса 2 повторяется: 3 k = RandInt (n) 4 if A [k] == 1, 5 return k;

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

Определение

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

Алгоритм A является алгоритмом Лас-Вегаса для класса проблемы X, если

(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.
  • по существу неполный Las Алгоритмы Вегаса - это алгоритмы Лас-Вегаса, которые не являются приблизительно полными.

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

Сценарии приложений

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

Тип1: ограничений по времени нет, что означает, что алгоритм работает до тех пор, пока не найдет решение.

Тип2: существует ограничение по времени t max для нахождения результата.

Тип 3: полезность решения определяется временем, необходимым для его поиска.

Обратите внимание, что Type1 и Type2 являются частными случаями Type3.

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

Здесь P (RT ≤ t max), который представляет собой вероятность найти решение во времени, описывает его поведение во время выполнения..

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

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

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

Приложения

Аналогия

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

Randomized QuickSort

1 INPUT: 2 # A - это массив из n элементов 3 def randomized_quicksort (A): 4 if n = 1 : 5 return A # A отсортировано. 6 else: 7 i = random.randrange (1, n) # Возьмем случайное число в диапазоне 1 ~ n 8 X = A [i] # Сводный элемент 9 "" "Разделит A на элементы < x, x, and>x # как показано на рисунке выше. 10 Выполните быструю сортировку для A [от 1 до i-1] и A [от i + 1 до n]. 11 Объедините ответы, чтобы получить отсортированный массив. "" "

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

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

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

T (n) = T (0) + T (n - 1) + Θ (n) {\ displaystyle T ( n) знак равно T (0) + T (n-1) + \ Theta (n)}{\ Displaystyle Т (п) = Т (0) + Т (п-1) + \ Тета (п)}

T (n) = Θ (1) + T (n - 1) + Θ (n) {\ displaystyle T ( п) = \ тета (1) + Т (п-1) + \ тета (п)}{\ Displaystyle Т (п) = \ Тета (1) + Т (п-1) + \ Theta (n)}

Т (п) = Т (п - 1) + Θ (п) {\ Displaystyle Т (п) = Т (n-1) + \ Theta (n)}{\ displaystyle T (п) знак равно Т (п-1) + \ Тета (п)}

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

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

T (n) ≤ 2 ∗ T (n / 2) + Θ (n) {\ displaystyle T (n) \ Leq 2 * T (n / 2) + \ Theta (n)}{\ Displaystyle Т (п) \ Leq 2 * Т (п / 2) + \ Тета (п)}

T (n) = Θ (n log ⁡ (n)) {\ displaystyle T (n) = \ Theta ( n \ log (n))}{\ displaystyle T (n) = \ Theta (n \ log (n))}

Время работы QuickSort сильно зависит от того, насколько хорошо выбрана точка поворота. Если значение pivot слишком велико или мало, то раздел будет несбалансированным. Этот случай дает плохое время работы. Однако, если значение pivot близко к середине массива, то разбиение будет достаточно хорошо сбалансированным. Таким образом, время его работы будет хорошим. Поскольку точка поворота выбирается случайным образом, время работы в большинстве случаев будет хорошим, а иногда - плохим.

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

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

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

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

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

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

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

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

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

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

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

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

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

ZPP = RP ∩ co-RP {\ displaystyle {\textf {ZPP}} = {\textf {RP} } \ cap {\ textf {co-RP}}}{\ displaystyle {\textf {ZPP}} = {\textf {RP}} \ cap {\textf {co-RP}}}

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

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

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

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

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

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

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

Вот таблица, в которой сравниваются алгоритмы Лас-Вегаса и Монте-Карло:

Время выполненияКорректность
Алгоритм Лас-Вегасавероятностныйопределенный
Алгоритм Монте-Карлоопределенныйвероятностный

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

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

Предположим, что существует массив с длиной четного n. Половина массива - нули, а остальная половина - единицы. Цель здесь - найти индекс, содержащий 1.

0 // Алгоритм Лас-Вегаса 1 повтор: 2 k = RandInt (n) 3 if A [k] == 1, 4 return k; 5 6 // Алгоритм Монте-Карло 7 повторяется 300 раз: 8 k = RandInt (n) 9 if A [k] == 1 10 return k 11 return "Failed"

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

См. Также

Ссылки

Цитаты

Источники

Последняя правка сделана 2021-05-26 13:58:47
Содержание доступно по лицензии CC BY-SA 3.0 (если не указано иное).
Обратная связь: support@alphapedia.ru
Соглашение
О проекте