Сравнение вероятностных алгоритмов

Подведем итоги обсуждению алгоритмов. Численные вероятностные алгоритмы всегда дают ответ, и этот ответ будет тем точнее, чем дольше они работают.

Алгоритмы Монте-Карло всегда дают ответ, но иногда ответ оказывается неправильным. Чем дольше выполняется алгоритм Монте Карло, тем выше вероятность того, что он даст правильный ответ. Повторный вызов алгоритма Монте-Карло также приводит к улучшению результата.

Алгоритмы Лас Вегаса не могут вернуть неправильного результата, но они могут и не вернуть никакого результата, если им не удалось найти правильный ответ.

Шервудскую технику можно применять к любому детермини-рованному алгоритму. Она не влияет на правильность алгоритма, а лишь уменьшает вероятность реализации наихудшего поведения. Вероятность наилучшего поведения при этом, правда, тоже понижается.

Вероятностные алгоритмы для 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. Итоговая вероятность станет константой: .

Дата добавления: 2014-01-03