Пример неполноты GSAT

Question

Алгоритм GSAT (Greedy Satisfiability) может быть использован для поиска решения проблемы поиска, закодированной в CNF. Я знаю, что, поскольку GSAT является жадным, он неполон (что означает, что могут быть случаи, когда решение может существовать, но GSAT не может его найти). По следующей ссылке я узнал, что это может произойти, когда переключение переменных жадно заманивает нас в такой цикл, как I → I '→ I' '→ I.

http://www.dis.uniroma1.it/~liberato/ar/incomplete/incomplete.html

Я изо всех сил пытался придумать фактический экземпляр, который может показать это, но не смог (и не смог найти примеров в другом месте). Любая помощь приветствуется. Спасибо:)

PS Я не говорю о "сложных" задачах k-SAT, в которых отношение переменных к предложениям приближается к 4.3. Я просто ищу простой пример, возможно, с наименьшим количеством необходимых переменных и / или предложений.

Answer 1

Как насчет формулы:

{x_1, x_2, -x_3}, {-x_1, x_2, -x_3}, {-x_2, -x_3}, {-x_2, -x_3}, {x_2, x_3}, {x_2, x_3}

Эта формула выполняется с помощью присваивания (0,1,0). Однако, если человек начинает с начального задания (0,0,1), он получает баллы (1,2,2) и поэтому переворачивает x_1. Затем вы попадаете на задание (1,0,1), которое снова приводит к баллам (1,2,2), и вы застряли. Тогда только перезапуск с другим начальным назначением поможет вам выйти.

Конечно, это немного построено из-за двух удвоенных предложений, но я уверен, что можно легко расширить это, чтобы получить формулу без повторяющихся предложений.

Answer 2

Возьмите небольшую неудовлетворительную формулу с n переменными и выполните GSAT для> 2^n шагов. Поскольку есть только 2 ^ n различных комбинаций, GSAT должен повториться - он не остановится, потому что формула не выполняется.

Одна маленькая неудовлетворительная формула (A V B V C) ^ (~A V B V C) ^ (A V ~B V C) ^ (~A V ~B V C) ^ (A V B V ~C) ^ (~A V B V ~C) ^ (A V ~B V ~C) ^ (~A V ~B V ~C) - все 8 комбинаций трехзначных членов.

В Кнута том 4А, раздел 7.1.1, уравнение 32 P 56 Кнут дает то, что он называет интересной формулой из 8 предложений с восемью различными переменными.