Когда использовать SAT vs Ограничение удовлетворенности?

18

Если у меня возникла сложная проблема, один из стандартных подходов состоит в том, чтобы выразить его как экземпляр SAT и попробовать запустить на нем решатель SAT. Другой стандартный подход состоит в том, чтобы выразить это как проблему удовлетворения ограничений и попытаться использовать решатель CSP. Эти два понятия как-то смутно схожи в том, какие проблемы могут быть естественным образом выражены в их формате ввода.

Существуют ли какие-либо руководящие принципы или практические правила о том, как распознать для данной проблемы, какой подход с большей вероятностью даст хорошие результаты? Есть ли какое-либо руководство, которое кто-либо может предложить о том, какие виды проблем могут быть решены лучше решателями SAT, чем решателями CSP, или наоборот?

(Очевидно, что есть несколько простых проблем, которые могут быть решены с помощью обоих подходов. Есть также некоторые сложные проблемы, которые не могут быть эффективно решены ни одним из подходов. Давайте отложим их в сторону. В случае, когда руководство является наиболее полезным, это проблемы, когда любой SAT решатели работают лучше, чем решатели CSP, или где решатели CSP работают лучше, чем решатели SAT. Как определить, что решатель SAT лучше подходит, чем решатель CSP, или когда решатель CSP может быть лучше SAT решатель - то есть, какой подход попробовать в первую очередь?)

heuristics sat-solvers constraint-programming DW
источник
1
Обратите внимание, что проблема не может быть слишком сложной, если вы хотите сократить SAT.
Рафаэль
1
Или почему бы сосредоточиться только на SAT / CSP, а как насчет SMT?
Юхо
Преимущество использования инструмента для определения ограничений заключается в том, что вы можете легко попробовать некоторые оптимизации (например, методы нарушения симметрии) в случаях, которые не являются слишком сложными (и проверить эффективность таких оптимизаций). Кроме того, многие из них могут выводить стандартный файл CNF в качестве промежуточного вывода.
Вор
Замечательно, @Juho! Стоит рассмотреть и SMT - не стесняйтесь сравнивать все три (SAT, CSP, SMT), если у вас есть какие-либо мысли по этому поводу.
DW
У меня был тот же вопрос, спасибо за вопрос.
ххх ---

Ответы:

8

Я думаю, что это очень хороший вопрос. Вы также можете спросить: когда использовать SMT решатель? У меня есть ощущение, что это может быть трудно определить до моделирования проблемы и фактического запуска решателей CSP / SAT / SMT и выяснения. Хорошо известно, что даже разные решатели работают совершенно по-разному в одних и тех же случаях! Моя интуиция также исходит из того факта, что существует множество способов моделирования проблемы. Кроме того, существует много способов поиска и вывода, в зависимости от того, какой тип ограничений используется (если рассматриваемый формализм допускает разные типы).

8×89+9+9знак равно2732×32 Головоломки судоку, SAT решатели будут быстрее, чем CSP решатели.

Различные формализмы могут собирать информацию о предметной области и использовать ее лучше и по-разному. Подробнее об этом см. Ответ и комментарии здесь .

Юхо
источник