2SAT
Рассмотрим функцию, записанную в виде 2-КНФ (КНФ Крома).
Решим задачу 2-SAT выполнимости данной функции.
| Задача: |
| 2-SAT (2-satisfiability) выполнимость данной функции — задача распределения аргументов таким образом, чтобы результат данной функции был равен . |
Алгоритм Решения
Рассмотрим любой дизъюнкт функции: . Несложно заметить, что это равнозначно записи .
Построим ориентированный граф, где вершинами будут аргументы и их отрицание, а ребрами будут ребра вида: и для каждого дизъюнкта функции .
| Теорема: |
Для того, чтобы данная задача 2-SAT имела решение, необходимо и достаточно, чтобы для любой переменной из вершины нельзя достичь и из вершины нельзя достичь одновременно. . |
| Доказательство: |
|
Теперь мы можем собрать весь алгоритм воедино:
- Построим граф импликаций.
- Найдём в этом графе компоненты сильной связности за время , пусть — это номер компоненты сильной связности, которой принадлежит вершина .
- Проверим, что для каждой переменной вершины и лежат в разных компонентах, т.е. . Если это условие не выполняется, то вернуть "решение не существует".
- Если , то переменной x выбираем значение true, иначе - false.
Применение 2-SAT задач
Предположим, что семь комиков согласились во время трехдневного фестиваля дать концерты в двух из пяти отелей. При этом у каждого из них один из дней занят другой работой, поэтому вот как выглядят возможные варианты их выступлений в отелях Лас-Вегаса:
- Tomlin может выступить в отелях Aladdin и Caesars в дни 1 и 2;
- Unwin может выступить в отелях Bellagio и Excalibur в дни 1 и 2;
- Vegas может выступить в отелях Desert и Excalibur в дни 2 и 3;
- Williams может выступить в отелях Aladdin и Desert в дни 1 и 3;
- Xie может выступить в отелях Caesars и Excalibur в дни 1 и 3;
- Yankovic может выступить в отелях Bellagio и Desert в дни 2 и 3;
- Zany может выступить в отелях Bellagio и Caesars в дни 1 и 2.
Можно ли составить расписание так, чтобы не возникало никаких конфликтов? Для решения этой задачи можно ввести семь булевых переменных где например, означает выступление Tomlin в Aladdin в первый день и в Caesars во второй, в то время как означает, что дни соответствуют отелям в обратном порядке: выступление в Aladdin — во второй день, а в Caesars — в первый. Тогда мы можем записать ограничения, означающие, что никакие два комедианта не выступают в одном отеле в один и тот же день, следующим образом.
Тогда мы можем записать ограничения, означающие, что никакие два комедианта не выступают в одном отеле в один и тот же день, следующим образом. (В квадратных скобках указаны первая буква отеля и день, в который двое участников не могут выступать одновременно).
Каждое из этих ограничений, конечно же, представляет собой дизъюнкт Крома, которые мы должны выполнить
Кроме того, дизъюнкты Крома могут быть записаны в виде импликаций:
И каждая такая импликация может также быть представлена в альтернативном, "контрапозитивном" виде:
При решение данной задачи можно найти следующий цикл:
Этот цикл говорит о том, что и должны иметь одно и то же значение; так что нет никакой возможности удовлетворить все условия. Если расписание должно быть составлено любой ценой, организаторам фестиваля придется провести переговоры и пересмотреть соглашение по крайней мере с одним из семи комедиантов.
Организаторы могут, например, попытаться временно вывести за рамки картины . Тогда пять из шестнадцати ограничений исчезнут, и останутся только 22 из импликаций. Такое решение будет иметь циклы наподобие или . Можно заметить что значение выполняют каждый дизъюнкт. Эти значения дают нам расписание, которое выполняет шесть из семи исходных условий, начиная с выступления (Tomlin, Unwin, Zany, Williams, Xie) в первый день в (Aladdin, Bellagio, Caesars, Desert, Excalibur).
