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

Ответ 1

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

Ответ 2

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

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

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

Ответ 3

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

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

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

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

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

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

(Хорошо, если A подразумевает "не A" , но не наоборот. Это просто означает, что A должно быть отменено, чтобы удовлетворить выражение.)

Ответ 4

2 удовлетворительность:

если x и! x сильно связаны то от! х мы можем дойти до x от х мы можем доходить до! х

поэтому в нашей работе, в случае x, у нас есть только 2 варианта, 1. Приняв x (x), что приводит к! X 2. постановка x (! X), приводящая к x и оба выбора приводят к парадоксу принятия и отвержения выбора в то же время

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