24
правки
Изменения
2SAT
,→Применение 2-SAT задач: Добавлен пример применения 2-SAT
== Применение 2-SAT задач ==
* Расположение текстовых меток на карте или диаграмме. Имеется Tomlin может выступить в отелях Aladdin и Caesars в дни 1 и 2;*Unwin может выступить в виду нахождение такого расположения меток, при котором никакие две не пересекаются. Стоит заметить, что отелях Bellagio и Excalibur в общем случае, когда каждая метка дни 1 и 2;*Vegas может занимать множество различных позиций, мы получаем задачу general satisfiability, которая является NP-полной. Однако, если ограничиться только двумя возможными позициями, то полученная задача будет задачей выступить в отелях Desert и Excalibur в дни 2-SAT. и 3;*Williams может выступить в отелях Aladdin и Desert в дни 1 и 3;*Xie может выступить в отелях Caesars и Excalibur в дни 1 и 3;* Расположение рёбер при рисовании графа. Аналогично предыдущему пункту, если ограничиться только двумя возможными способами провести ребро, то мы придём к Yankovic может выступить в отелях Bellagio и Desert в дни 2-SAT.и 3;* Составление расписания игр. Имеется Zany может выступить в виду такая система, когда каждая команда должна сыграть с каждой по одному разу, а требуется распределить игры по типу домашняя-выездная, с некоторыми наложенными ограничениямиотелях Bellagio и Caesars в дни 1 и 2.
Можно ли составить расписание так, чтобы не возникало никаких конфликтов?
Для решения этой задачи можно ввести семь булевых переменных <tex>{t, u, v, w, x, у, z}, </tex> где <tex>t</tex> например, означает выступление Tomlin в Aladdin в первый день и в Caesars во второй, в то время как <tex> \overline t </tex> означает, что дни соответствуют отелям в обратном порядке: выступление в Aladdin — во второй день, а в Caesars — в первый. Тогда мы можем записать ограничения, означающие, что никакие два комедианта не выступают в одном отеле в один и тот же день, следующим образом.
Тогда мы можем записать ограничения, означающие, что никакие два комедианта не выступают в одном отеле в один и тот же день, следующим образом. (В квадратных скобках указаны первая буква отеля и день, в который двое участников не могут выступать одновременно).
{| class="wikitable" style="width:10cm" border=1
|<tex>\overline {(t \wedge w)} {[}A1{]} </tex>
||<tex>\overline {(y \wedge \overline z)} {[}B2{]} </tex>
||<tex>\overline {(t \wedge z)} {[}C2{]} </tex>
||<tex>\overline {(w \wedge y)} {[}D3{]} </tex>
|-
|<tex>\overline {(u \wedge z)} {[}B1{]} </tex>
||<tex>\overline {(\overline t \wedge x)} {[}C1{]} </tex>
||<tex>\overline {(v \wedge \overline y)} {[}D2{]} </tex>
||<tex>\overline {(\overline u \wedge \overline x)} {[}E1{]} </tex>
|-
|<tex>\overline {(\overline u \wedge y)} [B2] </tex>
||<tex>\overline {(\overline t \wedge \overline z)} [C1] </tex>
||<tex>\overline {(\overline v \wedge w)} [D3] </tex>
||<tex>\overline {(u \wedge \overline v)} [E2] </tex>
|-
|<tex>\overline {(\overline u \wedge \overline z)} [B2] </tex>
||<tex>\overline {(x \wedge \overline z)} [C1] </tex>
||<tex>\overline {(\overline v \wedge y)} [D3] </tex>
||<tex>\overline {(v \wedge x)} [E3] </tex>
|}
Каждое из этих ограничений, конечно же, представляет собой дизъюнкт Крома, которые мы должны выполнить
<tex>
(\overline t \vee \overline w)
\wedge (\overline u \vee \overline z)
\wedge (u \vee \overline y)
\wedge (u \vee z)
\wedge (\overline y \vee z)
\wedge (t \vee \overline x)
\wedge (t \vee z)
\wedge (\overline x \vee z)
\wedge
</tex>
<tex>
(\overline t \vee \overline z)
\wedge (\overline v \vee y)
\wedge (v \vee \overline w)
\wedge (v \vee \overline y)
\wedge (\overline w \vee \overline y)
\wedge (u \vee x)
\wedge (\overline u \vee v)
\wedge (\overline v \vee \overline x)
</tex>
Кроме того, дизъюнкты Крома могут быть записаны в виде импликаций:
<tex>
(t \to \overline w)
\wedge (u \to \overline z)
\wedge (\overline u \to \overline y)
\wedge (\overline u \to z)
\wedge (y \to z)
\wedge (\overline t \to \overline x)
\wedge (\overline t \to z)
\wedge (x \to z)
\wedge
</tex>
<tex>
(t \to \overline z)
\wedge (v \to y)
\wedge (\overline v \to \overline w)
\wedge (\overline v \to \overline y)
\wedge (w \to \overline y)
\wedge (\overline u \to x)
\wedge (u \to v)
\wedge (v \to \overline x)
</tex>
И каждая такая импликация может также быть представлена в альтернативном, "контрапозитивном" виде:
<tex>
(w \to \overline t)
\wedge (z \to \overline u)
\wedge (\overline y \to \overline u)
\wedge (\overline z \to u)
\wedge (z \to y)
\wedge (\overline x \to \overline t)
\wedge (\overline z \to t)
\wedge (z \to x)
\wedge
</tex>
<tex>
(z \to \overline t)
\wedge (y \to v)
\wedge (\overline w \to \overline v)
\wedge (\overline y \to \overline v)
\wedge (y \to \overline w)
\wedge (\overline u \to x)
\wedge (v \to u)
\wedge (x \to \overline v)
</tex>
При решение данной задачи можно найти следующий цикл:
<tex>
u
\to \overline z
\to \overline y
\to \overline v
\to \overline u
\to z
\to \overline t
\to \overline x
\to \overline u
</tex>
Этот цикл говорит о том, что <tex> v </tex> и <tex> \overline v </tex> должны иметь одно и то же значение; так что нет никакой возможности удовлетворить все условия. Если расписание должно быть составлено любой ценой, организаторам фестиваля придется провести переговоры и пересмотреть соглашение по крайней мере с одним из семи комедиантов.
Организаторы могут, например, попытаться временно вывести за рамки картины <tex> v </tex>. Тогда пять из шестнадцати ограничений исчезнут, и останутся только 22 из импликаций.
Такое решение будет иметь циклы наподобие <tex> z \to \overline u \to x \to z </tex> или <tex> t \to \overline z \to t </tex>.
Можно заметить что значение <tex> tuwxyz = 110000 </tex> выполняют каждый дизъюнкт. Эти значения дают нам расписание, которое выполняет шесть из семи исходных условий, начиная с выступления (Tomlin, Unwin, Zany, Williams, Xie) в первый день в (Aladdin, Bellagio, Caesars, Desert, Excalibur).
== См. также ==
