Введение
Тип рандомизированного алгоритма
В информатике алгоритм Лас-Вегаса — это рандомизированный алгоритм, который всегда выдает корректный результат; то есть, он либо всегда находит правильное решение, либо сообщает об неудаче. Однако время работы алгоритма Лас-Вегаса варьируется в зависимости от входных данных. Обычно определение алгоритма Лас-Вегаса включает ограничение, что математическое ожидание времени работы должно быть конечным, где вычисление математического ожидания производится по пространству случайной информации или энтропии, используемой в алгоритме. Альтернативное определение требует, чтобы алгоритм Лас-Вегаса всегда завершался (был вычислимым), но мог выдавать символ, не принадлежащий области допустимых решений, для индикации неудачи в поиске решения. Специфика алгоритмов Лас-Вегаса делает их подходящими для ситуаций, когда число возможных решений ограничено, и проверка корректности кандидатного решения относительно проста, в то время как поиск решения сложен. Систематические методы поиска для вычислительно трудных задач, такие как некоторые варианты алгоритма Дэвиса — Путнама для задачи выполнимости булевых формул (SAT), также используют недетерминированные решения и, следовательно, могут рассматриваться как алгоритмы Лас-Вегаса.
In computing, a Las Vegas algorithm is a randomized algorithm that always gives correct results; that is, it always produces the correct result or it informs about the failure. However, the runtime of a Las Vegas algorithm differs depending on the input. The usual definition of a Las Vegas algorithm includes the restriction that the expected runtime be finite, where the expectation is carried out over the space of random information, or entropy, used in the algorithm. An alternative definition requires that a Las Vegas algorithm always terminates (is effective), but may output a symbol not part of the solution space to indicate failure in finding a solution. The nature of Las Vegas algorithms makes them suitable in situations where the number of possible solutions is limited, and where verifying the correctness of a candidate solution is relatively easy while finding a solution is complex. Systematic search methods for computationally hard problems, such as some variants of the Davis–Putnam algorithm for propositional satisfiability (SAT), also utilize non deterministic decisions, and can thus also be considered Las Vegas algorithms.
История
Алгоритмы Лас-Вегаса были введены Ласло Бабаем в 1979 году в контексте задачи об изоморфизме графов как дуальные алгоритмам Монте-Карло. Бабаи ввёл термин «алгоритм Лас-Вегаса» вместе с примером, основанным на подбрасывании монеты: алгоритм зависит от последовательности независимых подбрасываний монеты, и существует небольшая вероятность неудачи (отсутствия результата). Однако, в отличие от алгоритмов Монте-Карло, алгоритм Лас-Вегаса может гарантировать корректность любого выдаваемого результата.
Сценарии применения
Алгоритмы Лас-Вегаса имеют различные критерии оценки, зависящие от постановки задачи. Эти критерии разделены на три категории с разными временными ограничениями, поскольку алгоритмы Лас-Вегаса не имеют фиксированной временной сложности. Вот некоторые возможные сценарии применения:
Тип 1: Временные ограничения отсутствуют, то есть алгоритм выполняется до тех пор, пока не будет найдено решение. Тип 2: Существует временной предел tmax для поиска результата. Тип 3: Ценность решения определяется временем, необходимым для его нахождения. (Типы 1 и 2 являются частными случаями типа 3). Для типа 1, где нет временных ограничений, среднее время выполнения может характеризовать поведение алгоритма. Это не относится к типу 2. Здесь P(RT ≤ tmax), то есть вероятность нахождения решения за время tmax, описывает его поведение во времени выполнения. В случае типа 3, его поведение во времени выполнения может быть представлено только функцией распределения времени выполнения rtd: R → [0,1], определяемой как rtd(t) = P(RT ≤ t) или ее приближением. Функция распределения времени выполнения (RTD) – это специфический способ описания поведения алгоритма Лас-Вегаса. На основе этих данных можно легко получить другие характеристики, такие как среднее время выполнения, стандартное отклонение, медиана, процентили или вероятности успеха P(RT ≤ t) для произвольных временных ограничений t.
Аналогия
Алгоритмы Лас-Вегаса часто встречаются в задачах поиска. Например, человек, ищущий информацию в сети, может просматривать связанные веб-сайты в надежде найти нужные данные. Временная сложность в этом случае варьируется от "удачного" моментального нахождения контента до "неудачного" и затраты большого количества времени. Как только подходящий веб-сайт найден, вероятность ошибки отсутствует.
Рандомизированный алчный алгоритм для задачи "Восемь королев"
Проблема восьми королев обычно решается с помощью алгоритма перебора с возвратом. Однако можно применить алгоритм Лас-Вегаса, который, на самом деле, более эффективен, чем перебор с возвратом. Расставьте 8 королев на шахматной доске так, чтобы ни одно из них не атаковало другое. Помните, что королева атакует другие фигуры на той же строке, столбце и по диагоналям. Предположим, что k строк, 0 ≤ k ≤ 8, успешно заняты королевами. Если k = 8, то завершите работу успешно. В противном случае перейдите к заполнению строки k + 1. Определите все позиции в этой строке, которые не находятся под атакой уже расставленных королев. Если таких позиций нет, то завершите работу с неудачей. В противном случае выберите одну случайную позицию, увеличьте k и повторите процесс. Обратите внимание, что алгоритм завершается неудачей, если не удается разместить королеву. Однако процесс можно повторять, и каждый раз будет генерироваться новая расстановка.
Оптимальный алгоритм Лас-Вегаса
Для того, чтобы сделать алгоритм Лас-Вегаса оптимальным, необходимо минимизировать ожидаемое время работы. Этого можно достичь следующим образом: алгоритм Лас-Вегаса A(x) многократно запускается на протяжении t1 шагов. Если A(x) останавливается в течение этого времени, то алгоритм завершает работу; в противном случае процесс повторяется с начала еще на t2 шагов, и так далее. Задача заключается в разработке стратегии, оптимальной среди всех возможных стратегий для A(x), при условии полного знания распределения времени работы TA(x). Само существование оптимальной стратегии может представлять собой интересный теоретический результат. Однако на практике это нереализуемо, поскольку сложно получить информацию о распределении TA(x). Более того, нет смысла многократно проводить эксперименты для получения этой информации, так как в большинстве случаев ответ требуется лишь единожды для любого x.
The Las Vegas algorithm A(x) runs repeatedly for some number t1 steps. If A(x) stops during the run time then A(x) is done; otherwise, repeat the process from the beginning for another t2 steps, and so on. Designing a strategy that is optimal among all strategies for A(x), given the full information about the distribution of TA(x). The existence of the optimal strategy might be a fascinating theoretical observation. However, it is not practical in real life because it is not easy to find the information of distribution of TA(x). Furthermore, there is no point of running the experiment repeatedly to obtain the information about the distribution since most of the time, the answer is needed only once for any x.