Если у вас возникли сложности с курсовой, контрольной, дипломной, рефератом, отчетом по практике, научно-исследовательской и любой другой работой - мы готовы помочь.
Предоплата всего
Подписываем
екция: Алгоритмы поиска с возвращением 4 из 4 с.
|
[1] Оглавление [2] Алгоритм поиска с возвращением [2.1] Обходы ордерева в глубину и в ширину [2.2] Обходы графа в глубину и в ширину [2.3] Контрольные вопросы |
Лекция №23
Рассмотрим общий случай, когда решение задачи имеет вид вектора (а1, а2,…), длина которого не определена, но ограничена сверху некоторым (известным или неизвестным) числом r, а каждое аi является элементом некоторого конечного линейно упорядоченного множества Аi . Таким образом, при исчерпывающем поиске в качестве возможных решений мы рассматриваем элементы множества А1 А2 … Аi для любого i, где ir , и среди них выбираем те, которые удовлетворяют ограничениям, определяющим решение задачи.
В качестве начального частичного решения берется пустой вектор ( ) и на основе имеющихся ограничений выясняется, какие элементы из А1 являются кандидатами для их рассмотрения в качестве а1 (множество таких элементов а1 из А1 ниже обозначается через а1). В качестве а1 выбирается наименьший элемент множества S1, что приводит к частичному решению (а1) . В общем случае ограничения, описывающие решения, говорят о том, из какого подмножества Sk множества Аk выбираются кандидаты для расширения частичного решения от (а1, а2,… , аk-1) до (а1, а2,… , аk-1, аk) . Если частичное решение (а1, а2,… , аk-1) не предоставляет других возможностей для выбора нового аk (т.е. у частичного решения (а1, а2,… , аk-1)
либо нет кандидатов для расширения, либо все кандидаты к данному моменту уже использованы), то происходит возврат и осуществляется выбор нового элемента аk-1 из Sk-1 . Если новый элемент аk-1 выбрать нельзя, т.е. к данному моменту множество Sk-1 уже пусто, то происходит еще один возврат и делается попытка выбрать новый элемент аk-2 и т.д.
Общую схему алгоритма, осуществляющего поиск с возвращением для нахождения всех решений, можно представить в следующем виде:
k:=1;
Вычислить S1 (*например, в качестве S1 взять А1 *);
while k>0 do
while не пусто Sk do
(* Продвижение *)
В качестве аk взять наименьший элемент из Sk , удалив его из Sk
if (а1, а2,… , аk) является решением
then Записать это решение
end;
if k<r then
k := k + 1; Вычислить Sk
(* Например, в качестве Sk можно взять А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
Здесь || обозначает операцию конкатенации (соединения) двух векторов, т.е.
(а1, а2,… , аn) || (b1, b2,… , bm)= (а1, а2,… , аn,,b1, b2,… , bm) и () || (а1) для любых а1, а2,… , аn,,b1, b2,… , bm.
Вызов ПОИСК((),1) находит все решения, причем все возвраты скрыты в механизме, регулирующем рекурсию.
Для иллюстрации того, как описанный метод применяется при решении конкретных задач, рассмотрим задачу нахождения таких расстановок восьми ферзей на шахматной доске, в которых ни один ферзь не атакует другого. Решение расстановки ферзей можно искать в виде вектора (а1, а2, а3, а4, а5, а6, а7, а8), где аi – номер вертикали, на которой стоит ферзь, находящийся в i-й горизонтали, т.е. А1 =А2 =А3=А4 =А5 =А6 =А7 =А8 ={1,2,3,4,5,6,7,8} . Каждое частичное решение – это расстановка N ферзей (где 1N8) в первых N горизонталях таким образом, чтобы эти ферзи не атаковали друг друга. Заметим, что общая процедура поиска с возвращением при применении ее к задаче о расстановке ферзей уточняется таким образом, что в ней не вычисляются и не хранятся явно множества Sk .
Процесс поиска с возвращением удобно описывать в терминах обхода в глубину (см. ниже) дерева поиска решения, которое строится следующим образом. Корень дерева поиска решения (нулевой уровень) соответствует пустому вектору, являющемуся начальным частичным решением. Для любого k1 вершины k-го уровня, являющиеся сыновьями некоторой вершины p, соответствуют частичным решениям
(а1, а2,… , аk-1, аk), где (а1, а2,… , аk-1) – это то частичное решение, которое соответствует вершине p, а аk Sk; при этом упорядоченность сыновей вершины p отражает упорядоченность соответствующих элементов аk в Sk .
Во многих задачах необходимо обойти некоторое ордерево в глубину или в ширину, посещая каждую его вершину в точности один раз и выполняя при этом некоторую систематическую обработку информации, относящейся к этой вершине. Посещение каждой вершины дерева может быть связано или с выполнением простой операции, например с распечаткой пометки вершины дерева, или со сложной, например, с вычислением некоторой функции.
Рис. 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
Пусть T1,…,Tk – поддеревья корня v;
for i := 1 to k do ПРЕФИКСНЫЙ-ОБХОД(Ti) 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
Следует заметить, что обход дерева поиска в ширину позволяет обходить дерево поиска одновременно с его построением. Таким образом, можно решать задачу нахождения какого-нибудь одного решения в форме вектора (а1, а2,…) неизвестной длины (не зная 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;