книги / Математическая логика и теория алгоритмов. Анализ алгоритмов
.pdfВ случае явной (прямой) рекурсии в теле процедуры (функции) присутствует оператор вызова самой же себя, в случае косвенной (взаимной) рекурсии – вызов другой процедуры или функции, которая, в свою очередь, вызывает рассматриваемую. Вызов процедурой (функцией) самой себя называется рекурсивным. При рекурсивном вызове изменяется параметр процедуры (функции), причем новое значение параметра меньше (проще) предыдущего. Также в теле рекурсивной процедуры (функции) в том или ином виде обязательно присутствует ветвление, и при определенных значениях входных параметров рекурсивный вызов не происходит. Такая ветка рекурсивной процедуры (функции) называется тривиальной.
7. Некоторые примеры рекурсивных алгоритмов:
1) вычисление факториала числа по формуле n! n (n 1)!, 1! =1;
2)вычисление наибольшего общего делителя по алгорит-
му Евклида: НОД(a,b) НОД(b,a modb), НОД(a,0) a ;
3)бинарный поиск в упорядоченном массиве;
4)быстрая рекурсивная сортировка массива (сортировка
Хоара);
5)алгоритм обхода графа в глубину.
8. Рекурсивную процедуру (функцию) f для случая простой рекурсии можно представить следующим образом:
procedure f(X); begin
h(X); {действия, не содержащие рекурсивных вызовов} if X=S
then triv(X) {тривиальная ветка} else
begin f(Y(X)); {рекурсивный вызов}
r(X) {прочие действия в рекурсивной ветке}
end end;
121
Рекуррентное уравнение для нахождения сложности такой процедуры:
tf (X) = th (X) + tусл (X) + tY (X) + tr (X) + tf (Y), tf (S) = th (S) + tусл (S) + ttriv (S),
где tf (X) – искомая сложность процедуры (функции),
th (X) – сложность общих для тривиальной и рекурсивной веток действий,
tусл (X) – сложность проверки условия if X=S,
tY (X)–сложностьвычисленияновогозначенияпараметраY(X), tr (X) – сложность прочих действий в рекурсивной ветке, ttriv (X) – сложность тривиальной ветки процедуры.
ОТВЕТЫ НА ЗАДАЧИ
9.xn 53 2n 53 ( 3)n .
10.xn (2 3n) ( 1)n 3n 3.
11.Получаемое рекуррентное уравнение: t (h) =4+t (h – 1);
t (0) = 2. Ответ: t (h) = 4h + 2. Можно отметить, что в случае сбалансированного дерева h ~ logN (где N – число вершин) поиск в сбалансированном дереве выполняется за время O (logN).
122
ПРАКТИЧЕСКОЕ ЗАНЯТИЕ № 3 АНАЛИЗ СЛОЖНОСТИ ЗАДАЧ
Цель занятия: закрепить знания о классах сложности задач, научиться определять класс сложности задачи.
Контрольные вопросы
1.Что такое сложность задачи? Какие вы знаете классы сложности задач?
2.Какие задачи относятся к классу сложности P? Приведите примеры задач из класса P.
3.Какие задачи относятся к классу сложности EXP?
4.Какие задачи относятся к классу сложности NP?
5.В каком случае задача T1 полиномиально сводима к задаче T2? Назовите основные свойства полиномиальной сводимости.
6.Какие задачи относятся к классу сложности NPC?
7.Назовите 4 задачи, принадлежащие классу NPC.
8.Сформулируйте основное свойство, позволяющее доказы- ватьNP-полнотузадачнаосновезнаниядругихNP-полныхзадач.
Методика решения задач
При решении задач следует считать известным факт NPполноты следующих задач.
1. Задача «3-Выполнимость». Дано: булева функция f в виде КНФ, при этом в каждый дизъюнкт входит ровно 3 литерала. Определить: выполнима ли функция f.
2.Задача «О клике». Дано: граф G, число k. Определить: существует ли в G полный подграф, содержащий k вершин.
3.Задача «О гамильтоновом цикле». Дано: граф G. Определить: существует ли в G гамильтонов цикл.
4.Задача «О сумме подмножества». Дано: множество натуральных чисел S = {s1, s2, …, sn} и натуральное число t. Опре-
делить: существует ли подмножество S множества S такое, что сумма его элементов равна t.
123
Задача 1. Множество вершин графа называется независимым, если вершины, входящие в это множество, попарно не смежны. Рассмотрим задачу T: «Даны граф G = (V, E) и число k. Определить, существует ли в графе G независимое подмножество, состоящееизk вершин».Доказать,чтозадачаT являетсяNP-полной.
Решение.
1. Докажем, что T NP. Рассматриваемая задача T является задачей принятия решения, а входными данными в ней являются граф G = (V, E) и число k. Воспользуемся вторым определением класса NP: задача принятия решения T NP, если она представима в форме
T (x) = y: (|y| Q (|x|)) &R (x, y), |
(1) |
где y имеет смысл «дополнительных данных», |x| и |y| – объемы входных данных и дополнительных данных соответственно, Q () – полином, а задача R P.
Можно догадаться, что в рассматриваемой задаче в качестве «дополнительных данных» можно взять независимое подмножество V . Объем таких данных не превышает объем исходных данных, а задача R (x, y) состоит из простых проверок (что V содержит k вершин и является независимым множеством в G), которые выполняются за полиномиальное время. Докажем это более строго.
Переформулируем задачу. Ответом на задачу по условию является значение следующего выражения:
T (G, k) = V : V V & |V |=k & ( vi, vj V : (vi, vj) E), (2)
где G = (V, E). Последнее условие в скобках означает проверку, что V действительно является независимым множеством в графе G.
Обозначим:
R (G, k, V ) = V V & |V | = k & ( vi, vj V : (vi, vj) E), (3) где G = (V, E).
124
Тогда
T (G, k) = V : R (G, k, V ). |
(4) |
Как было отмечено выше, входными данными в задаче являются граф G = (V, E) и число k. Поскольку речь идёт о графах, в качестве объема входных данных будем рассматривать количество вершин в графе, которое обозначим за n. Очевидно, что |V | |V| = n, поскольку количество вершин в независимом подмножестве не может быть больше общего количества вершин в графе. Добавим в (4) это утверждение, получим:
T (G, k) = V : (|V | n) &R (G, k, V ). |
(5) |
Формула (5) соответствует требуемой формуле (1) при x = (G, k), y = V , |x| = n, Q (n) = n.
Длязавершениядоказательстваосталосьдоказать,чтоR P. Напомним, что
R (G, k, V ) = V V & |V |=k & ( vi, vj V : (vi, vj) E), G = (V, E), |V| = n.
Приведем алгоритм решения задачи R на псевдокоде. Отметим, что в данном случае от алгоритма не требуется оптимальности, достаточно лишь, чтобы алгоритм имел полиномиальную сложность (неважно даже, какой степени будет этот полином).
|
№ |
|
Действие |
|
Сложность |
|
строки |
|
|
||
|
|
|
|
|
|
1 |
|
cnt 0; |
|
O(1) |
|
|
2 |
|
Для каждой вершины vi из V : |
|
n итераций |
3 |
|
begin |
|
|
|
|
4 |
|
cnt cnt + 1; |
|
O(1) |
|
5 |
|
если vi V, то return false; |
|
O(n) |
|
6 |
|
для каждой вершины vj из V : |
|
n итераций |
|
7 |
|
если (vi,vj) E, то return false; |
|
O(|E|) = O(n2) |
8 |
|
end; |
|
|
|
9 |
|
если cnt k, то return false, иначе |
|
O(1) |
|
|
|
|
return true |
|
|
125
В строке 5 проверяется условие, что V V. Строки 1, 4 и 9 позволяют проверить, что |V | = k. В строках 6–7 проверяется условие, что
vi, vj V : (vi, vj) E.
Оценим сложность приведенного алгоритма. Точная функция сложности будет существенно зависеть от способа представления графа и других нюансов реализации, но нас интересует только порядок роста функции сложности, поэтому будем строить лишь верхнюю оценку сложности, максимально упрощая вычисления.
В строках 1, 4 и 9 выполняется фиксированное количество элементарных операций, поэтому их сложность равна O (1). В строке 5 проверка условия (vi V) может быть организована как перебор всех вершин в V, сложность которого в худшем случае составит O (|V|) = O (n). В строке 7 проверка условия ((vi,vj) E) может быть организована как перебор всех рёбер в E, сложность которого в худшем случае составит O (|E|). Поскольку число ребер в любом графе не больше, чем в пол-
ном, то |E| n (n–1)/2 = O (n2).
Строки 4 и 5 выполняются внутри цикла, описанного в строке 2. Количество повторений цикла равно |V | |V| = n, то есть количество повторений можно ограничить числом n. Строка 7 выполняется внутри вложенного цикла (описанного в строке 6), количество повторений которого аналогично ограничивается числом n, то есть строка 7 выполняется не более чем n n = n2 раз.
В итоге получаем следующую верхнюю оценку сложности:
tRmax (n) O(1) n (O(1) O(n)) n2 O(n2) O(1)
O(1) O(n) O(n2) O(n4) O(n4).
где n4 – это полином, поэтому в соответствии с определением класса P задача R P.
126
2. Подберём известную NP-полную задачу, которая бы полиномиально сводилась к рассматриваемой. В качестве такой задачи T0 рассмотрим известную NP-полную задачу о клике:
T0 (G0, k0) = {в графе G0 существует полный подграф, содержащий k0 вершин}, G0 = (V0, E0).
Более формально эту задачу можно записать следующим образом:
T0 (G0, k0) =
= V0 :V0 V0 &|V0 |=k0 &( vi, vj V0 :vi =vj (vi,vj) E0) (6)
Докажем, что T0 полиномиально сводима к рассматриваемой задаче T, то есть что существует такой алгоритм , что:
1)T0 (G0, k0) = T ( (G0, k0));
2)сложность алгоритма ограничена полиномом относи-
тельно объема входных данных (как уже упоминалось выше, за объем входных данных мы принимаем число n вершин в графе):
t (n) P (n).
Сравнивая выражения (2) и (6), можно заметить, что в преобразовании достаточно «инвертировать» все рёбра в графе, то есть построить дополнительный граф. Описание алгоритма на псевдокоде будет выглядеть следующим образом:
алгоритм
дано: G0 = (V0, E0), k0 begin
V V0
E
для каждой вершины vi из V для каждой вершины vj из V
если (vi vj)&(vi,vj) E0, то E E (vi,vj)
k k0 end
127
Докажем, |
что T0 (G0, k0) |
= T ( (G0, k0)). |
Обозначим |
|
(G0, k0) = (G, k). Заметим, что согласно приведенному выше |
||||
алгоритму V0=V, k0=k, и (vi ,vj ) E vi |
vj (vi ,vj ) E0 . Таким |
|||
образом, |
|
|
|
|
T0 (G0, k0) = V0 : V0 V0 & |V0 | = k0 & ( vi, vj |
V0 : vi = vj |
|||
(vi, vj) E0) = V0 : V0 V & |V0 | = k & ( vi, vj V0 : (vi, vj) E) = |
||||
T (G, k) = T ( (G0, k0)). |
|
|
|
|
Графически рассматриваемая ситуация изображена на |
||||
рисунке. |
|
|
|
|
|
Задача T0 «о клике» |
|
||
Граф G0 = (V0, E0) |
Алгоритм : |
G |
Решаемая задача T |
|
|
G = дополнитель- |
|
«о независимом |
true / |
|
ный к G0 (V=V0; |
|
подмножестве» |
|
|
|
false |
||
|
(vi, vj) E |
|
|
|
|
|
|
|
|
Число k0 |
(vi, vj) E0) |
k |
|
|
|
|
|
||
|
k = k0 |
|
|
|
Рис. Полиномиальная сводимость задачи «о клике» |
||||
к задаче «о независимом подмножестве» |
|
Осталось оценить сложность алгоритма t (n).
Три элементарных присваивания вне циклов требуют фиксированного количества элементарных операций, поэтому их сложность равна O (1). Внутри циклов проверка условия ((vi,vj) E0) может быть организована как перебор всех рёбер, сложность которого в худшем случае, как это рассматривалось выше, составит O (n2). Каждый из циклов повторяется ровно |V| = n раз, то есть общее количество повторений можно ограничить числом n2. В итоге получаем, что:
t (n) O (1) + n2 O (n2) = O (n4),
где n4 – это полином, поэтому t (n) P (n).
128
Доказательство полиномиальной сводимости T0 к T завершено.
3. На шаге 1 мы доказали, что T NP. На шаге 2 мы указали такую задачу T0 NPC, что T0 полиномиально сводима к T. По основному свойству NP-полных задач T NPC, что и требовалось доказать.
Задача 2. Рассмотрим задачу T: «Дан граф G = (V, E). Определить, является ли граф G связным». Определить, к каким классам сложности относится задача T.
Решение. Для определения связности графа вначале построим матрицу смежности А, а затем применим известный и простой в реализации алгоритм Флойда для построения транзитивного замыкания. Если в результате все вершины будут связаны, то исходный граф был связным, иначе – не был. Как обычно, обозначим за n количество вершин в графе, то есть n = |V|.
Запишем алгоритм на псевдокоде:
|
№ |
|
Строка |
|
Сложность |
|
строки |
|
|
||
|
|
|
|
|
|
1 |
|
function isConnected (V:множество |
|
|
|
|
|
|
вершин, E:множество ребер):boolean; |
|
|
2 |
|
var A : array[1..n,1..n] of boolean; |
|
|
|
3 |
|
i,j,k:integer; |
|
|
|
4 |
|
begin |
|
|
|
5 |
|
заполнить массив A значениями false; |
|
O(n2) |
|
|
6 |
|
для каждого ребра (vi,vj) E: |
|
n2 итераций |
|
7 |
|
A[i,j] true; A[j,i] true; |
|
O(1) |
8 |
|
for k:=1 to n do |
|
n итераций |
|
9 |
|
for i:=1 to n do |
|
n итераций |
|
10 |
|
for j:=1 to n do |
|
n итераций |
|
|
11 |
|
if (A[i,k]&A[k,j]) |
|
О(1) |
|
|
|
then A[i,j] true; |
|
|
12 |
|
for i:=1 to n do |
|
n итераций |
|
|
13 |
|
for j:=1 to n do |
|
n итераций |
|
14 |
|
if (not A[i,j]) return false; |
|
О(1) |
15 |
|
return true; |
1 |
||
16 |
|
end; |
|
|
129
Вначале определим сложность этого алгоритма.
В строке 5 происходит заполнение массива размерности n*n. Очевидно, количество операций пропорционально количеству элементов массива, то есть n2. Количество повторений цикла в строке 6 равно количеству ребер в графе |E|. Поскольку число ребер в любом графе не больше, чем в полном, то |E| n (n–1)/2 = O (n2). На каждой итерации в строке 7 выполняется фиксированное число операций, поэтому общая сложность составит O (n2). Количество итераций каждого из трех вложенных циклов в строках 8, 9 и 10 равно n. Таким образом, общее количество итераций составит: n n n = n3. На каждой итерации выполняется фиксированное число операций в строке 11, поэтому общая сложность составит O (n3). Наконец, каждый из двух вложенных циклов в строках 12 и 13 выполняется тоже n раз, общее количество итераций составит: n n = n2. На каждой итерации выполняется фиксированное число операций в строке 14, поэтому общая сложность составит O (n2). В последней строке 15 присутствует одна операция.
В итоге получаем следующую верхнюю оценку сложности:
tisConnectedmax (n) O(n2) O(n2) O(n3) O(n2) 1 O(n3).
Такимобразом,алгоритмимеетполиномиальнуюсложность. Также подробно обоснуем корректность этого алгоритма.
Очевидно, что в течение всего алгоритма поддерживается свойство: если A[i,j]=true, то между вершинами vi и vj в графе G существует путь. Действительно, при начальном заполнении матрицы A в строках 5–7 значение «true» записывается в A только в том случае, если между вершинами есть ребро (путь длины 1). Далее значения в матрице A изменяются только
встроке 11, при этом названное свойство сохраняется: если ме-
жду вершинами vi и vk, а также между vk и vj существует путь, то путь также есть и между вершинами vi и vj. Таким образом, если
витоге все элементы массива A равны true, то между любой
парой вершин существует путь и граф G – связный.
130