Реализация поиска на графах
При решении задач путем поиска на основе данных либо от цели требуется найти путь от начального состояния к целевому на графе пространства состояний. Последовательность дуг этого пути соответствует упорядоченной последовательности этапов решения задачи. Модуль решения задачи должен безошибочно двигаться прямо к цели, запоминая путь движения. Решатель должен рассматривать различные пути до тех пор, пока не достигнет цели. Поиск с возвратами - это метод систематической проверки различных путей в пространстве состояний. Это один из первых алгоритмов поиска в информатике.
Алгоритм поиска с возвратами запускается из начального состояния и следует по некоторому пути до тех пор, пока не достигнет цели либо не упрется в тупик. Если цель достигнута, поиск завершается, и в качестве решения задачи возвращается путь к цели. Если же поиск привел в тупиковую вершину, то алгоритм возвращается в ближайшую из пройденных вершин и исследует все ее вершины-братья, а затем спускается по одной из ветвей, ведущих от вершины-брата. Этот процесс описывается следующим рекурсивным правилом.
Алгоритм работает до тех пор, пока не достигнет цели либо не исследует все пространство состояний. На рис.7 изображен процесс поиска с возвратами в гипотетическом пространстве состояний.
Рисунок 7 - Поиск с возвратами в гипотетическом пространстве состояний
Пунктирные стрелки в дереве указывают направление процесса поиска в пространстве состояний (вниз или вверх). Числа возле каждой вершины указывают порядок их посещения. Ниже приведем фрагмент алгоритма поиска с возвратами. В нем используются три списка, позволяющих запоминать путь от узла к узлу в пространстве состояний.
SL (State List ) - список исследованных состояний рассматриваемого пути. Если цель уже найдена, SL содержит список состояний пути решения.
NSL ( New State List ) - список новых состояний, он содержит вершины, подлежащие рассмотрению, т.е. список вершин, потомки которых еще не были порождены и рассмотрены.
DЕ (Dead Ends) - список тупиков, т.е. список вершин, потомки которых уже были исследованы, но не привели к цели. Если состояние из этого списка снова встречается в процессе поиска, то оно обнаруживается в списке DЕ и исключается из рассмотрения.
При описании алгоритма поиска с возвратами на графах общего вида (не только для деревьев) необходимо учитывать возможность повторного появления состояний, чтобы избежать их повторного рассмотрения, а также петель, ведущих к зацикливанию алгоритма поиска пути. Это обеспечивается проверкой каждой вновь порожденной вершины на ее вхождение в один из трех вышеуказанных списков. Если новое состояние обнаружится хотя бы в одном из двух списков SL или DE, значит, оно уже рассматривалось, и его следует проигнорировать.
Обозначим текущее состояние при поиске с возвратами через CS (current state). Состояние CS всегда равно последнему из состояний, занесенных в список SL, и представляет "фронтальную" вершину на построенном в данный момент пути. Правила вывода, ходы в игре или иные соответствующие операторы решения задачи упорядочиваются и применяются к CS. В результате возникает упорядоченное множество новых состояний, потомков CS. Первый из этих потомков объявляется новым текущим состоянием, а остальные заносятся в список новых состояний NSL для дальнейшего изучения. Новое текущее состояние заносится в список состояний SL, и поиск продолжается. Если текущее состояние CS не имеет потомков, то оно удаляется из списка состояний SL (именно в этот момент алгоритм "возвращается назад"), и исследуется какой-либо из оставшихся потомков его предка в списке состояний SL.
Алгоритм поиска с возвратами на графе из рис.7 работает следующим образом.
Инициализируем списки.
Поиск с возвратами в данном случае является поиском на основе данных, при котором корень дерева связывается с начальным состоянием, а потомки узлов анализируются для построения пути к цели. Этот же алгоритм можно интерпретировать и как поиск от цели. Для этого целевую вершину следует взять в качестве корня дерева и анализировать совокупность предков для нахождения пути к начальному состоянию.
Поиск с возвратами - это алгоритм поиска на графе пространства состояний. Алгоритмы поиска на графах, которые будут рассматриваться далее, включая поиск в глубину, поиск в ширин, используют идеи поиска с возвратами, в том числе следующие.
1.Формируется список неисследованных состояний (NSL), для того чтобы иметь возможность возвратиться к любому из них.
2.Поддерживается список "неудачных" состояний (DE), чтобы оградить алгоритм от проверки бесполезных путей.
3.Поддерживается список узлов (SL) текущего пути, который возвращается по достижении цели.
4.Каждое новое состояние проверяется на вхождение в эти списки, чтобы предотвратить зацикливание.
В следующем подразделе рассматриваются алгоритмы с использованием списков, подобные алгоритму поиска с возвратами. Эти алгоритмы, среди которых поиск в глубину, поиск в ширину, отличаются от поиска с возвратами более гибкими средствами и стратегиями поиска.