Алгоритмы C++

Построим теперь так называемый граф импликаций: для каждой переменной в графе будет по две вершины, обозначим их через xi и !xi. Рёбра в графе будут соответствовать импликативным связям.

Например, для 2-CNF формы:

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

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

!a => b !b => a !b => !c c => b

Стоит обратить внимание на такое свойство графа импликаций, что если есть ребро a => b, то есть и ребро !b => !a.

Теперь заметим, что если для какой-то переменной x выполняется, что из x достижимо !x, а из !x достижимо x, то задача решения не имеет. Действительно, какое бы значение для переменной x мы бы ни выбрали, мы всегда придём к противоречию - что должно быть выбрано и обратное ему значение. Оказывается, что это условие является не только достаточным, но и необходимым (доказательством этого факта будет описанный ниже алгоритм). Переформулируем данный критерий в терминах теории графов. Напомним, что если из одной

вершины достижима другая, а из той вершины достижима первая, то эти две вершины находятся в одной сильно связной компоненте. Тогда мы можем сформулировать критерий существования решения следующим образом:

Для того, чтобы данная задача 2-SAT имела решение, необходимо и достаточно, чтобы для любой переменной x вершины x и !x находились в разных компонентах сильной связности графа импликаций.

Этот критерий можно проверить за время O (N + M) с помощью алгоритма поиска сильно связных компонент.

Теперь построим собственно алгоритм нахождения решения задачи 2-SAT в предположении, что решение существует.

Заметим, что, несмотря на то, что решение существует, для некоторых переменных может выполняться, что из

x достижимо !x, или (но не одновременно), из !x достижимо x. В таком случае выбор одного из значений переменной x будет приводить к противоречию, в то время как выбор другого - не будет. Научимся выбирать из двух значений то, которое не приводит к возникновению противоречий. Сразу заметим, что, выбрав какое-либо значение, мы должны запустить из него обход в глубину/ширину и пометить все значения, которые следуют из него, т.е. достижимы

в графе импликаций. Соответственно, для уже помеченных вершин никакого выбора между x и !x делать не нужно, для

них значение уже выбрано и зафиксировано. Нижеописанное правило применяется только к непомеченным ещё вершинам.

Утверждается следующее. Пусть comp[v] обозначает номер компоненты сильной связности, которой принадлежит вершина v, причём номера упорядочены в порядке топологической сортировки компонент сильной связности в графе компонентов (т.е. более ранним в порядке топологической сортировки соответствуют большие

номера: если есть путь из v в w, то comp[v] <= comp[w]). Тогда, если comp[x] < comp[!x], то выбираем значение !x, иначе, т.

е. если comp[x] > comp[!x], то выбираем x.

Докажем, что при таком выборе значений мы не придём к противоречию. Пусть, для определённости, выбрана вершина x (случай, когда выбрана вершина !x, доказывается симметрично).

Во-первых, докажем, что из x не достижимо !x. Действительно, так как номер компоненты сильной связности comp [x] больше номера компоненты comp[!x], то это означает, что компонента связности, содержащая x, расположена левее компоненты связности, содержащей !x, и из первой никак не может быть достижима последняя.

Во-вторых, докажем, что никакая вершина y, достижимая из x, не является "плохой", т.е. неверно, что из y достижимо ! y. Докажем это от противного. Пусть из x достижимо y, а из y достижимо !y. Так как из x достижимо y, то, по свойству графа импликаций, из !y будет достижимо !x. Но, по предположению, из y достижимо !y. Тогда мы получаем, что из

x достижимо !x, что противоречит условию, что и требовалось доказать.

Итак, мы построили алгоритм, который находит искомые значения переменных в предположении, что для любой переменной x вершины x и !x находятся в разных компонентах сильной связности. Выше показали корректность этого алгоритма. Следовательно, мы одновременно доказали указанный выше критерий существования решения.

Теперь мы можем собрать весь алгоритм воедино:

●Построим граф импликаций.

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

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

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

Реализация

Ниже приведена реализация решения задачи 2-SAT для уже построенного графа импликаций g и обратного ему графа 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, графа g, построение графа 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);

}

}

Длина объединения отрезков на прямой за O (N log N)

Даны N отрезков на прямой, т.е. каждый отрезок задаётся парой координат (X1, X2). Рассмотрим объединение этих отрезков и найдём его длину.

Алгоритм был предложен Кли (Klee) в 1977 году. Алгоритм работает за O (N log N). Было доказано, что этот алгоритм является быстрейшим (асимптотически).

Описание

Положим все координаты концов отрезков в массив X и отсортируем его по значению координаты.

Дополнительное условие при сортировке - при равенстве координат первыми должны идти левые концы. Кроме того, для каждого элемента массива будем хранить, относится он к левому или к правому концу отрезка. Теперь пройдёмся по всему массиву, имея счётчик C перекрывающихся отрезков. Если C отлично от нуля, то к результату добавляем разницу Xi - Xi-1. Если текущий элемент относится к левому концу, то увеличиваем счётчик C, иначе уменьшаем его.

Реализация

unsigned segments_union_measure (const vector <pair <int,int> > & a)

{

unsigned n = a.size();

vector <pair <int,bool> > x (n*2); for (unsigned i=0; i<n; i++)

{

x[i*2] = make_pair (a[i].first, false); x[i*2+1] = make_pair (a[i].second, true);

}

sort (x.begin(), x.end());

unsigned result = 0; unsigned c = 0;

for (unsigned i=0; i<n*2; i++)

{

if (c && i)

result += unsigned (x[i].first - x[i-1].first); if (x[i].second)

++c;

else

--c;

}

return result;

}

Реализация

Реализации функций, вычисляющих соответственно ориентированную, обычную площадь треугольника, а также две функции проверки, по/против часовой стрелке направлена тройка точек или нет.

int triangle_square_2 (int x1, int y1, int x2, int y2, int x3, int y3) { return x1 * (y2 - y3) + x2 * (y3 - y1) + x3 * (y1 - y2);

}

double triangle_square (int x1, int y1, int x2, int y2, int x3, int y3) { return abs (triangle_square_2 (x1, y1, x2, y2, x3, y3)) / 2.0;

}

bool clockwise (int x1, int y1, int x2, int y2, int x3, int y3) { return triangle_square_2 (x1, y1, x2, y2, x3, y3) < 0;

}

bool counter_clockwise (int x1, int y1, int x2, int y2, int x3, int y3) { return triangle_square_2 (x1, y1, x2, y2, x3, y3) > 0;

}

Проверка двух отрезков на пересечение

Даны два отрезка и , возможно, вырожденные в точку. Требуется проверить, пересекаются они или нет.

Первый способ: ориентированная площадь треугольника

Воспользуемся Ориентированной площадью треугольника и предикат 'По часовой стрелке'. Действительно, чтобы

вычисляя ориентированные площади соответствующих треугольников и сравнивая их знаки.

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

Реализация:

struct pt { int x, y;

};

int square (pt a, pt b, pt c) {

return a.x * (b.y - c.y) + b.x * (c.y - a.y) + c.x * (a.y - b.y);

}

bool intersect_1 (int a, int b, int c, int d) {

return max (a, b) >= min (c, d) && max (c, d) >= min (a, b);

}

bool intersect (pt a, pt b, pt c, pt d) { int s11 = square (a, b, c);

int s12 = square (a, b, d); int s21 = square (c, d, a); int s22 = square (c, d, b);

if (s11 == 0 && s12 == 0 && s21 == 0 && s22 == 0) return intersect_1 (a.x, b.x, c.x, d.x)

&& intersect_1 (a.y, b.y, c.y, d.y);

else

return (s11 * s12 <= 0) && (s21 * s22 <= 0);

}

В целях оптимизации здесь можно вместо вызовов функции подставить сами формулы, и вместо многократного вычисления одинаковых слагаемых запоминать их во временных переменных.

Второй способ: пересечение двух прямых

Вместо пересечения отрезков выполним пересечение двух прямых, в результате, если прямые не параллельны,

получим какую-то точку, которую надо проверить на принадлежность обоим отрезкам; для этого достаточно проверить, что эта точка принадлежит обоим отрезкам в проекции на ось и на ось .

Если же прямые оказались параллельными, то, если они не совпадают, то отрезки точно не пересекаются. Если же прямые совпали, то отрезки лежат на одной прямой, и для проверки их пересечения достаточно проверить, что пересекаются их проекции на ось и .

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

Этот способ оказывается проще первого способа, если заранее известно, что никакие два отрезка не лежат на одной прямой, и отрезки невырождены. Ну и, конечно, преимущество его в том, что он находит и саму точку пересечения. Недостаток — в использовании дробной арифметики.

Реализация (без учёта случая вырожденных отрезков):

struct pt { int x, y;

};

int det (int a, int b, int c, int d) { return a * d - b * c;

}