Обходы ордерева в глубину и в ширину

Лекция №23

Алгоритм поиска с возвращением, их реализация с помощью рекурсий и динамических структур.

Рассмотрим общий случай, когда решение задачи имеет вид вектора (а₁, а₂,…), длина которого не определена, но ограничена сверху некоторым (известным или неизвестным) числом r, а каждое а_i является элементом некоторого конечного линейно упорядоченного множества А_i. Таким образом, при исчерпывающем поиске в качестве возможных решений мы рассматриваем элементы множества А₁ ´ А₂ ´… ´ А_i для любого i, где i£r, и среди них выбираем те, которые удовлетворяют ограничениям, определяющим решение задачи.

В качестве начального частичного решения берется пустой вектор () и на основе имеющихся ограничений выясняется, какие элементы из А₁ являются кандидатами для их рассмотрения в качестве а₁ (множество таких элементов а₁ из А₁ ниже обозначается через а₁). В качестве а₁ выбирается наименьший элемент множества S₁, что приводит к частичному решению (а₁). В общем случае ограничения, описывающие решения, говорят о том, из какого подмножества S_k множества А_k выбираются кандидаты для расширения частичного решения от (а₁, а₂,…, а_k-1) до (а₁, а₂,…, а_k-1, а_k). Если частичное решение (а₁, а₂,…, а_k-1) не предоставляет других возможностей для выбора нового а_k (т.е. у частичного решения (а₁, а₂,…, а_k-1)
либо нет кандидатов для расширения, либо все кандидаты к данному моменту уже использованы), то происходит возврат и осуществляется выбор нового элемента а_k-1 из S_k-1. Если новый элемент а _k-1 выбрать нельзя, т.е. к данному моменту множество S_k-1 уже пусто, то происходит еще один возврат и делается попытка выбрать новый элемент а_k-2 и т.д.

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

k:=1;
Вычислить S₁ (*например, в качестве S₁ взять А₁ *);
while k>0 do
while не пусто S_k do (* Продвижение *)
В качестве а_k взять наименьший элемент из S_k, удалив его из S_k
if (а₁, а₂,…, а _k ) является решением then Записать это решение
end;
if k<r then k:= k + 1; Вычислить S_k
(* Например, в качестве S_k можно взять А_k *)
end
end;
(* Возврат *) k:= k - 1
end;
(* Все решения найдены *)

 

Более коротко общую процедуру поиска с возвращением можно записать в рекурсивной форме:

procedure ПОИСК (X: ВЕКТОР; i: Integer);
begin
if   Х является решением then записать его end;
if i <= r then Вычислить Si
for all a from Si do ПОИСК (X || (a),i+1) end
end
end

Здесь || обозначает операцию конкатенации (соединения) двух векторов, т.е.
(а₁, а₂,…, а_n) || (b₁, b₂,…, b_m) = (а₁, а₂,…, а_n,,b₁, b₂,…, b_m) и () || (а₁) для любых а₁, а₂,…, а_n,,b₁, b₂,…, b_m.

Вызов ПОИСК((),1) находит все решения, причем все возвраты скрыты в механизме, регулирующем рекурсию.

Для иллюстрации того, как описанный метод применяется при решении конкретных задач, рассмотрим задачу нахождения таких расстановок восьми ферзей на шахматной доске, в которых ни один ферзь не атакует другого. Решение расстановки ферзей можно искать в виде вектора (а₁, а₂, а₃, а₄, а₅, а₆, а₇,

 а₈ ), где а_i – номер вертикали, на которой стоит ферзь, находящийся в i - й горизонтали, т.е. А₁ = А₂ = А₃ = А₄ = А₅ = А₆ = А₇ = А₈ ={1,2,3,4,5,6,7,8}. Каждое частичное решение – это расстановка N ферзей (где 1£N£8) в первых N горизонталях таким образом, чтобы эти ферзи не атаковали друг друга. Заметим, что общая процедура поиска с возвращением при применении ее к задаче о расстановке ферзей уточняется таким образом, что в ней не вычисляются и не хранятся явно множества S_k.

Процесс поиска с возвращением удобно описывать в терминах обхода в глубину (см. ниже) дерева поиска решения, которое строится следующим образом. Корень дерева поиска решения (нулевой уровень) соответствует пустому вектору, являющемуся начальным частичным решением. Для любого k³1 вершины k - го уровня, являющиеся сыновьями некоторой вершины p, соответствуют частичным решениям
(а₁, а₂,…, а _k-1, а _k), где (а₁, а₂,…, а _k-1 ) – это то частичное решение, которое соответствует вершине p, а а_k Î S_k; при этом упорядоченность сыновей вершины p отражает упорядоченность соответствующих элементов а_k в S_k.

Обходы ордерева в глубину и в ширину

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

Рис. 20. Дерево

 

При префиксном обходе ордерева T, сначала нужно посетить его корень v, а затем, если v не является листом, то реализовать префиксный обход всех ее поддеревьев в порядке их упорядоченности. Например, для дерева, показанного на рис. 20, вершины будут проходиться в следующем порядке: A,B,C,D,E,F,G,H,I,J,K,L. Следующая рекурсивная процедура реализует префиксный обход ордерева:

procedure ПРЕФИКСНЫЙ-ОБХОД(T: ордерево);
begin
Посетить корень v ордерева T;
if v не лист then Пусть T₁,…,T_k – поддеревья корня v;
for i:= 1 to k do ПРЕФИКСНЫЙ-ОБХОД(T_i) end
end
end.

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

Посетить корень дерева и поместить его в пустой стек S;
while стек S не является пустым do
Пусть p – вершина, находящаяся на верху стека S;
if Сыновья вершины p еще не посещались
then Посетить старшего сына вершины p и поместить его в стек S
else Удалить вершину p из стека S;
if p имеет братьев then Посетить брата вершины p и поместить его в стек S end
end
end

 

Способ обхода ордерева в ширину предполагает посещение вершин ордерева по старшинству, уровень за уровнем, отправляясь от корня. Например, при обходе в ширину изображенного на рис. 20 дерева вершины проходятся сверху вниз и слева направо и посещаются в следующем порядке: A,B,C,G,H,D,E,F,I,L,J,K. Приведенный ниже алгоритм реализует обход дерева в ширину, используя очередь О.

Поместить корень в пустую очередь O;
while очередь O не пуста do
Пусть p – первая вершина очереди O;
Посетить вершину p и удалить ее из O;
Поместить всех сыновей вершины p в очередь O, начиная со старшего сына
end

Следует заметить, что обход дерева поиска в ширину позволяет обходить дерево поиска одновременно с его построением. Таким образом, можно решать задачу нахождения какого-нибудь одного решения в форме вектора (а₁, а₂,…) неизвестной длины (не зная r), если только известно, что существует конечное решение задачи.

 Обходы графа в глубину и в ширину

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

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

procedure ОБХОД-В-ГЛУБИНУ(р: вершина);
begin
Посетить вершину р;
for all q from множества вершин, смежных с р do
if q еще не посещалась then ОБХОД-В-ГЛУБИНУ(q) end
end
end;
begin
for all р from множества вершин G do
if р еще не посещалась then ОБХОД-В-ГЛУБИНУ(р) end
end
end.

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

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

Нерекурсивный вариант алгоритма обхода графа G в глубину может иметь следующий вид:

procedure ОБХОД-В-ГЛУБИНУ-1(р: вершина);
begin
Посетить вершину р и поместить ее в пустой стек S;
while Стек S непуст do
Пусть р – вершина, находящаяся на верхушке стека S;
if у р есть непосещенные смежные вершины then
Пусть q – непосещенная вершина, смежная вершине р;
Пройти по ребру (р, q), посетить вершину q и поместить ее в стек S
else Удалить вершину р из стека S
end
end
end;

Рис. 21. Граф и его обход в глубину

 

Обход в ширину связного графа предполагает рассмотрение всех его вершин в порядке возрастания расстояния от некоторой вершины, с которой начался данный обход графа. Например, в результате обхода графа G (рис. 21) в ширину возможен следующий порядок посещения вершин: C,A,B,D,H,K,L,E,F,G.

Следующий алгоритм позволяет осуществить обход в ширину любого связного графа G:

procedure ОБХОД-В-ШИРИНУ(р: вершина);
begin
Поместить вершину р в пустую очередь O;
while очередь O не пуста do
Взять первую вершину р из очереди O;
if р еще не посещалась then
Посетить вершину р и поместить в очередь O все вершины, смежные с р
end
end
end;

Контрольные вопросы

1. Дать описание алгоритму поиска с возвращением. В чем заключается суть алгоритма с возвращением?
2. Дать описание алгоритма обхода ордерева в глубину и ширину. В чем заключается суть алгоритма?
3. Дать описание алгоритма обхода графа в глубину и ширину. В чем заключается суть алгоритма?