4501
правка
Алгоритмы локального поиска для k-КНФ: различия между версиями
Перейти к навигации
Перейти к поиску
Алгоритмы локального поиска для k-КНФ (посмотреть исходный код)
Версия от 10:46, 13 апреля 2018
, 13 апреля 2018→Основные результаты
Irina (обсуждение | вклад) |
Irina (обсуждение | вклад) |
||
| Строка 24: | Строка 24: | ||
'''end''' | '''end''' | ||
'''return''' y' | '''return''' y' | ||
Шонинг выполнил очень изящный анализ этого алгоритма. Обозначим за 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 оказывается выполнимой на нескольких присваиваниях. Отсюда следует важная лемма. | |||
Лемма 1. Пусть F – выполнимая формула, а y* – присваивание, на котором она оказывается выполнимой. Для любого присваивания y вероятность того, что присваивание, на котором формула оказывается выполнимой (и которое может быть отличным от y*), найдено алгоритмом RandomWalk(F, y), составляет не менее (1/(k - 1))d(y, y*)/p(n), где p(n) – полином от n. | |||
Взяв среднее значение по случайным начальным присваиваниям, получим следующую теорему. | |||
Теорема 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). | |||
== Применение == | |||
Результат Шонинга был улучшен в серии статей [1, 3, 9], основанных на идее из [3]. В частности, сочетание алгоритма RandomWalk с алгоритмом 2-КНФ с полиномиальным временем выполнения позволило выбирать более подходящие начальные присваивания. Дерандомизация алгоритма SCH описана в работе [2]. В работе [4] была предложена нетривиальная комбинация SCH с еще одним известным представителем семейства алгоритмов с возвратом [8], что позволило ускорить выполнение алгоритма до показателя O(1,324n). Самый быстрый известный на данный момент алгоритм представлен в [10], он основан на том же подходе, что и алгоритм из работы [4], и выполняется за время O(1,32216n). | |||
== Открытые вопросы == | |||
Задача k-КНФ остается, вероятно, самой популярной NP-полной задачей, над поиском самого быстрого алгоритма решения которой бьется множество исследователей. Улучшение его временной границы представляет собой значимую цель исследований. | |||
== Экспериментальные результаты == | |||
Исследователи искусственного интеллекта также активно изучали алгоритм КНФ, включая локальный поиск – см., например, [5]. | |||
== См. также == | |||
* [[Точные алгоритмы решения задачи о выполнимости формулы в КНФ общего вида]] | |||
* [[Случайный выбор 3-КНФ]] | |||
== Литература == | |||
1. Baumer, S., Schuler, R.: Improving a probabilistic 3-SAT algorithm by dynamic search and independent clause pairs. ECCC TR03-010, (2003) Also presented at SAT (2003) | |||
2. Dantsin, E., Goerdt, A., Hirsch, E.A., Kannan, R., Kleinberg, J., Papadimitriou, C., Raghavan, P., Schöning, U.: A deterministic (2 - 2/(k +1))n algorithm for k-SAT based on local search. Theor. Comput. Sci. 289(1), 69–83 (2002) | |||
3. Hofmeister, T., Schöning, U., Schuler, R., Watanabe, O.: Probabilistic 3-SAT algorithm further improved. Proceedings 19th Symposiumon Theoretical Aspects of Computer Science. LNCS 2285, 193–202 (2002) | |||
4. Iwama, K., Tamaki, S.: Improved upper bounds for 3-SA T. In: Proceedings 15th Annual ACM-SIAM Symposium on Discrete Algorithms, pp. 321–322. New Orleans, USA (2004) | |||
5. Kautz, H., Selman, B.: Ten Challenges Redux: Recent Progress in Propositional Reasoning and Search. Proceedings 9th International Conference on Principles and Practice of Constraint Programming, pp. 1–18. Kinsale, Ireland (2003) | |||
6. Monien, B., Speckenmeyer, E.: Solving satisfiability in less than 2n steps. Discret. Appl.Math. 10, 287–295 (1985) | |||
7. Papadimitriou, C.H.: On selecting a satisfying truth assignment. Proceedings 32nd Annual Symposium on Foundations of Computer Science, pp. 163–169. San Juan, Puerto Rico (1991) | |||
8. Paturi, R., Pudlák, P., Saks, M.E., Zane, F.: An improved exponential-time algorithm for k-SAT. Proceedings 39th Annual Symposium on Foundations of Computer Science, pp. 628–637. Palo Alto, USA (1998) Also, J. ACM52(3), 337–364 (2006) | |||
9. Rolf, D.: 3-SAT 2 RTIME(O(1.32793n)). ECCC TR03–054. (2003) | |||
10. Rolf, D.: Improved Bound for the PPSZ/Schöning-Algorithm for 3-SAT. J. Satisf. Boolean Model. Comput. 1, 111–122 (2006) | |||
11. Schöning, U.: A probabilistic algorithm for k-SAT and constraint satisfaction problems. Proceedings 40th Annual Symposium on Foundations of Computer Science, pp. 410–414. New York, USA (1999) | |||