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

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

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

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

Приклад

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

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

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