Алгоритмы локального поиска для k-КНФ: различия между версиями

Перейти к навигации Перейти к поиску
м
Строка 26: Строка 26:




Шонинг выполнил очень изящный анализ этого алгоритма. Обозначим за d(a, b) [[Hamming distance|расстояние Хэмминга]] между двумя бинарными векторами (присваиваниями) a и b. Для простоты будем считать, что формула F оказывается выполнимой только на одном присваивании y* и что текущее присваивание y находится от y* на расстоянии Хэмминга d. Предположим также, что ложный в настоящий момент дизъюнкт C включает три переменные – xi, xj и xk. Тогда y и y* должны различаться по меньшей мере в одной из этих переменных. Это значит, что если поменять значение xi, xj или xk на противоположное, то новое присваивание будет ближе к y* согласно расстоянию Хэмминга с вероятностью не ниже 1/3 – и дальше от него с вероятностью не более 2/3. Это рассуждение можно распространить на случай, когда формула F оказывается выполнимой на нескольких присваиваниях. Отсюда следует важная лемма.
Шонинг выполнил очень изящный анализ этого алгоритма. Обозначим за d(a, b) [[Hamming distance|расстояние Хэмминга]] между двумя бинарными векторами (присваиваниями) a и b. Для простоты будем считать, что формула F оказывается выполнимой только на одном присваивании y* и что текущее присваивание y находится от y* на расстоянии Хэмминга d. Предположим также, что ложный в настоящий момент дизъюнкт C включает три переменные – <math>x_i, x_j \;</math> и <math>x_k \;</math>. Тогда y и y* должны различаться по меньшей мере в одной из этих переменных. Это значит, что если поменять значение <math>x_i, x_j \;</math> или <math>x_k \;</math> на противоположное, то новое присваивание будет ближе к y* согласно расстоянию Хэмминга с вероятностью не ниже 1/3 – и дальше от него с вероятностью не более 2/3. Это рассуждение можно распространить на случай, когда формула F оказывается выполнимой на нескольких присваиваниях. Отсюда следует важная лемма.




Лемма 1. Пусть F – выполнимая формула, а y* – присваивание, на котором она оказывается выполнимой. Для любого присваивания y вероятность того, что присваивание, на котором формула оказывается выполнимой (и которое может быть отличным от y*), найдено алгоритмом RandomWalk(F, y), составляет не менее (1/(k - 1))d(y, y*)/p(n), где p(n) – полином от n.
'''Лемма 1'''. Пусть F – выполнимая формула, а y* – присваивание, на котором она оказывается выполнимой. Для любого присваивания y вероятность того, что присваивание, на котором формула оказывается выполнимой (и которое может быть отличным от y*), найдено алгоритмом '''RandomWalk'''(F, y), составляет не менее <math>(1/(k - 1))^{d(y, y*)}/p(n) \;</math>, где p(n) – полином от n.




Строка 35: Строка 35:




Теорема 2. Для любой выполнимой формулы F с n переменными вероятность успеха алгоритма RandomWalk(F, y) составляет не менее (k/2(k - 1))n /p(n) для некоторого полиномиального p. Таким образом, положив I = (2(k - 1)/k)n _ p(n), алгоритм SCH с высокой вероятностью находит присваивание, на котором формула выполняется. При k = 3 значение I составляет O(1,334n).
Теорема 2. Для любой выполнимой формулы F с n переменными вероятность успеха алгоритма '''RandomWalk'''(F, y) составляет не менее <math>(k/2(k - 1))^n /p(n) ';</math> для некоторого полиномиального p. Таким образом, положив <math>I = (2(k - 1)/k)^n \cdot p(n) \;</math>, алгоритм '''SCH''' с высокой вероятностью находит присваивание, на котором формула выполняется. При k = 3 значение I составляет <math>O(1,334^n) \;</math>.


== Применение ==
== Применение ==
4501

правка

Навигация