Алгоритм Шёнинга - Версия для печати

Алгоритм Шёнинга - Версия для печати

+- Aluarium (http://aluarium.net/forum)
+-- Форум: Наука и техника (/forum-46.html)
+--- Форум: Математика (/forum-49.html)
+--- Тема: Алгоритм Шёнинга (/thread-299.html)

Страниц: 1 2

Алгоритм Шёнинга - Галл - 07-11-2012 19:55

Прочитал недавно статью 1999го года об алгоритме для проблемы поиска набора переменных, при котором данная 3-КНФ (а также вообще k-КНФ) истинна: homepages.cwi.nl/~rdewolf/schoning99.pdf
Возникли такие мысли: 1) действительно ли наиболее целесообразно делать именно 3n шагов? 2) Не сделает ли алгоритм более эффективным генерация не рандомных значений переменных, независимых от предыдущих попыток, а какой-либо более сложный подход? Например, выбор нескольких наборов значений переменных так, чтобы искомый набор (решение) был гарантированно близок по крайней мере к одному из них на расстояние Хэмминга, не превосходящее n/t, где t - некая специально подобранная константа.
Сейчас получены несколько лучшие асимптотики, чем в описанном алгоритме, но его относительная простота (и простота доказательства его асимптотики) делает поиск усовершенствований не таким сложным.

RE: Чем бы нам заняться? - Quasus - 07-11-2012 22:31

Прочитал. Осмысливаю.

RE: Чем бы нам заняться? - Quasus - 08-11-2012 21:01

Не вникая пока в выкладки (с. 411 — мне не очень понятно, какие там используются эквивалентности и пр.), могу сказать, что не понимаю, как это вообще работает. Матожидание приращения расстояния Хэмминга при одном «флипе» оценивается через $(-1)\cdot \frac 1k + 1 \cdot \frac{k-1}{k} = \frac{k-2}k > 0$ при $k \geqslant 3$ . Если мы всё равно уходим от искомого решения, зачем вообще эти 3n итераций, и почему сразу не выбирать новую точку? Какой-то фокус.

RE: Чем бы нам заняться? - Галл - 09-11-2012 22:54

(08-11-2012 21:01)Quasus писал(а): Не вникая пока в выкладки (с. 411 — мне не очень понятно, какие там используются эквивалентности и пр.), могу сказать, что не понимаю, как это вообще работает. Матожидание приращения расстояния Хэмминга при одном «флипе» оценивается через $(-1)\cdot \frac 1k + 1 \cdot \frac{k-1}{k} = \frac{k-2}k > 0$ при $k \geqslant 3$ . Если мы всё равно уходим от искомого решения, зачем вообще эти 3n итераций, и почему сразу не выбирать новую точку? Какой-то фокус.

Там получается, что вероятность прийти к решению (если конечно оно существует) за те 3n итераций не менее чем $\tfrac{1}{3}\cdot\(\tfrac{1}{k-1})^j$ , где j - расстояние Хэмминга от сгенерённого набора переменных до ответа, и этого оказывается достаточно, чтобы побить "наивный" алгоритм по производительности.

RE: Чем бы нам заняться? - Галл - 09-11-2012 23:00

Идея подобного рода алгоритмов основывается на том, что если есть способ получить ответ за одно испытание с вероятностью не менее 1/k, то если провести k таких независимых испытаний, то вероятность, что ответ не будет получен, будет всего лишь примерно 1/e. Если повторить их C*k раз, где C - соотв. константа, можно понизить вероятность неудачи ниже нужного уровня.

RE: Алгоритм Шёнинга - Quasus - 09-11-2012 23:51

Видимо, в первую очередь я не понимаю, какой «функционал стоимости» оптимизируется.

RE: Алгоритм Шёнинга - Галл - 10-11-2012 00:14

Оптимизуется зависимость времени поиска решения (в данном случае - времени, за которое алгоритм найдёт решение с вероятностью, близкой к единице) от числа переменных в КНФ при максимальном размере дизъюнкций, обозначенном через k. Понятно, что на поиск невыполненной дизъюнкции тоже будет каждый раз уходить время, но в данном случае им можно пренебречь, поскольку сложность всё равно будет экспоненциальная. Цель построения алгоритмов для задачи о выполнимости k-КНФ (k >= 3) - максимально приблизить к 1 основание степени в асимпотической оценке (возможно, существуют и субэкспоненциальные алгоритмы, или даже полиномиальные, но пока таких не удалось найти). Для задачи о выполнимости 2-КНФ существует простой полиномиальный алгоритм - O(N²).

RE: Алгоритм Шёнинга - Галл - 10-11-2012 00:17

Задача о выполнимости 3-КНФ - NP-полная задача, поэтому весьма вероятно, что полиномиального алгоритма для неё не существует.

RE: Алгоритм Шёнинга - Quasus - 10-11-2012 01:38

То есть начальное приближение — «дорого», нахождение невыполненной дизъюнкции — «дёшево» (a fortiori проверка тоже дешёвая). А «флипанье» значит дорого?

RE: Алгоритм Шёнинга - Галл - 10-11-2012 10:20

(10-11-2012 01:38)Quasus писал(а): То есть начальное приближение — «дорого», нахождение невыполненной дизъюнкции — «дёшево» (a fortiori проверка тоже дешёвая)

Сам блок из 3n итераций дёшев, так как работает за полиномиальное от n время. Но его нужно повторять экспоненциальное число раз, чтобы достичь близкой к 1 вероятности нахождения ответа. От полиномиального множителя можно избавиться, промажорировав его через $O((1+\epsilon)^n)$ , где эпсилон - положительное число, сколь угодно близкое к нулю. Сложность для 3-КНФ будет тогда выглядеть как $O((4/3+\epsilon)^n)$ .