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

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

Идея алгоритма Лас-Вегас состоит в следующем. Если у нас есть некий вероятностный алгоритм $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. (англ.)