Лас-Вегас (алгоритм)
Лас-Вегас — увипадковлений алгоритм, що завжди повертає правильний результат; тобто, він завжди видає правильний результат або повідомляє про збій. Інакше кажучи, Лас-Вегас не грається із правильністю результату, а лише з ресурсами використовними для обчислень. Єдиною відмінністю між запусками на одних вхідних даних є час виконання, який може бути необмеженим, але очікуваний час виконання завжди обмежений. Простим прикладом є увипадковлене швидке сортування, де опірний елемент вибирають випадковим чином, але результат завжди правильний.
Алгоритм Лас-Вегаса представив Ласло Бабай у 1979, у контексті проблеми визначення чи два графи ізоморфні, як сильнішу версію алгоритму Монте-Карло.[1][2][3] Алгоритм Лас-Вегаса можна використати в ситуаціях коли число можливих розв'язків порівняно обмежене і перевірка правильності кандидата в розв'язки порівняно проста тоді коли обчислення розв'язку складне.
Ім'я покликається до міста Лас-Вегас у штаті Невада, яке добре відоме своїм ігорним бізнесом.
Приклад[ред. | ред. код]
// алгоритм Лас-Вегас
repeat:
k = RandInt(n)
if A[k] == 1,
return k;
Зв'язок з алгоритмом Монте-Карло[ред. | ред. код]
Алгоритм Лас-Вегаса можна протиставити алгоритму Монте-Карло, в якому використовні ресурси обмежені, але результат може бути неправильний. Через використання нерівності Маркова, алгоритм Лас-Вегаса можна перетворити у алгоритм Монте-Карло через ранню зупинку і повернення випадкового результату якщо алгоритм не встиг видати відповідь.
Примітки[ред. | ред. код]
- ↑ Ласло Бабай, Monte-Carlo algorithms in graph isomorphism testing [Архівовано 8 грудня 2017 у Wayback Machine.], Université de Montréal, D.M.S. No. 79-10.
- ↑ Леонід Левін, The Tale of One-way Functions [Архівовано 9 липня 2012 у Archive.is], Problems of Information Transmission, vol. 39 (2003), 92-103.
- ↑ Dan Grundy, Concepts and Calculation in Cryptography [Архівовано 12 квітня 2016 у Wayback Machine.], University of Kent, Ph.D. thesis, 2008