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

В вычислениях алгоритм Лас-Вегаса — это рандомизированный алгоритм , который всегда дает правильные результаты; то есть он всегда выдает правильный результат или сообщает о сбое. Однако время выполнения алгоритма Лас-Вегаса различается в зависимости от входных данных. Обычное определение алгоритма Лас-Вегаса включает ограничение, согласно которому ожидаемое время выполнения должно быть конечным, при этом ожидание осуществляется в пространстве случайной информации или энтропии, используемой в алгоритме. Альтернативное определение требует, чтобы алгоритм Лас-Вегаса всегда завершался (эффективен ) , но мог выводить символ, не являющийся частью пространства решений , чтобы указать на неудачу в поиске решения. ^[1] Характер алгоритмов Лас-Вегаса делает их подходящими в ситуациях, когда количество возможных решений ограничено и где проверить правильность возможного решения относительно легко, а найти решение сложно.

Методы систематического поиска для вычислительно сложных задач, такие как некоторые варианты алгоритма Дэвиса-Патнэма для пропозициональной выполнимости (SAT), также используют недетерминированные решения и, таким образом, также могут считаться алгоритмами Лас-Вегаса. ^[2]

История [ править ]

Алгоритмы Лас-Вегаса были представлены Ласло Бабаем в 1979 году в контексте проблемы изоморфизма графов как двойственные алгоритмам Монте-Карло . ^[3] отец ^[4] ввел термин «алгоритм Лас-Вегаса» рядом с примером, связанным с подбрасыванием монеты: алгоритм зависит от серии независимых подбрасываний монеты, и существует небольшая вероятность неудачи (без результата). Однако, в отличие от алгоритмов Монте-Карло, алгоритм Лас-Вегаса может гарантировать правильность любого сообщаемого результата.

Пример [ править ]

// Las Vegas algorithm
repeat:
    k = RandInt(n)
    if A[k] == 1,
        return k;

Как упоминалось выше, алгоритмы Лас-Вегаса всегда возвращают правильные результаты. Код выше иллюстрирует это свойство. Переменная k генерируется случайным образом; после того, как сгенерирован , k используется для индексации массива A. k Если этот индекс содержит значение 1, то k возвращается ; в противном случае алгоритм повторяет этот процесс, пока не найдет 1. Хотя этот алгоритм Лас-Вегаса гарантированно найдет правильный ответ, он не имеет фиксированного времени выполнения; из-за рандомизации (в строке 3 приведенного выше кода) до завершения алгоритма может пройти сколь угодно много времени.

Определение [ править ]

В этом разделе представлены условия, характеризующие алгоритм типа Лас-Вегаса.

Алгоритм A называется алгоритмом Лас-Вегаса для класса задач X, если ^[5]

всякий раз, когда для данного экземпляра задачи xεX он возвращает решение s, s гарантированно является допустимым решением x
для каждого данного экземпляра x время выполнения A является случайной величиной RT _A,x

Существует три понятия полноты алгоритмов Лас-Вегаса:

Полные алгоритмы Лас-Вегаса могут гарантировать решение каждой разрешимой проблемы за время выполнения t max, где t max — константа, зависящая от экземпляра.

Пусть P(RT _A,x ≤ t) обозначает вероятность того, что A найдет решение для разрешимого экземпляра x за время в пределах t, тогда A является полным в точности, если для каждого x существует

некоторый t max такой, что P(RT _A,x ≤ t _max ) = 1.

приблизительно полные алгоритмы Лас-Вегаса решают каждую задачу с вероятностью, стремящейся к 1 по мере того, как время выполнения приближается к бесконечности. Таким образом, A является приближенно полным, если для каждого экземпляра x lim _t→∞ P(RT _A,x ≤ t) = 1.
существенно неполные алгоритмы Лас-Вегаса — это алгоритмы Лас-Вегаса, которые не являются приблизительно полными.

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

Сценарии применения [ править ]

Алгоритмы Лас-Вегаса имеют разные критерии оценки в зависимости от постановки задачи. Эти критерии разделены на три категории с разными ограничениями по времени, поскольку алгоритмы Лас-Вегаса не имеют заданной временной сложности. Вот несколько возможных сценариев применения:

Тип 1: ограничения по времени отсутствуют, что означает, что алгоритм работает до тех пор, пока не найдет решение.
Тип 2: существует ограничение по времени t _max для определения результата.
Тип 3: Полезность решения определяется временем, необходимым для его поиска.

(Тип 1 и Тип 2 являются частными случаями Типа 3.)

Для типа 1, где нет ограничений по времени, среднее время выполнения может отражать поведение во время выполнения. Это не то же самое для типа 2.

Здесь P ( RT ≤ t _max ), который представляет собой вероятность нахождения решения за время, описывает его поведение во время выполнения.

В случае типа 3 его поведение во время выполнения может быть представлено только функцией распределения времени выполнения rtd : R → [0,1], определенной как rtd ( t ) = P ( RT ≤ t ) или ее приближением.

Распределение во время выполнения (RTD) — это особый способ описания поведения алгоритма Лас-Вегаса во время выполнения.

С помощью этих данных мы можем легко получить другие критерии, такие как среднее время выполнения, стандартное отклонение, медиана, процентили или вероятности успеха P ( RT ≤ t ) для произвольных временных ограничений t .

Приложения [ править ]

Аналогия [ править ]

Алгоритмы Лас-Вегаса часто возникают в задачах поиска . Например, тот, кто ищет какую-то информацию в Интернете, может искать нужную информацию на соответствующих веб-сайтах. Таким образом, временная сложность варьируется от «повезения» и немедленного нахождения контента до «невезения» и траты большого количества времени. Как только правильный веб-сайт найден, вероятность ошибки исключена. ^[6]

быстрая Рандомизированная сортировка

INPUT: 
    # A is an array of n elements
def randomized_quicksort(A):
    if n == 1:
        return A  # A is sorted.
    else:
        i = random.randrange(1, n)  # Will take a random number in the range 1~n
        X = A[i]  # The pivot element
    """Partition A into elements < x, x, and >x  # as shown in the figure above.
    Execute Quicksort on A[1 to i-1] and A[i+1 to n].
    Combine the responses in order to obtain a sorted array."""

Простым примером является рандомизированная быстрая сортировка , где ось выбирается случайным образом и делит элементы на три части: элементы меньше, чем стержень, элементы, равные стержню, и элементы больше, чем стержень. Рандомизированная быстрая сортировка требует много ресурсов, но на выходе всегда генерирует отсортированный массив. ^[7]

Очевидно, что QuickSort всегда генерирует решение, которым в данном случае является отсортированный массив. К сожалению, временная сложность не так очевидна. Оказывается, время выполнения зависит от того, какой элемент мы выберем в качестве опорного.

Худший случай Θ( n ²), когда точка поворота является самым маленьким или самым большим элементом.

T(n)=T(0)+T(n-1)+\Theta (n)

T(n)=\Theta (1)+T(n-1)+\Theta (n)

T(n)=T(n-1)+\Theta (n)

T(n)=\Theta (n^{2})

Однако благодаря рандомизации, когда ось выбирается случайным образом и каждый раз соответствует ровно среднему значению, быструю сортировку можно выполнить за Θ( n log n ).

T(n)\leq 2*T(n/2)+\Theta (n)

T(n)=\Theta (n\log(n))

Время выполнения быстрой сортировки во многом зависит от того, насколько хорошо выбрана опорная точка. Если значение Pivot слишком велико или мало, раздел будет несбалансированным, что приведет к низкой эффективности выполнения. Однако если значение Pivot находится рядом с серединой массива, то разделение будет достаточно хорошо сбалансированным, что приведет к более быстрому выполнению. Поскольку опорная точка выбирается случайным образом, время работы большую часть времени будет хорошим, а иногда и плохим.

В случае среднего случая определить это сложно, поскольку анализ зависит не от входного распределения, а от случайного выбора, который делает алгоритм. Среднее значение быстрой сортировки вычисляется по всем возможным случайным выборам, которые алгоритм может сделать при выборе опорной точки.

Хотя наихудшее время выполнения — Θ( n ²), среднее время выполнения равно Θ( n log n ). Оказывается, худший вариант случается нечасто. Для больших значений n время выполнения равно Θ( n log n с высокой вероятностью ).

Обратите внимание, что вероятность того, что опорный элемент каждый раз является элементом среднего значения, равна одному из n чисел, что встречается очень редко. Однако время выполнения остается тем же, когда разделение составляет 10%-90% вместо 50%-50%, поскольку глубина дерева рекурсии по-прежнему будет равна O (log n ), причем O ( n на каждом уровне будет взято ) раз. рекурсия.

задачи восьми Рандомизированный жадный алгоритм для ферзей

Задача восьми ферзей обычно решается с помощью алгоритма возврата. Однако можно применить алгоритм Лас-Вегаса; на самом деле это более эффективно, чем возврат.

Разместите на шахматной доске 8 ферзей так, чтобы никто не атаковал другого. Помните, что ферзь атакует другие фигуры на той же строке, столбце и диагонали.

Предположим, что k строк, 0 ≤ k ≤ 8, успешно заняты ферзями.

Если k = 8, то остановка успешно. В противном случае перейдите к занятию строки k + 1.

Подсчитайте все позиции в этом ряду, не атакованные существующими ферзями. Если их нет, то провал. В противном случае выберите один наугад, увеличьте k и повторите.

Обратите внимание, что алгоритм просто терпит неудачу, если невозможно поставить ферзя. Но процесс можно повторить, и каждый раз будет создаваться другое расположение. ^[8]

Класс сложности [ править ]

Класс сложности задач решения , в которых используются алгоритмы Лас-Вегаса с ожидаемым полиномиальным временем выполнения, — ZPP .

Оказывается,

{\textsf {ZPP}}={\textsf {RP}}\cap {\textsf {co-RP}}

что тесно связано с тем, как иногда строятся алгоритмы Лас-Вегаса. А именно, класс RP состоит из всех задач решения, для которых существует рандомизированный алгоритм с полиномиальным временем, который всегда дает правильный ответ, когда правильный ответ «нет», но допускает ошибку с определенной вероятностью, отделенной от единицы, когда ответ «нет». да". Когда такой алгоритм существует как для задачи, так и для ее дополнения (с поменянными местами ответами «да» и «нет»), два алгоритма можно запускать одновременно и неоднократно: запускать каждый на постоянное число шагов по очереди, пока не из них дает окончательный ответ. Это стандартный способ построения алгоритма Лас-Вегаса, работающего за ожидаемое полиномиальное время. Обратите внимание, что в общем случае не существует верхней границы времени выполнения алгоритма Лас-Вегаса для наихудшего случая.

алгоритм Лас Оптимальный - Вегаса

Чтобы сделать алгоритм Лас-Вегаса оптимальным, ожидаемое время выполнения должно быть минимизировано. Это можно сделать следующим образом:

Алгоритм Лас-Вегаса A ( x ) выполняется неоднократно для некоторого количества шагов t ₁ . Если A ( x ) останавливается во время выполнения, то A ( x ) завершается; в противном случае повторите процесс с начала еще t ₂ шагов и так далее.
Разработка стратегии, оптимальной среди всех стратегий для ( x ) , учитывая полную информацию о распределении TA ₍ x A ).

Существование оптимальной стратегии может стать интересным теоретическим наблюдением. ) непросто в реальной жизни это непрактично, поскольку найти информацию о распределении TA _Однако ( x . Более того, нет смысла проводить эксперимент повторно, чтобы получить информацию о распределении, поскольку в большинстве случаев ответ необходим только один раз для любого x . ^[9]

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

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

Вот таблица, сравнивающая алгоритмы Лас-Вегаса и Монте-Карло: ^[10]

	Время работы	Корректность
Алгоритм Лас-Вегаса	вероятностный	определенный
Алгоритм Монте-Карло	определенный	вероятностный

Если доступен детерминированный способ проверки правильности, то можно превратить алгоритм Монте-Карло в алгоритм Лас-Вегаса. Однако трудно преобразовать алгоритм Монте-Карло в алгоритм Лас-Вегаса, не имея возможности протестировать этот алгоритм. С другой стороны, заменить алгоритм Лас-Вегаса на алгоритм Монте-Карло легко. Это можно сделать, запустив алгоритм Лас-Вегаса в течение определенного периода времени, заданного параметром достоверности. Если алгоритм находит решение в течение времени, то это успех, а если нет, то на выходе может быть просто «извините».

Это пример алгоритмов Лас-Вегаса и Монте-Карло для сравнения: ^[11]

Предположим, что существует массив длиной четного n . Половина элементов массива равна 0, а оставшаяся половина — 1. Цель здесь — найти индекс, содержащий 1.

// Las Vegas algorithm
repeat:
    k = RandInt(n)
    if A[k] == 1,
        return k;
        
// Monte Carlo algorithm
repeat 300 times:
    k = RandInt(n)
    if A[k] == 1
        return k
    return "Failed"

Поскольку Лас-Вегас не заканчивается, пока не найдет 1 в массиве, он делает ставку не на корректность, а на время выполнения. С другой стороны, метод Монте-Карло выполняется 300 раз, а это означает, что невозможно знать, что Монте-Карло найдет «1» в массиве за 300 циклов, пока он фактически не выполнит код. Возможно, оно найдет решение или нет. Поэтому, в отличие от Лас-Вегаса, Монте-Карло делает ставку не на время выполнения, а на корректность.

См. также [ править ]

Ссылки [ править ]

Цитаты [ править ]

^ Стивен Д. Гэлбрейт (2012). Математика криптографии с открытым ключом . Издательство Кембриджского университета. п. 16. ISBN 978-1-107-01392-6 .
^ Хоос, Хольгер Х.. «Об эмпирической оценке алгоритмов Лас-Вегаса — позиционный документ». (1998).
^
* Ласло Бабай , Алгоритмы Монте-Карло для проверки изоморфизма графов , Университет Монреаля, DMS No. 79-10.
- Леонид Левин , Сказка об односторонних функциях , Проблемы передачи информации , вып. 39 (2003), 92-103.
- Дэн Гранди, «Концепции и вычисления в криптографии», архивировано 12 апреля 2016 г. в Wayback Machine , Кентский университет, доктор философии. диссертация, 2008 г.
^ Бабай, Ласло. «Алгоритмы Монте-Карло при проверке изоморфизма графов». (1979).
^ Х. Х. Хоос и Т. Штютцле. Оценка алгоритмов Лас-Вегаса — подводные камни и способы их устранения. В материалах четырнадцатой конференции по неопределенности в искусственном интеллекте (UAI-98), страницы 238–245. Издательство Morgan Kaufmann, Сан-Франциско, Калифорния, 1998 г.
^ Рандомизированные алгоритмы. Бриллиант.орг . Получено 23:54, 24 октября 2018 г., с https://brilliant.org/wiki/randomized-algorithms-overview/.
^ «От Лас-Вегаса до Монте-Карло: рандомизированные алгоритмы в системах машинного обучения» . На пути к науке о данных . 07.09.2018 . Проверено 25 октября 2018 г.
^ Бэрринджер, Ховард (декабрь 2010 г.). «Рандомизированные алгоритмы. Краткое введение» (PDF) . www.cs.man.ac.uk. Проверено 8 декабря 2018 г.
^ Луби, Майкл (27 сентября 1993 г.). «Оптимальное ускорение алгоритмов Лас-Вегаса». Письма об обработке информации . 47 (4): 173–180. дои : 10.1016/0020-0190(93)90029-9 .
^ Гудрич, Майкл. Разработка и применение алгоритмов: рандомизированные алгоритмы. Уайли, 2015 г. , https://nscpolteksby.ac.id/ebook/files/Ebook/Computer%20Engineering/Algorithm%20Design%20and%20Applications%20A4%20(2015)/20.%20Chapter%2019%20-%20Randomized %20Алгоритмы.pdf . 23 октября 2018 г.
^ Прокачча, Ариэль (5 ноября 2015 г.). «Великие теоретические идеи в информатике» (PDF) . www.cs.cmu.edu ( PowerPoint ) . Проверено 3 ноября 2018 г.

Источники [ править ]

Справочник по алгоритмам и теории вычислений , ООО «CRC Press», 1999.
«Алгоритм Лас-Вегаса», в Словаре алгоритмов и структур данных [онлайн], Пол Э. Блэк, изд., Национальный институт стандартов и технологий США . 17 июля 2006 г. (по состоянию на 9 мая 2009 г.). Доступно по адресу: [1]

[Galbraith201222-1] Стивен Д. Гэлбрейт (2012). Математика криптографии с открытым ключом . Издательство Кембриджского университета. п. 16. ISBN 978-1-107-01392-6 .

[2] Хоос, Хольгер Х.. «Об эмпирической оценке алгоритмов Лас-Вегаса — позиционный документ». (1998).

[3] * Ласло Бабай , Алгоритмы Монте-Карло для проверки изоморфизма графов , Университет Монреаля, DMS No. 79-10.
Леонид Левин , Сказка об односторонних функциях , Проблемы передачи информации , вып. 39 (2003), 92-103.

Дэн Гранди, «Концепции и вычисления в криптографии», архивировано 12 апреля 2016 г. в Wayback Machine , Кентский университет, доктор философии. диссертация, 2008 г.

[4] Леонид Левин , Сказка об односторонних функциях , Проблемы передачи информации , вып. 39 (2003), 92-103.

[5] Дэн Гранди, «Концепции и вычисления в криптографии», архивировано 12 апреля 2016 г. в Wayback Machine , Кентский университет, доктор философии. диссертация, 2008 г.

[4] Бабай, Ласло. «Алгоритмы Монте-Карло при проверке изоморфизма графов». (1979).

[5] Х. Х. Хоос и Т. Штютцле. Оценка алгоритмов Лас-Вегаса — подводные камни и способы их устранения. В материалах четырнадцатой конференции по неопределенности в искусственном интеллекте (UAI-98), страницы 238–245. Издательство Morgan Kaufmann, Сан-Франциско, Калифорния, 1998 г.

[6] Рандомизированные алгоритмы. Бриллиант.орг . Получено 23:54, 24 октября 2018 г., с https://brilliant.org/wiki/randomized-algorithms-overview/.

[7] «От Лас-Вегаса до Монте-Карло: рандомизированные алгоритмы в системах машинного обучения» . На пути к науке о данных . 07.09.2018 . Проверено 25 октября 2018 г.

[8] Бэрринджер, Ховард (декабрь 2010 г.). «Рандомизированные алгоритмы. Краткое введение» (PDF) . www.cs.man.ac.uk. Проверено 8 декабря 2018 г.

[9] Луби, Майкл (27 сентября 1993 г.). «Оптимальное ускорение алгоритмов Лас-Вегаса». Письма об обработке информации . 47 (4): 173–180. дои : 10.1016/0020-0190(93)90029-9 .

[10] Гудрич, Майкл. Разработка и применение алгоритмов: рандомизированные алгоритмы. Уайли, 2015 г. , https://nscpolteksby.ac.id/ebook/files/Ebook/Computer%20Engineering/Algorithm%20Design%20and%20Applications%20A4%20(2015)/20.%20Chapter%2019%20-%20Randomized %20Алгоритмы.pdf . 23 октября 2018 г.

[11] Прокачча, Ариэль (5 ноября 2015 г.). «Великие теоретические идеи в информатике» (PDF) . www.cs.cmu.edu ( PowerPoint ) . Проверено 3 ноября 2018 г.

[1]

[2]

[3]

[4]

[5]

[6]

[7]

[8]

[9]

[10]

[11]