E073. Bài toán 2-SAT

Источник: e-maxx.ru/algo, страница PDF 219.

Bài toán 2-SAT (2-satisfiability) - это Bài toán распределения значений булевым переменным таким образом, чтобы они удовлетворяли всем наложенным Ràng buộcм. Задачу 2-SAT можно представить в виде конъюнктивной нормальной формы, где в каждом выражении в скобках стоит ровно по две переменной; такая форма называется 2-CNF (2-conjunctive normal form). НаVí dụ:

(a || c) && (a || !d) && (b || !d) && (b || !e) && (c || d)

Приложения

Thuật toán для решения 2-SAT может быть применим во всех Bài toánх, где есть набор величин, каждая из которых может принимать 2 возможных значения, и есть связи между этими величинами:

● Расположение текстовых меток на карте или диаграмме.

Имеется в виду нахождение такого расположения меток, при котором никакие две не пересекаются. Стоит заметить, что в общем случае, когда каждая метка может занимать множество различных позиций, мы получаем задачу general satisfiability, которая является NP-полной. Однако, если ограничиться только двумя возможными позициями, то полученная Bài toán будет задачей 2-SAT.

● Расположение рёбер при рисовании đồ thịа.

Аналогично предыдущему пункту, если ограничиться только двумя возможными способами провести edge, то мы придём к 2-SAT.

● Составление расписания игр.

Имеется в виду такая система, когда каждая команда должна сыграть с каждой по одному разу, а it is required распределить игры по типу домашняя-выездная, с некоторыми наложенными Ràng buộcми.

● и т.д.

Thuật toán

Сначала приведём задачу к другой форме - так называемой импликативной форме. Заметим, что выражение вида a || b эквивалентно !a => b или !b => a. Это можно воспринимать следующим образом: если есть выражение a || b, и нам необходимо добиться обращения его в true, то, если a=false, то необходимо b=true, и наоборот, если b=false, то необходимо a=true. Построим теперь так называемый đồ thị импликаций: для каждой переменной в đồ thịе будет по две вершины, обозначим их через xi и !xi. Рёбра в đồ thịе будут соответствовать импликативным связям. НаVí dụ, для 2-CNF формы:

(a || b) && (b || !c)

đồ thị импликаций будет содержать следующие рёбра (ориентированные):

!a => b

!b => a

!b => !c

c => b

Стоит обратить внимание на такое свойство đồ thịа импликаций, что если есть edge a => b, то есть и edge !b => !a. Теперь заметим, что если для какой-то переменной x выполняется, что из x достижимо !x, а из !x достижимо x, то Bài toán решения не имеет. Действительно, какое бы значение для переменной x мы бы ни выбрали, мы всегда придём к противоречию - что должно быть выбрано и обратное ему значение. Оказывается, что это Đề bài является не только достаточным, но и необходимым (Chứng minhм этого факта будет описанный ниже Thuật toán). Переформулируем данный критерий в терминах теории đồ thịов. Напомним, что если из одной вершины достижима другая, а из той вершины достижима первая, то эти две вершины находятся в одной сильно связной компоненте. Тогда мы можем сформулировать критерий существования решения следующим образом: Для того, чтобы данная Bài toán 2-SAT имела Lời giải, необходимо и достаточно, чтобы для любой переменной x вершины x и !x находились в разных компонентах сильной связности đồ thịа импликаций. Этот критерий можно проверить за время O (N + M) с помощью Thuật toánа поиска сильно связных компонент. Теперь построим собственно Thuật toán нахождения решения задачи 2-SAT в предположении, что Lời giải существует. Заметим, что, несмотря на то, что Lời giải существует, для некоторых переменных может выполняться, что из x достижимо !x, или (но не одновременно), из !x достижимо x. В таком случае выбор одного из значений переменной x будет приводить к противоречию, в то время как выбор другого - не будет. Научимся выбирать из двух значений то, которое не приводит к возникновению противоречий. Сразу заметим, что, выбрав какое-либо значение, мы должны запустить из него обход в глубину/ширину и пометить все значения, которые следуют из него, т.е. достижимы в đồ thịе импликаций. Соответственно, для уже помеченных вершин никакого выбора между x и !x делать не нужно, для них значение уже выбрано и зафиксировано. Нижеописанное правило применяется только к непомеченным ещё vertexм. Утверждается следующее. Пусть comp[v] обозначает номер компоненты сильной связности, которой принадлежит vertex v, причём номера упорядочены в порядке топологической сортировки компонент сильной связности в đồ thịе компонентов (т.е. более ранним в порядке топологической сортировки соответствуют большие номера: если есть путь из v в w, то comp[v] <= comp[w]). Тогда, если comp[x] < comp[!x], то выбираем значение !x, иначе, т. е. если comp[x] > comp[!x], то выбираем x. Докажем, что при таком выборе значений мы не придём к противоречию. Пусть, для определённости, выбрана vertex x (случай, когда выбрана vertex !x, доказывается симметрично). Во-первых, докажем, что из x не достижимо !x. Действительно, так как номер компоненты сильной связности comp [x] больше номера компоненты comp[!x], то это означает, что компонента связности, содержащая x, расположена левее компоненты связности, содержащей !x, и из первой никак не может быть достижима последняя. Во-вторых, докажем, что никакая vertex y, достижимая из x, не является "плохой", т.е. неверно, что из y достижимо ! y. Докажем это от противного. Пусть из x достижимо y, а из y достижимо !y. Так как из x достижимо y, то, по свойству đồ thịа импликаций, из !y будет достижимо !x. Но, по предположению, из y достижимо !y. Тогда мы получаем, что из x достижимо !x, что противоречит условию, что и требовалось доказать. Итак, мы построили Thuật toán, который находит искомые значения переменных в предположении, что для любой переменной x вершины x и !x находятся в разных компонентах сильной связности. Выше показали корректность этого Thuật toánа. Следовательно, мы одновременно доказали указанный выше критерий существования решения. Теперь мы можем собрать весь Thuật toán воедино:

● Построим đồ thị импликаций.

● Найдём в этом đồ thịе компоненты сильной связности за время O (N + M), пусть comp[v] - это номер компоненты

сильной связности, которой принадлежит vertex v.

● Проверим, что для каждой переменной x вершины x и !x лежат в разных компонентах, т.е. comp[x] ≠ comp[!x]. Если

это Đề bài не выполняется, то вернуть "Lời giải не существует".

● Если comp[x] > comp[!x], то переменной x выбираем значение true, иначе - false.

Cài đặt

Ниже приведена Cài đặt решения задачи 2-SAT для уже построенного đồ thịа импликаций g и обратного ему đồ thịа gt (т.е. в котором направление каждого ребра изменено на противоположное). Программа выводит номера выбранных вершин, либо фразу "NO SOLUTION", если решения не существует.

int n;

vector < vector<int> > g, gt;

vector<bool> used;

vector<int> order, comp;

void dfs1 (int v) {

used[v] = true;

for (size_t i=0; i<g[v].size(); ++i) {

int to = g[v][i];

if (!used[to])

dfs1 (to);

}

order.push_back (v);

}

void dfs2 (int v, int cl) {

comp[v] = cl;

for (size_t i=0; i<gt[v].size(); ++i) {

int to = gt[v][i];

if (comp[to] == -1)

dfs2 (to, cl);

} }

int main() {

... чтение n, đồ thịа g, построение đồ thịа gt ...

used.assign (n, false);

for (int i=0; i<n; ++i)

if (!used[i])

dfs1 (i);

comp.assign (n, -1);

for (int i=0, j=0; i<n; ++i) {

int v = order[n-i-1];

if (comp[v] == -1)

dfs2 (v, j++);

}

for (int i=0; i<n; ++i)

if (comp[i] == comp[i^1]) {

puts ("NO SOLUTION");

return 0;

}

for (int i=0; i<n; ++i) {

int ans = comp[i] > comp[i^1] ? i : i^1;

printf ("%d ", ans);

} }