Как получить значения 2-Sat
-
22-09-2019 - |
Вопрос
Всякий раз, когда я ищу алгоритм для 2-Sat, я получаю алгоритм формы решения проблемы:Существует ли юридический набор ценностей, удовлетворяющий всем пунктам?Однако это не позволяет мне легко найти набор удовлетворяющих логических значений.
Как я могу эффективно найти допустимый набор значений, который будет удовлетворять экземпляру 2-Sat?
Я работаю на C++ с библиотекой boost и был бы признателен за код, который можно легко интегрировать.
заранее спасибо
Решение
Если у вас есть алгоритм принятия решения для определения наличия действительного назначения для 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.
Другие советы
Существует по крайней мере один алгоритм Томаса Федера, который перечисляет все решения проблемы с двумя спутниками: http://www.springerlink.com/content/j582276p06276l12/