Поиск в глубину в графе

End

End

Begin

End

End

Begin

End

End

Begin

2. k := 1;

3. while k > 0 do

4. if существует еще не использованный элемент y є A_k,
такой что P(X[1],..., X[k-1], y) then

5. begin X[k] := y; (*элемент y использован*)

6. if {X[1],..., x[k]} является целочисленным решением then

7. write(X[1],...,X[k]);

8. k := k + 1

10. else (*возврат на более короткое частичное решение;
все элеметы множества A_k вновь становятся неиспользованными *)

11. k := k - 1

Этот алгоритм находит все решения в предположении, что множества A_k, конечные и что существует n, такое что P{x₁,..., x_n} = ложь для всех x₁ є A₁,..., x_n є A_n (последнее условие означает, что все решения имеют длину меньше n).

Покажем наличие общего свойства:

Пусть s > 0, и пусть {x₁,..., x_s-1} - некоторое частичное решение, построенное алгоритмом. Рассмотрим первую итерацию цикла 3, для которой k = s, X[i] = x_i, 1<= i <=s. Начиная с этой итерации, алгоритм генерирует все целочисленные решения, являющиеся расширением последовательности {x₁,..., x_s-1}, и приходит к состоянию, когда k = s-1.

Очевидно, что для s = 1 приведенное выше свойство означает просто корректность алгоритма. Доказательство этого свойства в общем виде проводится по индукции "назад" относительно s. Оно имеет место для s = n, потому что не существует ни одного допустимого элемента для {x₁,..., x_s-1} и сразу же выполняется второе условие условного оператора в строке 10, т.е. переменная к принимает значение s - 1. Предположим теперь правильность нашего свойства для некоторого s > 1. Покажем его правильность для s - 1. Пусть {x₁,..., x_s-2} - произвольное частичное решение, построенное нашим алгоритмом; рассмотрим первую итерацию цикла 3, для которой k = s - 1, X[i] = X_i, 1 <= i <= s - 1. Если существует элемент y, допустимый для {x₁,..., x_s-2},то построение дает частичное решение {x₁,..., x_s-2, y} (строка 5) и переменная k принимает значение s (строка 8). Затем согласно нашему индуктивному предположению будут сгенерированы все решения, являющиеся расширением последовательности {x₁,..., x_s-1, y}, и мы приходим к состоянию, когда k = s - 1, после чего процесс повторяется для следующего неиспользованного элемента y, допустимого для {x₁,..., x_s-2}, пока не будут использованы все такие элементы (такая ситуация может появиться сразу с самого начала). Переменная k уменьшается тогда на 1 и принимает значение s - 2 (строка 11).

Из приведенных выше рассуждений следует, что алгоритм правильно порождает все решения, являющиеся расширением последовательности {x₁,..., x_s-1}, что завершает доказательство шага индукции.

Доказанное свойство приводит непосредственно к следующему простому и очевидному рекурсивному варианту схемы алгоритма с возвратом:

1. procedure AP(k); (*генерирование всех решений,
являющихся расширением последовательности X[1],...,X[k-1];
массив X - глобальный *)

3. for y є A_k такого, что P(X[1],...,X[k-1],y) do

4. begin X[k] := y;

5. if X[1],...,X[k] есть целочисленное решение then

6. write(X[1],...,X[k]);

7. AP(k + 1)

Генерирование всех целочисленных решений можно вызвать вызовом AP(1).

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

Применим теперь алгоритм с возвратом для нахождения гамильтонова цикла в графе G={V,E}. Каждый такой цикл можно представить последовательностью {x₁, x₂,..., x_n+1}, причем x₁ = x_n + 1 = v₀, где v₀ - некоторая фиксированная вершина графа, x_i - x_i+1 для 1 <= i <= n и x_i x_j для 1 <= j <= n. Согласно этим условиям мы можем получить:

A_k = V,
P(x₁,...,x_k - 1, y) <=> y є ЗАПИСЬ[x_k - 1] ^ y {x₁,..., x_k-1}.

Алгоритм 2.14. (Нахождение всех гамильтоновых циклов в графе.)

Данные: граф G = {V,E}, представленный списками инцидентности ЗАПИСЬ[v], v є V.
Результаты: Список всех гамильтоновых циклов графа G.

1. procedure ГАМИЛЬТ(k) (* генерирование всех гамильтоновых циклов,
являющихся расширением последовательности {X[1],..., X[k-1]};
массивы X, DOP - глобальные *)

3. for y є ЗАПИСЬ[X[k-1]] do

4. if (k = n + 1) and (y = v₀) then write(X[1],..., X[n], v₀)

5. else if DOP[y] then

6. begin X[k] := y; DOP[y] :=ложь;

7. ГАМИЛЬТ(k + 1);

8. DOP[y] :=истина

10. end; (*ГАМИЛЬТ*)

11. begin (*главная программа*)

12. for v є V do DOP[v] := истина; (* инициализация*)

13. X[1] := v₀; (*v₀-произвольная фиксированая вершина графа*)

14. DOP v₀ := ложь;

15. ГАМИЛЬТ(2);

Работу этого алгоритма, так же как и произвольного алгоритма с возвратом, можно проиллюстрировать процессом поиска в некотором дереве. Каждая вершина дерева естественным образом соответствует некоторой последовательности {x₁,..., x_k}, причем вершины, соответствующие последовательностям вида {x₁,..., x_k, y}, являются сыновьями этой вершины (корень соответствует пустой последовательности e). Рассмотрим полное дерево D, состоящее из всех возможных последовательностей вида {x₁,..., x_k}, где 0<= k <= n и x_i є A_i для 1 <= i <= k, и временно допустим, что каждый элемент y є A является допустимым для {x₁,..., x_k-1}, если k > n; другими словами,

(x_i є A_i для 1 <= i <= k). Тогда нетрудно отметить, что вызов AP(1) вызывает поиск в глубину во всем дереве D (начиная от корня e).

Для случая менее тривиальной функции P, определяющей допустимость вершин, процесс поиска "опускает" рассмотрение вершин поддерева с корнем в каждой встреченной "недопустимой" вершине (т.е. вершине, соответствующей последовательности {x₁,..., x_k}, для которой P(x₁,..., x_k) = ложь). В этом, собственно говоря, заключается эффективность алгоритма с возвратом в отношении полного перебора всех возможностей.

Для алгоритма 2.14 это иллюстрируется рис.2.

Рис. 2: Граф и дерево, иллюстрирующие алгоритм с возвратом нахождения всех гамильтоновых циклов в этом графе.

Следует отметить, что для большинства приложений число шагов алгоритма с возвратом хотя и будет меньше, чем в случае полного перебора, однако же в наихудшем случае растет по экспоненте с возрастанием размерности задачи. Это справедливо и для случая, когда мы ищем только одно, а не все решения (тогда мы просто прерываем выполнение алгоритма после получения первого решения; отметим, что, когда задача не имеет решения, эта модификация не влияет на ход выполнения алгоритма).

Существует много алгоритмов на графах, в основе которых лежит систематический перебор вершин графа, такой, что каждая вершина просматривается в точности один paз. Поэтому важной задачей является нахождение хороших методов поиска в графе. Вообще говоря, метод поиска, «хорош», если

• (а) он позволяет алгоритму решения интересующей нас задачи легко «грузиться» в этот метод;
• (б) каждое ребро графа анализируется не более одного раза (или, что существенно не меняет ситуации, число раз, ограниченное константой).

Опишем теперь такой метод поиска в неориентированном графе, который стал одной из основных методик проектирования графовых алгоритмов. Этот метод называется поиском в глубину (англ. depth first search).

Общая идея этого метода состоит в следующем:

Мы начинаем поиск с некоторой фиксированной вершины v₀. Затем выбираем произвольную вершину u, смежную с v₀, и повторяем наш процесс от u. В общем случае предположим, что мы находимся в вершине V. Если существует новая (еще непросмотренная} вершина u, u—v, то мы рассматриваем эту вершину (она перестает быть новой), и, начиная с нее, продолжаем поиск. Если же не существует ни одной новой вершины, смежной с v, то мы говорим, что вершина v использована, возвращаемся в вершину, из которой мы попали в v, и продолжаем процесс (если v — v₀, to поиск закончен). Другими словами, поиск в глубину из вершины v основывается на поиске в глубину из всех новых вершин, смежных с v. Это можно легко записать с помощью следующей рекурсивной процедуры:

1.procedure WG(v) (*поиск в глубину из вершины v, переменные НОВЫЙ, ЗАПИСЬ глобальные *)
2.begin рассмотреть v; НОВЫЙ[v]:=ложь;
3. for и є ЗАПИСЬ[v] do
4. if НОВЫЙ[v] then WG(u)
5.end (*вершина v использована*)

Поиск в глубину в произвольном, необязательно связном, графе проводится согласно следующему алгоритму:

1.begin
2. for v є V do НОВЫЙ[v]:=истина;
3. for v є V do
4. if НОВЫЙ[u] then WG(v)
5.end

Покажем теперь, что этот алгоритм просматривает каждую вершину в точности один раз и его сложность порядка 0(m+n). Отметим сначала, что вызов WG(v) влечет за собой просмотр всех вершин связной компоненты графа, содержащей v (если НОВЫЙ[u]=истина для каждой вершины u этой компоненты). Это непосредственно следует из структуры процедуры WG: после посещения вершины (строка 2) следует вызов процедуры WG для всех ее новых соседей. Отметим также, что каждая вершина просматривается не более одного раза, так как просматриваться может только вершина u, для которой НОВЫЙ[и]=истина, сразу же после посещения этой вершины исполняется команда НОВЫЙ[u]:=ложь (строка 2).

Наш алгоритм начинает поиск поочередно от каждой еще не просмотренной вершины, следовательно, просматриваются все вершины графа (необязательно связного).

Чтобы оценить вычислительную сложность алгоритма, отметим сначала, что число шагов в обоих циклах (строки 2 и 3) порядка n, не считая шагов, выполнение которых инициировано вызовом процедуры WG. Эта процедура выполняется не более n paз во втором цикле сразу после посещения каждой и вершин для каждого из ее новых соседей, итого суммарно 0(n + m) paз. Полное число шагов, выполняемых циклом в строке 3 процедуры WG (не считая шагов выполняемых WG(n)), для всех вызовов этой процедуры будет порядка m, где m - число ребер. Это дает общую сложность алгоритма 0(m + n).

Отметим, что алгоритм поиска в глубину в произвольном графе можно легко модифицировать так, чтобы он вычислял связные компоненты этого графа. Зафиксируем этот факт:

Следствие 2.2. Связные компоненты произвольного графа, представленного списками инцидентности, можно вычислить за время О(n + m).

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

1. procedureWG1(v); (* поиск в глубину в графе, начиная с вершины v -нерекурсивная версия процедуры WG; предполагаем, что в начале процесса поиска Р[u] = указатель на первую запись списка ЗАПИСЬ[u] для каждой вершины u; массивы Р, НОВЫЙ - глобальные*)
2. begin СТЕК := ; СТЕК <= v; рассмотреть v; НОВЫЙ[v]:=ложь;
3. while СТЕК = do
4. begin t:= tор(СТЕК); (*t — верхний элемент стека*) (•найти первую новую вершину в списке ЗАПИСЬ*)
5. if P[t]=nil then b:=ложь
6. else b:=not НОВЫЙ[P(t) ^ .Строка];
7. while b do
8. begin P[t]:= Р[t].слeд;
9. if p[t]=nil then b:=ложь
10. else b:=not НОВЫЙ[Р[t] ^ .строка
11. end;
12. if p[t] = nil then («найдена новая вершина •)
13. begin t:=P[t] ^ .Строка; СТЕК <= t;
14. рассмотреть t; НОВЫЙ[t]:=ложь
15. end

Рис. 1: Нумерация вершин графа (в скобках), соответствующая очередности, в которой они просматриваются в процессах поиска в глубину.

Корректность этой процедуры можно доказать путем незначительной модификации анализа процедуры WG. Мы оставляем это читателю. На рис. 1 показан граф, вершины которого перенумерованы в соответствии с тем порядком, в котором они просматриваются в процессе поиска в глубину (мы отождествляем эти вершины с числами 1, ..., 10 и полагаем, что в списке ЗАПИСЬ[u] вершины упорядочены по возрастанию).

Методика поиска в глубину очевидным образом переносится на ориентированные графы. Нетрудно проверить, что в случае ориентированного графа результатом вызова процедуры WG(u), а также WG1(v) будет посещение за О(n + m) шагов всех вершин u, таких что существует путь из v в u