Лас-Вегас — увипадковлений алгоритм, що завжди повертає правильний результат; тобто, він завжди видає правильний результат або повідомляє про збій. Інакше кажучи, Лас-Вегас не грається із правильністю результату, а лише з ресурсами використовними для обчислень. Єдиною відмінністю між запусками на одних вхідних даних є час виконання, який може бути необмеженим, але очікуваний час виконання завжди обмежений. Простим прикладом є увипадковлене швидке сортування, де опірний елемент вибирають випадковим чином, але результат завжди правильний.
Алгоритм Лас-Вегаса представив Ласло Бабай у 1979, у контексті проблеми визначення чи два графи ізоморфні, як сильнішу версію алгоритму Монте-Карло.Ласло Бабай, Monte-Carlo algorithms in graph isomorphism testing , Université de Montréal, D.M.S. No. 79-10.Леонід Левін, The Tale of One-way Functions , Problems of Information Transmission, vol. 39 (2003), 92-103.Dan Grundy, Concepts and Calculation in Cryptography , University of Kent, Ph.D. thesis, 2008 Алгоритм Лас-Вегаса можна використати в ситуаціях коли число можливих розв'язків порівняно обмежене і перевірка правильності кандидата в розв'язки порівняно проста тоді коли обчислення розв'язку складне.
Ім'я покликається до міста Лас-Вегас у штаті Невада, яке добре відоме своїм ігорним бізнесом.
Приклад // алгоритм Лас-Вегас, припускаючи, що A — масив довжини n. // Мета: повернути правильний індекс k такий, що A[k] == 1 n = A.length repeat: k = RandInt(n) if A[k] == 1, return k;
Як зазначалося вище, алгоритм Лас-Вегас завжди повертає правильний результат. Наведений вище код ілюструє цю властивість. Мета полягає в тому, щоб знайти індекс у масиві A, який містить значення 1. Змінна k генерується випадковим чином; після того як k згенеровано, вона використовується для доступу до елементу масиву A. Якщо цей елемент дорівнює 1, то повертається k; інакше алгоритм повторює цей процес, доки не знайде 1. Хоча цей алгоритм Лас-Вегаса гарантує знаходження правильного відповіді, він не має фіксованого часу виконання; через випадковість (рядок 4 у коді) може пройти довільно багато часу, перш ніж алгоритм завершиться.
Визначення Алгоритм A є алгоритмом Лас-Вегаса для класу задач X, якщо: для кожного вхідного прикладу x ∈ X він повертає розв’язок s, і цей s гарантовано є коректним розв’язком x; для кожного входу x час роботи A є випадковою величиною RTA,x
Існує три поняття повноти для алгоритмів Лас-Вегаса:
повні алгоритми Лас-Вегаса — це алгоритми, які гарантовано знаходять розв’язок для кожної розв’язної задачі за час tmax, де tmax — константа, що залежить від конкретного вхідного прикладу.
Нехай P(RTA,x ≤ t) позначає ймовірність того, що A знайде розв’язок для розв’язного входу x за час, що не перевищує t. Тоді A є повним тоді й лише тоді, коли для кожного x існує деякий tmax такий, що P(RTA,x ≤ tmax) = 1.
приблизно повні алгоритми Лас-Вегаса — це алгоритми, які розв’язують кожну задачу з імовірністю, що прямує до 1, коли час виконання прямує до нескінченності. Тобто A є приблизно повним, якщо для кожного входу x виконується: limt→∞ P(RTA,x ≤ t) = 1.
суттєво неповні алгоритми Лас-Вегаса — алгоритми Лас-Вегаса, які не є приблизно повними.
Поняття приблизної повноти має переважно теоретичне значення, оскільки необхідні часові межі для гарантії знаходження розв’язку зазвичай є надто великими, щоб бути практично корисними.
Сценарії застосування
Алгоритми Лас-Вегаса мають різні критерії оцінювання залежно від постановки задачі. Ці критерії поділяються на три категорії з різними часовими обмеженнями, оскільки алгоритми Лас-Вегаса не мають фіксованої часової складності. Нижче наведено кілька можливих сценаріїв застосування:
Тип 1: Часових обмежень немає, тобто алгоритм виконується, доки не знайде розв’язок. Тип 2: Існує граничний час tmax для знаходження розв’язку. Тип 3: Корисність розв’язку визначається часом, необхідним для його знаходження.
(Тип 1 і Тип 2 є окремими випадками Типу 3.)
Для Типу 1, де немає обмеження часу, середній час роботи може характеризувати поведінку алгоритму. Це не стосується Типу 2.
У цьому випадку P(RT ≤ tmax), тобто ймовірність знайти розв’язок у межах часу tmax, описує поведінку часу роботи.
У випадку Типу 3 його поведінку щодо часу виконання можна описати лише функцією розподілу часу роботи rtd: R → [0,1], визначеною як:
rtd(t) = P(RT ≤ t),або її наближенням.
Розподіл часу роботи (RTD) є характерним способом опису поведінки алгоритму Лас-Вегаса щодо часу роботи.
На основі цих даних легко отримати інші критерії, такі як середній час роботи, стандартне відхилення, медіана, перцентили або ймовірності успіху P(RT ≤ t) для довільних часових меж t.
Застосування
Аналогія Алгоритми Лас-Вегаса часто виникають у задачах пошуку. Наприклад, людина, яка шукає певну інформацію в інтернеті, може переходити за пов’язаними посиланнями, щоб знайти потрібні відомості. Часова складність у такому випадку може коливатися від «вдалого» швидкого знаходження інформації до «невдалого» довготривалого пошуку. Щойно потрібний сайт знайдено — помилок бути не може.
Рандомізований Quicksort
Нижче наведено приклад рандомізованого quicksort, де опорний елемент обирається випадково.
INPUT:
// A — масив з n елементів def randomized_quicksort(A): if n == 1: return A // A відсортовано. else: i = random.randrange(1, n) // Вибирає випадкове число в діапазоні 1~n X = A[i] // Елемент-опорний (pivot)
"""Розділити A на елементи < X, X і > X # як показано на рисунку вище Виконати Quicksort на A[1 до i-1] та A[i+1 до n] Об'єднати результати, щоб отримати відсортований масив"""
Простим прикладом є рандомізований quicksort, у якому опорний елемент обирається випадково та масив ділиться на три частини: елементи менші за опорний, рівні йому та більші за нього. QuickSort завжди повертає коректно відсортований масив. Проте часова складність не є очевидною: вона залежить від того, який елемент випадково обрано як опорний.
Найгірший випадок — Θ(n²), коли опорний елемент є найменшим або найбільшим у масиві. T(n) = T(0) + T(n − 1) + Θ(n) T(n) = Θ(1) + T(n − 1) + Θ(n) T(n) = T(n − 1) + Θ(n) T(n) = Θ(n²)
Однак завдяки рандомізації, коли опорний елемент вибирається випадково і кожного разу є приблизно серединним значенням, алгоритм QuickSort може працювати за Θ(n log n). T(n) ≤ 2 * T(n / 2) + Θ(n) T(n) = Θ(n log n)
Час виконання quicksort сильно залежить від того, наскільки вдало обрано опорний елемент. Якщо значення опорного елемента надто велике або надто мале, розбиття буде незбалансованим, що призведе до низької ефективності. Якщо ж опорний елемент близький до середини масиву, поділ буде більш-менш збалансованим, що дає швидше виконання. Оскільки опорний елемент обирається випадково, час виконання зазвичай хороший, хоча інколи може бути поганим.
У випадку середнього часу виконання його важко визначити, оскільки аналіз залежить не від вхідних даних, а від випадкових рішень алгоритму при виборі опорного елемента. Середній час quicksort обчислюється на основі всіх можливих випадкових виборів опорного елемента.
Хоча найгірший час виконання дорівнює Θ(n²), середній — Θ(n log n). Виявляється, що найгірший випадок трапляється нечасто. Для великих значень n час виконання з високою ймовірністю дорівнює Θ(n log n).
Зверніть увагу, що ймовірність того, що опорний елемент завжди буде саме середнім, становить 1 / n, що є дуже рідкісним випадком. Однак час виконання все одно буде таким самим, якщо поділ становитиме 10%–90% замість 50%–50%, тому що глибина дерева рекурсії все ще буде O(log n), з O(n) операцій на кожному рівні.
Рандомізований жадібний алгоритм для задачі про вісім ферзів
Задача про вісім ферзів зазвичай розв’язується за допомогою алгоритму пошуку з поверненням. Однак можна застосувати алгоритм типу Лас-Вегас, який фактично є ефективнішим, ніж пошук з поверненням. Розмістіть 8 ферзів на шахівниці так, щоб жоден із них не атакував іншого. Пам'ятайте, що ферзь атакує інші фігури на тій же горизонталі, вертикалі та діагоналях.
Припустимо, що k рядків, 0 ≤ k ≤ 8, успішно зайняті ферзями.
Якщо k = 8, алгоритм завершується успіхом. Інакше перейдіть до розміщення ферзя в рядку k + 1.
Обчисліть усі позиції в цьому рядку, які не атакуються вже розміщеними ферзями. Якщо таких позицій немає — алгоритм завершується невдачею. Якщо ж є хоча б одна позиція, оберіть одну випадковим чином, збільшіть k і повторіть.
Зверніть увагу, що алгоритм просто завершується невдачею, якщо ферзя не можна розмістити. Проте процес можна повторювати, і кожного разу він може генерувати інше розташування.
Клас складності Клас складності задач вибору, які мають алгоритми Лас-Вегаса з очікуваним поліноміальним часом виконання, називається ZPP.
Виявляється, що ZPP = RP ∩ co-RP
що тісно пов’язано зі способом побудови алгоритмів Лас-Вегаса. А саме, клас RP складається зі всіх задач прийняття рішень, для яких існує рандомізований поліноміальний алгоритм, що завжди дає правильну відповідь, коли правильна відповідь — «ні», але може помилятися з певною ймовірністю, обмеженою від 1, коли відповідь — «так». Коли такі алгоритми існують для задачі та її доповнення (з відповідями «так» і «ні», поміняними місцями), два алгоритми можна запускати одночасно й повторювано: кожен запускається деяку сталу кількість кроків, по черзі, доки один із них не поверне остаточної відповіді. Це стандартний спосіб побудови алгоритму Лас-Вегаса, що працює у сподіваному поліноміальному часі. Слід зазначити, що загалом не існує верхньої межі найгіршого часу виконання алгоритму Лас-Вегаса.
Оптимальний алгоритм Лас-Вегаса Щоб зробити алгоритм Лас-Вегаса оптимальним, потрібно мінімізувати очікуваний час виконання. Це можна зробити так:
Алгоритм Лас-Вегаса A(x) запускається повторно протягом деякої кількості кроків t₁. Якщо A(x) зупиняється під час виконання, тоді A(x) завершено; інакше процес повторюється з початку ще на t₂ кроків, і так далі. Розробка стратегії, що є оптимальною серед усіх стратегій для A(x), маючи повну інформацію про розподіл TA(x).
Існування оптимальної стратегії може бути захопливим теоретичним спостереженням. Однак це непрактично в реальному житті, оскільки знайти інформацію про розподіл TA(x) нелегко. Крім того, немає сенсу повторно запускати експеримент, щоб отримати інформацію про розподіл, оскільки здебільшого відповідь потрібна лише один раз для будь-якого x.
Зв'язок з алгоритмом Монте-Карло Алгоритм Лас-Вегаса можна протиставити алгоритму Монте-Карло, в якому використовувані ресурси обмежені, але результат може бути неправильний. Через використання нерівності Маркова, алгоритм Лас-Вегаса можна перетворити в алгоритм Монте-Карло через ранню зупинку і повернення випадкового результату якщо алгоритм не встиг видати відповідь. Ось таблиця, що порівнює алгоритми Лас-Вегаса та Монте-Карло:
Час виконання Коректність Алгоритм Лас-Вегаса ймовірнісний гарантована Алгоритм Монте-Карло гарантований ймовірнісна
Якщо доступний детермінований спосіб перевірки коректності, тоді можна перетворити алгоритм Монте-Карло на алгоритм Лас-Вегаса. Однак важко перетворити алгоритм Монте-Карло на алгоритм Лас-Вегаса без можливості перевіряти алгоритм. З іншого боку, змінити алгоритм Лас-Вегаса на алгоритм Монте-Карло легко. Це можна зробити, запустивши алгоритм Лас-Вегаса на певний проміжок часу, заданий параметром довіри. Якщо алгоритм знаходить розв’язок протягом цього часу — це успіх, а якщо ні — вихід може просто бути «вибачте».
Нижче наведено приклад алгоритмів Лас-Вегаса та Монте-Карло для порівняння:
Припустімо, що є масив довжини n, де n — парне число. Половина елементів масиву дорівнюють 0, а друга половина — 1. Мета — знайти індекс, який містить 1. // A — масив довжини n. n = A.length
// Алгоритм Лас-Вегаса repeat: k = RandInt(n); if A[k] == 1, return k;
// Алгоритм Монте-Карло repeat 300 times: k = RandInt(n); if A[k] == 1, return k; return "Невдача";