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

Лас-Вегас — вид вероятностного алгоритма (см. также Метод Монте-Карло).

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

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

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

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

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