Сравнение вероятностных алгоритмов
Подведем итоги обсуждению алгоритмов. Численные вероятностные алгоритмы всегда дают ответ, и этот ответ будет тем точнее, чем дольше они работают.
Алгоритмы Монте-Карло всегда дают ответ, но иногда ответ оказывается неправильным. Чем дольше выполняется алгоритм Монте Карло, тем выше вероятность того, что он даст правильный ответ. Повторный вызов алгоритма Монте-Карло также приводит к улучшению результата.
Алгоритмы Лас Вегаса не могут вернуть неправильного результата, но они могут и не вернуть никакого результата, если им не удалось найти правильный ответ.
Шервудскую технику можно применять к любому детермини-рованному алгоритму. Она не влияет на правильность алгоритма, а лишь уменьшает вероятность реализации наихудшего поведения. Вероятность наилучшего поведения при этом, правда, тоже понижается.
Вероятностные алгоритмы для NP-полных задач:
Рассмотрим задачу максимальная выполнимость: (MAX-SAT):
Даны m скобок КНФ – конъюктивной нормальной формы с n переменными. Найти значения переменных, максимизирующее число выполненных скобок.
Следующее утверждение дает приближенный вероятностный алгоритм решения методом Монте-Карло:
0,5 приближение: Для любых m скобок существуют значения переменных, при которых выполнено не менее m/2 скобок.
Предположим, что каждая переменная принимает значения 0 или 1 независимо и равновероятно. Пусть для , если i-тая скобка выполнена. И , в противном случае.
Для каждой дизъюнкции с k литералами (переменными или их отрицаниями), вероятность, что она не равна 1 при случайном выборе значений переменных равна . Значит вероятность того, что скобка равна 1, есть . И математическое ожидание . Отсюда математическое ожидание числа выполненных скобок (равных 1) равно . Это означает, что есть такой набор значений переменных, что выполняется .
Опр. Вероятностный (рандомизированный) приближенный алгоритм имеет коэффициент аппроксимации p(n), если:
,
n - размер входных данных;
Е(С) – математическое ожидание стоимости решения:
- стоимость оптимального решения.
Таким образом, описанный приближенный вероятностный алгоритм для задачи максимальная выполнимость дает точность 1/2.
Общая схема применения вероятностных алгоритмов:
1. Найти вероятностный алгоритм, работающий за полиномиальное время
2. Оценить вероятность успеха р.
3. Повторять исходный алгоритм раз.
4. Итоговая вероятность станет константой: .