1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
|
\documentclass[spec, och, labwork]{SCWorks}
\usepackage{preamble}
\begin{document}
\include{titlepage.tex}
В лабораторной работе №4 было продемонстрировано, что задача NP-полноты языка,
состоящего из булевых функций, не являющихся тавтологиями является NP-полной.
Таким образом, её невозможно решить за полиномиальное время и следует
использовать некоторое приближенное решение.
Такой приближённой задачей является задача 2-ВЫП или 2-КНФ, которая может быть
решена за полиномиальное время.
Сначала приведём задачу к другой форме - так называемой импликативной форме.
Заметим, что выражение вида $a \lor b$ эквивалентно $\neg a \implies b$ или
$\neg b \implies a$. Это можно воспринимать следующим образом: если есть
выражение $a \lor b$, и нам необходимо добиться обращения его в $true$, то, если
$a = false$, то необходимо $b = true$, и наоборот, если $b = false$, то
необходимо $a = true$.
Построим теперь так называемый граф импликаций: для каждой переменной в графе
будет по две вершины, обозначим их через $x_i$ и $\neg x_i$. Рёбра в графе будут
соответствовать импликативным связям.
Например, для 2-КНФ формы:
\begin{equation*}
(a \lor b) \land (b \lor \neg c)
\end{equation*}
Граф импликаций будет содержать следующие рёбра (ориентированные):
\begin{align*}
\neg a &\implies b \\
\neg b &\implies a \\
\neg b &\implies \neg c \\
c &\implies b
\end{align*}
Стоит обратить внимание на такое свойство графа импликаций, что если есть ребро
$a \implies b$, то есть и ребро $\neg b \implies \neg a$.
Теперь заметим, что если для какой-то переменной $x$ выполняется, что из $x$
достижимо $\neg x$, а из $\neg x$ достижимо $x$, то задача решения не имеет.
Действительно, какое бы значение для переменной $x$ мы бы ни выбрали, мы всегда
придём к противоречию - что должно быть выбрано и обратное ему значение.
Оказывается, что это условие является не только достаточным, но и необходимым
(доказательством этого факта будет описанный ниже алгоритм). Переформулируем
данный критерий в терминах теории графов. Напомним, что если из одной вершины
достижима другая, а из той вершины достижима первая, то эти две вершины
находятся в одной сильно связной компоненте. Тогда мы можем сформулировать
критерий существования решения следующим образом:
Для того, чтобы данная задача 2-ВЫП имела решение, необходимо и достаточно,
чтобы для любой переменной $x$ вершины $x$ и $\neg x$ находились в разных
компонентах сильной связности графа импликаций.
Этот критерий можно проверить за время $O(N + M)$ с помощью алгоритма поиска
сильно связных компонент.
Теперь построим собственно алгоритм нахождения решения задачи 2-ВЫП в
предположении, что решение существует.
Заметим, что, несмотря на то, что решение существует, для некоторых переменных
может выполняться, что из $x$ достижимо $\neg x$, или (но не одновременно), из
$\neg x$ достижимо $x$. В таком случае выбор одного из значений переменной $x$
будет приводить к противоречию, в то время как выбор другого - не будет.
Научимся выбирать из двух значений то, которое не приводит к возникновению
противоречий. Сразу заметим, что, выбрав какое-либо значение, мы должны
запустить из него обход в глубину/ширину и пометить все значения, которые
следуют из него, т.е. достижимы в графе импликаций. Соответственно, для уже
помеченных вершин никакого выбора между $x$ и $\neg x$ делать не нужно, для них
значение уже выбрано и зафиксировано. Нижеописанное правило применяется только к
непомеченным ещё вершинам.
Утверждается следующее. Пусть $comp[v]$ обозначает номер компоненты сильной
связности, которой принадлежит вершина $v$, причём номера упорядочены в порядке
топологической сортировки компонент сильной связности в графе компонентов (т.е.
более ранним в порядке топологической сортировки соответствуют большие номера:
если есть путь из $v$ в $w$, то $comp[v] \leq comp[w]$). Тогда, если $comp[x] <
comp[\neg x]$, то выбираем значение $\neg x$, иначе, т.е. если $comp[x] >
comp[\neg x]$, то выбираем $x$.
Докажем, что при таком выборе значений мы не придём к противоречию. Пусть, для
определённости, выбрана вершина $x$ (случай, когда выбрана вершина $\neg x$,
доказывается симметрично).
Во-первых, докажем, что из $x$ не достижимо $\neg x$. Действительно, так как
номер компоненты сильной связности $comp[x]$ больше номера компоненты $comp[\neg
x]$, то это означает, что компонента связности, содержащая $x$, расположена
левее компоненты связности, содержащей $\neg x$, и из первой никак не может быть
достижима последняя.
Во-вторых, докажем, что никакая вершина $y$, достижимая из $x$, не является
<<плохой>>, т.е. неверно, что из $y$ достижимо $\neg y$. Докажем это от
противного. Пусть из $x$ достижимо $y$, а из $y$ достижимо $\neg y$. Так как из
$x$ достижимо $y$, то, по свойству графа импликаций, из $\neg y$ будет достижимо
$\neg x$. Но, по предположению, из $y$ достижимо $\neg y$. Тогда мы получаем,
что из $x$ достижимо $\neg x$, что противоречит условию, что и требовалось
доказать.
Итак, мы построили алгоритм, который находит искомые значения переменных в
предположении, что для любой переменной $x$ вершины $x$ и $\neg x$ находятся в
разных компонентах сильной связности. Выше показали корректность этого
алгоритма. Следовательно, мы одновременно доказали указанный выше критерий
существования решения.
Теперь мы можем собрать весь алгоритм воедино:
\begin{itemize}
\item
Построим граф импликаций.
\item
Найдём в этом графе компоненты сильной связности за время O (N + M),
пусть $comp[v]$ "--- это номер компоненты сильной связности, которой
принадлежит вершина $v$.
\item
Проверим, что для каждой переменной $x$ вершины $x$ и $\neg x$ лежат в
разных компонентах, т.е. $comp[x] \neq comp[\neg x]$. Если это условие
не выполняется, то вернуть "решение не существует".
\item
Если $comp[x] > comp[\neg x]$, то переменной $x$ выбираем значение
$true$, иначе "--- $false$.
\end{itemize}
\end{document}
|
