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

См. также: Алгоритмы Монте-Карло

Лас-Вегас — вид вероятностного алгоритма.

Идея алгоритма Лас-Вегас состоит в следующем. Если у нас есть некий вероятностный алгоритм $A$, который с определенной вероятностью даёт верный результат, и существует возможность алгоритмически проверить результат алгоритма $A$ на корректность (скажем, с помощью алгоритма $K$), то можно выполнять алгоритм $A$ до тех пор, пока проверка не установит, что результат верен:

Выполнить алгоритм $A$ с результатом $r$ до тех пор, пока $K(r)$ не будет истиной.

Название этому принципу было дано с одной стороны как намек на метод Монте-Карло. С другой стороны это название намекает на «метод выигрыша в казино», которое схоже с процессом работы алгоритма — «если я буду играть ещё и ещё, я когда-нибудь обязательно выиграю».

Следует заметить, что алгоритм Лас-Вегаса гарантирует получение правильного результата. Алгоритм работает за конечное, но не детерминированное время. Можно указать только вероятность получения результата за заданное время.

Примеры

Данный псевдокод можно назвать примером алгоритма Лас-Вегас:

function lasvegas()
begin
    var a := random();
    
    if(verify(a) = true) then
        return a;
end

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

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

Пусть ${\mathcal {A}}$ - алгоритм Лас-Вегаса с ожидаемой временной сложностью $f(n)$, где $n$ - длина входа. Если остановить ${\mathcal {A}}$ после $\alpha \cdot f(n)$ шагов ($0<\alpha <1$), то мы получим алгоритм Монте-Карло ${\mathcal {B}}$ с вероятностью ошибки в $1/\alpha$. Для доказательства теоремы рассмотрим $x$ как вход длины $n$ и $T$ - случайную переменную, описывающую временную сложность ${\mathcal {A}}$. Тогда математическое ожидание $\mathbb {E} [T]\leqslant f(n)$ и согласно неравенству Маркова: $\mathbb {P} r[T\geqslant \alpha \cdot f(n)]\leqslant \mathbb {P} r[T\geqslant \alpha \cdot \mathbb {E} [T]]\leqslant 1/\alpha$.

Ссылки

• Algorithms and Theory of Computation Handbook, CRC Press LLC, 1999
• "Las Vegas algorithm" / Dictionary of Algorithms and Data Structures, Paul E. Black, ed., U.S. NIST. 17 July 2006.  (англ.)