Лекция: Алгоритм поиска с возвратом.

При решении задач путем поиска на основе данных либо от цели требуется найти путь от начального состояния к целевому на графе пространства состояний. Последова­тельность дуг этого пути соответствует упорядоченной последовательности этапов ре­шения задачи. Если решатель задач имеет в своем распоряжении оракула или иное непо­грешимое средство предсказания для построения пути решения, то и поиска не требует­ся. Модуль решения задачи должен безошибочно двигаться прямо к цели, запоминая путь движения. Поскольку для интересных задач оракулов не существует, решатель дол­жен рассматривать различные пути до тех пор, пока не достигнет цели. Поиск с возвра­тами(backtrackiпg) — это метод систематической проверки различных путей в про­странстве состояний.

Начнем рассмотрение алгоритмов поиска с алгоритма поиска с возвратами, поскольку это один из пер­вых алгоритмов поиска в информатике, который допускает естественную реализацию в рекурсивной среде, ориентированной на использование стеков.

Алгоритм поиска с возвратами запускается из начального состояния и следует по некото­рому пути до тех пор, пока не достигнет цели либо не упрется в тупик. Если цель достигнута, поиск завершается, и в качестве решения задачи возвращается путь к цели. Если же поиск привел в тупиковую вершину, то алгоритм возвращается в ближайшую из пройденных вер­шин и исследует все ее вершины-братья, а затем спускается по одной из ветвей, ведущих от вершины — брата. Этот процесс описывается следующим рекурсивным правилом.

Если исходное состояние S не удовлетворяет требованиям цели, то из списка его потомков выбираем первую вершину Schild1, и к этой вершине рекурсивно применяем процедуру поиска с воз­вратами. Если в результате поиска с возвратами в подграфе с корнем Schild1 цель не обна­ружена, то повторяем процедуру для вершины-брата Schild2. Эта процедура продолжается до тех пор, пока один из потомков рассматриваемой вершины-брата не окажется целевой вершиной, либо не выяснится, что рассмотрены уже все возможные потомки (все вершины­ — братья). Если же ни одна из вершин-братьев вершины S не привела к цели, возвращаемся к предку вершины S и повторяем процедуру с вершиной-братом S и т.д.

Алгоритм работает до тех пор, пока не достигнет цели либо не исследует все про­странство состояний. На рис. 10.9 изображен процесс поиска с возвратами в гипотети­ческом пространстве состояний. Пунктирные стрелки в дереве указывают направление процесса поиска в пространстве состояний (вниз или вверх). Числа возле каждой верши­ны указывают порядок их посещения.

Рисунок 10.9. Поиск с возвратом в гипотетическом пространстве состояний.

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

SL (State List) — список исследованных состояний рассматриваемого пути. Если цель уже найдена, то SL содержит список состояний пути решения.

NSL (New State List) — список новых состояний, он содержит вершины, подлежащие рассмотрению, т.е. список вершин, потомки которых еще не были порождены и рас­смотрены.

DЕ (Dead Ends) — список тупиков, т.е. список вершин, потомки которых уже были ис­следованы, но не привели к цели. Если состояние из этого списка снова встречается в процессе поиска, то оно обнаруживается в списке DЕ и исключается из рассмотрения.

– переменная текущего со­стояния. CS

При описании алгоритма поиска с возвратами на графах общего вида (не только для

деревьев) необходимо учитывать возможность повторного появления состояний, чтобы избежать их повторного рассмотрения, а также петель, ведущих к зацикливанию алго­ритма поиска пути. Это обеспечивается проверкой каждой вновь порожденной вершины на ее вхождение в один из трех вышеуказанных списков. Если новое состояние обнару­жится хотя бы в одном из двух списков SL или DЕ, значит, оно уже рассматривалось, и его следует проигнорировать. Обозначим текущее состояние при поиске с возвратами через CS (current state). Состояние CS всегда равно последнему из состояний, занесенных в список SL, и представ­ляет «фронтальную» вершину на построенном в данный момент пути. Правила вывода, ходы в игре или иные соответствующие операторы решения задачи упорядочиваются и применяются к CS. В результате возникает упорядоченное множество новых состояний, потомков CS. Первый из этих потомков объявляется новым текущим состоянием, а ос­тальные заносятся в список новых состояний NSL для дальнейшего изучения. Новое те­кущее состояние заносится в список состояний SL, и поиск продолжается. Если текущее состояние CS не имеет потомков, то оно удаляется из списка состояний SL (именно в этот момент алгоритм «возвращается назад»), и исследуется какой-либо из оставшихся потомков его предка в списке состояний SL.

Таблица 10.1. Состояние списков и текущей переменной после каждой итерации алгоритма.

В таблице 10.1 приведено состояние списков SL; NSL; DE; и текущей переменной CS после каждой итерации алгоритма поиска с возвратами на графах для графа на рис. 10.7.

Алгоритм поиска с возвратами на графах для графа из рис. 10.7 работает следующим образом:

0 итерация — Инициализируем списки. CS=A; SL=[A]; NSL=[A]; DE=[ ];

1 итерация – Применяем процедуру определения потомков к CS=A, потомки есть, ими являются вершины В, С,D. Первый из этих потомков объявляется новым текущим состоянием, все они заносятся в список новых состояний NSL. Новое те­кущее состояние заносится в список состояний SL, и алгоритм переходит к следующей итерации.

2 итерация — Применяем процедуру определения потомков к CS=В, потомки есть, ими являются вершины Е, F. Первый из этих потомков объявляется новым текущим состоянием, все они заносятся в список новых состояний NSL. Новое те­кущее состояние заносится в список состояний SL, и алгоритм переходит к следующей итерации.

3 итерация — Применяем процедуру определения потомков к CS=Е, потомки есть, ими являются вершины Н, I. Первый из этих потомков объявляется новым текущим состоянием, все они заносятся в список новых состояний NSL. Новое те­кущее состояние заносится в список состояний SL, и алгоритм переходит к следующей итерации.

4 итерация — Применяем процедуру определения потомков к CS=Н, потомков нет, поэтому вершина Н удаляется из списка состояний SL и списка новых состояний NSL и заносится в список тупиков ОЕ. Первая вершина из списка новых состояний NSL вершина I объявляется новым текущим состоянием. Новое те­кущее состояние заносится в список состояний SL и алгоритм переходит к следующей итерации.

5 итерация — Применяем процедуру определения потомков к CS=I, потомков нет, поэтому вершина I удаляется из списка состояний SL и списка новых состояний NSL и заносится в список тупиков ОЕ. Первая вершина из списка новых состояний NSL вершина F объявляется новым текущим состоянием, но эта вершина уже была в списке состоянийSL поэтому вершина F удаляется из списка состояний SL и списка новых состояний NSL и заносится в список тупиков ОЕ. Первая вершина из списка новых состояний NSL вершина объявляется новым текущим состоянием. Новое те­кущее состояние заносится в список состояний SL и алгоритм переходит к следующей итерации.

6 итерация — Применяем процедуру определения потомков к CS=F, потомки есть, им является вершина J. Первый и единственный из этих потомков объявляется новым текущим состоянием, он заносятся в список новых состояний NSL. Новое те­кущее состояние заносится в список состояний SL, и алгоритм переходит к следующей итерации.

7 итерация — Применяем процедуру определения потомков к CS=J, потомков нет, поэтому вершина J удаляется из списка состояний SL и списка новых состояний NSL и заносится в список тупиков ОЕ. Первая вершина из списка новых состояний NSL вершина F объявляется новым текущим состоянием, но эта вершина уже была в списке состоянийSL поэтому вершина F удаляется из списка состояний SL и списка новых состояний NSL и заносится в список тупиков ОЕ. Первая вершина из списка новых состояний NSL вершина В объявляется новым текущим состоянием, но эта вершина также уже была в списке состоянийSL поэтому вершина В удаляется из списка состояний SL и списка новых состояний NSL и заносится в список тупиков ОЕ. Первая вершина из списка новых состояний NSL вершина С объявляется новым текущим состоянием. Новое те­кущее состояние заносится в список состояний SL и алгоритм переходит к следующей итерации.

8 итерация — Применяем процедуру определения потомков к CS=С, потомки есть, ими являются вершины F, G. Первый из этих потомков вершина F находится в списке тупиков ОЕ и поэтому вершина G объявляется новым текущим состоянием, она заносятся в списки состояний SL и новых состояний NSL и алгоритм переходит к следующей итерации.

9 итерация — Применяем процедуру определения потомков к CS=G, потомков нет, поэтому вершина G удаляется из списка состояний SL и списка новых состояний NSL и заносится в список тупиков ОЕ. Первая вершина из списка новых состояний NSL вершина С объявляется новым текущим состоянием, но эта вершина уже была в списке состоянийSL поэтому вершина С удаляется из списка состояний SL и списка новых состояний NSL и заносится в список тупиков ОЕ. Первая вершина из списка новых состояний NSL вершина D объявляется новым текущим состоянием. Новое те­кущее состояние заносится в список состояний SL и алгоритм переходит к следующей итерации.

10 итерация — Применяем процедуру определения потомков к CS=D, потомков нет, поэтому вершина D удаляется из списка состояний SL и списка новых состояний NSL и заносится в список тупиков ОЕ. Первая вершина из списка новых состояний NSL вершина А объявляется новым текущим состоянием, но эта вершина является начальной вершиной, следовательно просмотр пространства состояний графа на рис. 10.7. закончен и алгоритм заканчивает свою работу.

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

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

Поиск с возвратами(backtrack) — это алгоритм поиска на графе пространства состояний. Алгоритмы поиска на графах, которые будут рассматриваться далее, включая поиск в глубину(depth-first), поиск в ширину (breadth-first) и поиск по первому наилучшему совпадению (best­ first search), используют идеи поиска с возвратами, в том числе следующие.

1. Формируется список неисследованных состояний (NSL), для того чтобы иметь

возможность возвратиться к любому из них.

2. Поддерживается список «неудачных» состояний (ОЕ), чтобы оградить алгоритм от

проверки бесполезных путей.

3. Поддерживается список узлов (SL) текущего пути, который возвращается по достижении цели.

4. Каждое новое состояние проверяется на вхождение в эти списки, чтобы предотвра­-

тить зацикливание.

в следующем разделе рассматриваются алгоритмы с использованием списков, по­добные алгоритму поиска с возвратами. Эти алгоритмы, среди которых поиск в глубину, поиск в ширину и поиск по первому наилучшему совпадению, отличаются от по­иска с возвратами более гибкими средствами и стратегиями поиска.

Определив направление поиска (от данных или от цели), алгоритм поиска должен оп­ределить порядок исследования состояний дерева или графа. В этом разделе рассматри­ваются два возможных варианта последовательности обхода узлов графа: поиск в глубину(depth-fist) и поиск в ширину (breadth-first).

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

Рис. 10.10. Граф, демонстрирующий работу алгоритмов поиска в глубину и в ширину

При поиске в глубинупосле исследования состояния сначала необходимо оценить все его потомки и их по­томки, а затем исследовать любую из вершин-братьев. Поиск в глубину по возможности уг­лубляется в область поиска. Если дальнейшие потомки состояния не найдены, рассматрива­ются вершины-братья. Поиск в глубину исследует состояния графа на рис. 10.10 в таком по­рядке: А, В, Е, К, S, L, Т, F, М, С, G, N, Н, О, Р,U, D, I, Q, J, R.

Поиск в ширину, напротив, исследует пространство состояний по уровням, один за другим. И только если состояний на данном уровне больше нет, алгоритм переходит к следующему уровню. При поиске в ширину на графе из рис. 10.10. состояния рассматри­ваются в таком порядке: А, В, С, D, Е, F, G, Н, 1, J, К, L, М, N, О, Р, Q, R, S, Т, U.

Поиск в ширину и в глубину осуществляется с использованием списков open и closed, позво­ляющих отслеживать продвижение в пространстве состояний. Список open, подобно NSLв алгоритме поиска с возвратами, содержит сгенерированные состояния, потомки которых еще не были исследованы. Порядок удаления состояний из списка ореп опре­деляет порядок поиска. В список closed заносятся уже исследованные состояния. Спи­сок closed объединяет списки ОЕ и SL, используемые в алгоритме поиска с возвратами.