Как получить значения 2-Sat

Question

Всякий раз, когда я ищу алгоритм для 2-Sat, я получаю алгоритм формы решения проблемы:Существует ли юридический набор ценностей, удовлетворяющий всем пунктам?Однако это не позволяет мне легко найти набор удовлетворяющих логических значений.

Как я могу эффективно найти допустимый набор значений, который будет удовлетворять экземпляру 2-Sat?

Я работаю на C++ с библиотекой boost и был бы признателен за код, который можно легко интегрировать.

заранее спасибо

Answer 1

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

Сначала запустите алгоритм принятия решения 2-SAT для всего выражения.Предположим, он говорит, что существует допустимое назначение.

Теперь, если x_1 является литералом, присвойте x_1 значение 0.Теперь вычислите 2-SAT для полученного выражения (из-за этого вам придется назначить некоторые другие литералы, например, если появляется x_1 ИЛИ x_3, вам также необходимо установить x_3 равным 1).

Если полученное выражение является 2-выполнимым, то вы можете принять x_1 равным 0, в противном случае принять x_1 равным 1.

Теперь вы можете узнать это о каждом литерале.

Для более эффективного алгоритма я бы предложил вам попробовать использовать подход графа импликации.

Дополнительную информацию можно найти здесь: http://en.wikipedia.org/wiki/2-satisfiability

Соответствующая часть:

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

Литералы в каждом сильно связном компоненте либо все равны нулю, либо все равны 1.

Answer 2

Существует по крайней мере один алгоритм Томаса Федера, который перечисляет все решения проблемы с двумя спутниками: http://www.springerlink.com/content/j582276p06276l12/