Изменения

Перейти к: навигация, поиск

2SAT

3900 байт добавлено, 16 сентябрь
Нет описания правки
Рассмотрим функцию, записанную в виде 2-КНФ (КНФ Крома). {{ОпределениеЗадача|definition =<b><tex>\mathrm {2SAT}</tex></b> (2-SAT satisfiability) выполнимость данной функции — эта задача распределения аргументов в булевой [[КНФ|КНФ]] функции, записанной в виде [[Специальные_формы_КНФ|2-КНФ (КНФ Крома)]], таким образом, чтобы результат данной функции был равен <tex> 1</tex>.
}}
== Алгоритм решения ==
== Алгоритм Решения ==
Рассмотрим любой дизъюнкт функции: <tex> a \vee b </tex>.
Несложно заметить, что это равнозначно записи <tex>(\overline a \to b \wedge \overline b \to a) </tex>.
Рассмотрим любой дизъюнкт функции: <tex> a \vee b </tex> <br>Несложно заметить, что это равнозначно записи <tex>(\overline a \to b \wedge b \to \overline a) </tex> <br> Построим [[Основные_определения_теории_графов|ориентированный граф]], где вершинами будут аргументы и их отрицание, а ребрами будут ребра вида: <tex>\overline a \to b </tex> и <tex> \overline b \to \overline a </tex> для каждого дизъюнкта функции <tex> a \vee b </tex> <br>.
{{Теорема
|statement=
Для того, чтобы данная задача 2-SAT <tex>\mathrm {2SAT}</tex> имела решение, необходимо и достаточно, чтобы для любой переменной <tex> x </tex> из вершины <tex> x </tex> нельзя достичь <tex> \overline x </tex> и из вершины <tex> \overline x </tex> нельзя достичь <tex> x </tex> одновременно. <tex>(\overline x \to x ) \wedge (x \to \overline x) </tex>.
|proof=
<tex>(\Rightarrow)</tex>Докажем достаточность: Пусть 2-SAT <tex>\mathrm {2SAT}</tex> имеет решение. <br>Докажем, что не может быть такого, чтобы для любой переменной <tex> x </tex> из вершины <tex> x </tex> можно достичь <tex> \overline x </tex> и из вершины <tex> \overline x </tex> можно достичь <tex> x </tex> одновременно. <tex>((\overline x \to x ) \wedge (x \to \overline x)) </tex> <br>. Тогда чтобы из <tex> \overline x </tex> достичь <tex> x </tex> <tex> (\overline x \to x </tex> было верным), <tex> x </tex> должен быть равен <tex> 1</tex>. С другой стороны для того, чтобы из <tex> x </tex> достичь <tex> \overline x </tex> <tex> (\overline x \to \overline x </tex> было верным), <tex> x </tex> должен быть равен 0. Отсюда следует противоречие. <br> <br>
<tex>(\Leftarrow)</tex>Докажем необходимость: Пусть для любой переменной <tex> x </tex> из вершины <tex> x </tex> нельзя достичь <tex> \overline x </tex> и из вершины <tex> \overline x </tex> нельзя достичь <tex> x </tex> одновременно. <br>Докажем, что этого достаточно, чтобы 2-SAT <tex>\mathrm {2SAT}</tex> имело решение. <br>Пусть из <tex> \overline x </tex> можно достичь <tex> x </tex>, но из вершины <tex> x </tex> нельзя достичь <tex> \overline x </tex>. Докажем, что из <tex> x </tex> не достижимо такой <tex> y </tex>, что из <tex> y </tex> достижимо <tex> \overline y </tex>. (т.е. <tex> x \to y \to \overline y \, (x = 1, y = 0)) </tex>. <br>Если из <tex> x \to y </tex>, то <tex> \overline x \vee y </tex>, отсюда следует <tex> \overline y \to \overline x </tex>. Тогда <tex> x \to y \to \overline y \to \overline x </tex>. Следовательно <tex> x \to \overline x </tex>. Противоречие.
}}
Теперь мы можем собрать весь алгоритм воедино: #Построим граф импликаций. #<i>Найдём в этом графе [[Отношение_связности,_компоненты_связности#Сильная связность | компоненты сильной связности]] за время <tex>O(N + M)</tex></i>, где <tex> N </tex> — количество вершин в графе (удвоенное количество переменных), а <tex> M </tex> — количество ребер графа (удвоенное количество дизъюнктов).#Пусть <tex>comp[v]</tex> — это номер компоненты сильной связности, которой принадлежит вершине <tex>v</tex>. Проверим, что для каждой переменной <tex>x</tex> вершины <tex>x</tex> и <tex>\overline x</tex> лежат в разных компонентах, т.е. <tex>comp[x] \ne comp[\overline x]</tex>. Если это условие не выполняется, то вернуть <i>решение не существует</i>. #Если <tex>comp[x] > comp[\overline x]</tex>, то переменной <tex>x</tex> выбираем значение <tex> \mathtt {true}</tex>, иначе — <tex> \mathtt {false}</tex>. Компоненты сильной связности найдем за <tex>O(N + M)</tex>, затем проверим каждую из <tex>N</tex> переменных за <tex>O(N)</tex>. Следовательно асимптотика <tex>O(N + M)</tex>. == Применение 2-SAT задач Примеры решения 2SAT ===== Первый пример === Рассмотрим следующую функцию: <tex> (a \vee b) \wedge (a \vee c) \wedge(\overline b \vee c) \wedge(\overline b \vee a) </tex> Данная функция эквивалентна функции <tex>\overline a \to b \wedge\overline b \to a \wedge\overline a \to c \wedge\overline c \to a \wedgeb \to c \wedge\overline c \to \overline b \wedge\overline a \to \overline b \wedgea \to b</tex>. Построим ориентированный граф со следующими множествами вершинам и ребер:множество вершин <tex> V = \{a, b, c, \overline a, \overline b, \overline c\}, </tex>множество ребер <tex> E = \{(\overline a, b), (\overline b, a), (\overline a, c), (\overline c, a), (b, c), (\overline c, \overline b), (\overline a, \overline b), (a, b)\}</tex>. Рассмотрим в графе следующие пути:* <tex> \overline a \to b \to a </tex>* <tex> \overline a \to \overline b \to a </tex>* <tex> \overline c \to a </tex>* <tex> a \to c </tex>* <tex> \overline a \to b \to c </tex>. Т.к. <tex> \overline a \to a </tex>, то <tex> a = 1, \overline a = 0 </tex>. Т.к. <tex> a \to c </tex> и <tex> a = 1 </tex>, то <tex> c = 1, \overline c = 0 </tex>. Значения <tex> b </tex> может быть любым, т.к. все вершины, из которых можно добраться в <tex> b </tex> имеют значение ноль. <b> Ответ: </b> <tex> a = 1, b = 0, c = 1 </tex> или <tex> a = 1, b = 1, c = 1 </tex>. === Второй пример === Рассмотрим следующую функцию: <tex>(\overline a \vee c) \wedge(\overline c \vee \overline a) \wedge(a \vee b) \wedge(\overline b \vee a)</tex>
Алгоритм для решения 2-SAT может быть применим во всех задачах, где есть набор величин, каждая из которых может принимать 2 возможных значения, и есть связи между этими величинами:Данная функция эквивалентна функции <tex>a \to c \wedge\overline c \to \overline a \wedgec \to \overline a \wedgea \to \overline c \wedge\overline a \to b \wedge\overline b \to a \wedgeb \to a \wedge\overline b \to \overline a</tex>
* Расположение текстовых меток на карте или диаграмме. Имеется в виду нахождение такого расположения метокПостроим ориентированный граф со следующими множествами вершинам и ребер:множество вершин V = <tex>\{a, b, при котором никакие две не пересекаются. Стоит заметитьc, что в общем случае\overline a, когда каждая метка может занимать \overline b, \overline c\}, </tex>множество различных позицийребер <tex> E = \{(a, c), (\overline c, \overline a), (c, мы получаем задачу general satisfiability\overline a), которая является NP-полной. Однако(a, если ограничиться только двумя возможными позициями\overline c), то полученная задача будет задачей 2-SAT. * Расположение рёбер при рисовании графа. Аналогично предыдущему пункту(\overline a, b), (\overline b, если ограничиться только двумя возможными способами провести реброa), то мы придём к 2-SAT.* Составление расписания игр. Имеется в виду такая система(b, когда каждая команда должна сыграть с каждой по одному разуa), а требуется распределить игры по типу домашняя-выездная(\overline b, с некоторыми наложенными ограничениями\overline a)\}</tex>.
Заметим следующий путь: <tex> a \to c \to \overline a \to b \to a </tex>.
 
Отсюда следует, что <tex> a \to \overline a \to a </tex>.
 
Следовательно по ранее доказанной теореме, у данной функции решений нет.
 
<b> Ответ: </b> Решений нет.
 
== Использование 2SAT ==
 
Решение <tex>\mathrm {2SAT}</tex> может потребоваться в следующих задачах:
*латинские квадраты<ref> [https://ru.wikipedia.org/wiki/Латинский_квадрат Википедия — Латинские квадраты] </ref>,
*квазигруппы<ref>[https://ru.wikipedia.org/wiki/Квазигруппа_(социология) Википедия — Квазигруппы]</ref>,
*числа Рамсея<ref>[https://ru.wikipedia.org/wiki/Теорема_Рамсея#.D0.A7.D0.B8.D1.81.D0.BB.D0.B0_.D0.A0.D0.B0.D0.BC.D1.81.D0.B5.D1.8F Википедия — Числа Рамсея]</ref>,
*система Штейнера<ref>[https://ru.wikipedia.org/wiki/Система_Штейнера Википедия — Система Штейнера]</ref>,
*проектирование протоколов (пример: для сетевых коммуникаций),
*электронная коммерция (Электронные аукционы и автоматизированные брокеры,
*теории кодирования, криптографии,
*проектирование и тестирование лекарств (мед. препаратов).
== См. также ==
*[http://neerc.ifmo.ru/wiki/index.php?title=КНФ - КНФ]*[http://neerc.ifmo.ru/wiki/index.php?title=Специальные_формы_КНФ - Специальные формы КНФ. КНФ в форме Крона (2-КНФ)]*[http://neerc.ifmo.ru/wiki/index.php?title=Основные_определения_теории_графов#.D0.9E.D1.80.D0.B8.D0.B5.D0.BD.D1.82.D0.B8.D1.80.D0.BE.D0.B2.D0.B0.D0.BD.D0.BD.D1.8B.D0.B5_.D0.B3.D1.80.D0.B0.D1.84.D1.8B - Ориентированные графы]*[http://neerc.ifmo.ru/wiki/index.php?title=3CNFSAT - | NP-полнота задачи о выполнимости булевой формулы в форме 3-КНФ]] == Примечания ==<references/> 
== Источники информации ==
*[http://e-maxx.ru/algo/2_sat MAXimal :: algo :: Задача 2-SAT 2SAT (2-CNF) ]*[https://en.wikipedia.org/wiki/2-satisfiability Википедия — 2-satisfiability - Википедия]
[[Категория: Дискретная математика и алгоритмы]]
[[Категория: Булевы функции ]]
Анонимный участник

Навигация