Алгоритм для задачи 2-удовлетворенности

Question

Может кто-нибудь объяснить алгоритм решения проблемы 2-удовлетворяемости или предоставить мне ссылки для этого же?Я не мог найти хорошие ссылки, чтобы понять это.

Answer 1

Если у вас n переменных и m предложений:

Создание графа с 2n вершинами: интуитивно каждая вершина напоминает литерал true или not true для каждой переменной. Для каждого предложения (a v b), где a и b являются литералами, создайте ребро от! A до b и от! B до a. Эти ребра означают, что если a не соответствует действительности, то b должно быть истинным и наоборот.

Как только этот орграф будет создан, просмотрите график и посмотрите, существует ли цикл, содержащий и a, и! A для некоторой переменной a. Если есть, то 2SAT не выполнимо (потому что a подразумевает! A и наоборот). В противном случае это выполнимо, и это может даже дать вам удовлетворительное предположение (выберите какой-нибудь литерал a, чтобы a не подразумевал! A, форсируйте все следствия оттуда, повторите). Вы можете выполнить эту часть с любым из ваших стандартных алгоритмов графа, ala Поиск в ширину , Floyd-Warshall или любым подобным алгоритмом, в зависимости от того, насколько вы чувствительны к времени сложность вашего алгоритма.

Answer 2

Вот страница Wikipedia по теме, которая описывает алгоритм полиномиального времени. (Алгоритм грубой силы, состоящий в том, чтобы просто пробовать все различные назначения правды, является экспоненциальным временем.) Может быть, немного дальнейшего объяснения поможет.

Выражение «если P, то Q» ложно, только когда P истинно, а Q ложно. Таким образом, выражение имеет те же значения таблицы истинности, что и "Q or not P". Это также эквивалентно его противозачаточному «если не Q, то не P», а это, в свою очередь, эквивалентно «не P или Q» (так же, как другой).

Таким образом, алгоритм включает замену каждого выражения формы «A или B» двумя выражениями: «если не A, то B» и «если не B, то A». (Другими словами, A и B не могут быть ложными.)

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

Последний шаг - убедиться, что ни одна из переменных не эквивалентна своему отрицанию. То есть для каждой переменной A (или не A) перейдите по ссылкам, чтобы обнаружить все узлы, к которым можно получить доступ из нее, стараясь обнаружить петли.

Если одна из переменных, A, может достигать «не A», а «не A» также может достигать A, то исходное выражение не выполнимо. (Это парадокс.) Если ни одна из переменных не делает этого, то она выполнима.

(Это нормально, если А подразумевает «не А», но не наоборот. Это просто означает, что А должен быть отрицан, чтобы удовлетворить выражению.)

Answer 3

Вы можете решить это с жадным подходом. Или с помощью теории графов, вот ссылка, которая объясняет решение с помощью теории графов. http://www.cs.tau.ac.il/~safra/Complexity/2SAT.ppt

Answer 4

2 удовлетворяет:

, если x &! X сильно связан тогда из! х мы можем добраться до х от х мы можем добраться до! х

так в нашей работе, в случае х, у нас есть только 2 варианта, 1. взяв х (х), что приводит к! Х 2. отвергая x (! X), что приводит к x и оба выбора приводят к парадоксу принятия и отклонения выбора одновременно

так что выполнимость невозможна: D