Русская Википедия:Лас-Вегас (алгоритм)

Содержание

Текст

Текст

Текст

Текст

Текст

Текст

Текст

Текст

Текст

Шаблон:Значения Лас-Вегас — вид вероятностного алгоритма (см. также Алгоритмы Монте-Карло).

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

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

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

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

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

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

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

Ссылки

• 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. Шаблон:Ref-en