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

Лас-Вегас — увипадковлений алгоритм, що завжди повертає правильний результат; тобто, він завжди видає правильний результат або повідомляє про збій. Інакше кажучи, Лас-Вегас не грається із правильністю результату, а лише з ресурсами використовними для обчислень. Єдиною відмінністю між запусками на одних вхідних даних є час виконання, який може бути необмеженим, але очікуваний час виконання завжди обмежений. Простим прикладом є увипадковлене швидке сортування, де опірний елемент вибирають випадковим чином, але результат завжди правильний.

Алгоритм Лас-Вегаса представив Ласло Бабай у 1979, у контексті проблеми визначення чи два графи ізоморфні, як сильнішу версію алгоритму Монте-Карло. Алгоритм Лас-Вегаса можна використати в ситуаціях коли число можливих розв'язків порівняно обмежене і перевірка правильності кандидата в розв'язки порівняно проста тоді коли обчислення розв'язку складне.

Ім'я покликається до міста Лас-Вегас у штаті Невада, яке добре відоме своїм ігорним бізнесом.

Приклад

// алгоритм Лас-Вегас repeat:  k = RandInt(n)  if A[k] == 1,  return k; 

Зв'язок з алгоритмом Монте-Карло

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

Примітки

1. Ласло Бабай, Monte-Carlo algorithms in graph isomorphism testing [ 8 грудня 2017 у Wayback Machine.], Université de Montréal, D.M.S. No. 79-10.
2. Леонід Левін, The Tale of One-way Functions [Архівовано 9 липня 2012 у Archive.is], Problems of Information Transmission, vol. 39 (2003), 92-103.
3. Dan Grundy, Concepts and Calculation in Cryptography [ 12 квітня 2016 у Wayback Machine.], University of Kent, Ph.D. thesis, 2008