Реализация поиска на графах
При решении задач путем поиска на основе данных либо от цели требуется найти путь от начального состояния к целевому на графе пространства состояний. Последовательность дуг этого пути соответствует упорядоченной последовательности этапов решения задачи. Если решатель задачи имеет в своем распоряжении оракула или иное непогрешимое средство предсказания для построения пути решения, то и поиска не требуется. Модуль решения задачи должен безошибочно двигаться прямо к цели, запоминая путь движения. Поскольку для интересных задач оракулов не существует, решатель дол-1кен рассматривать различные пути до тех пор, пока не достигнет цели. Поиск с возвратами (backtracking)– это метод систематической проверки различных путей в пространств состояний.
Начнем рассмотрение алгоритмов с поиска с возвратами, поскольку это один из первых алгоритмов поиска в информатике, который допускает естественную реализацию в рекурсивной среде, ориентированной на использование стеков (раздел 5.1). Упрощенная версия поиска с возвратами на примере поиска в глубину (раздел 5.1) будет реализована в части VI на языках LISP и PROLOG.
Алгоритм поиска с возвратами запускается из начального состояния и следует по некоторому пути до тех пор, пока не достигнет цели либо не упрется в тупик. Если цель достигнута, поиск завершается, и в качестве решения задачи возвращается путь к цели. Если же поиск привел в тупиковую вершину, то алгоритм возвращается в ближайшуюиз пройденных вершин и исследует ее вершины-братья, а затем спускается по одной из ветвей, ведущих от вершины-брата. Этот процесс описывается следующим рекурсивным правилом.
Если исходное состояние S не удовлетворяет требованиям цели, то из списка его потомков, выбираем первый Schild1 этой вершине рекурсивно применяем процедуру поиска с возвратами. Если в результате поиска с возвратами в подграфе с корнем Schild1 цель не обнаружена, то повторяем процедуру для вершины-брата Schild2. Эта процедура продолжается до тех пор, пока один из потомков рассматриваемой вершины-брата не окажется целевым узлом, либо не выяснится, что рассмотрены уже все возможные потомки (все вершины-братья). Если же ни одна из вершин-братьев вершины S не привела к цели, возвращаемся к предку вершины S и повторяем процедуру с вершиной-братом S и т.д.
Алгоритм работает до тех пор, пока не достигнет цели либо не исследует все пространство состояний. На рис. 3.12 изображен процесс поиска с возвратами в гипотетическом пространстве состояний. Пунктирные стрелки в дереве указывают направление процесса поиска в пространстве состояний (вниз или вверх). Числа возле каждой вершины указывают порядок их посещения. Ниже приведем алгоритм поиска с возвратами. В нем используются три списка, позволяющих запоминать путь от узла к узлу в пространстве состояний.
SL (State List) – список исследованных состояний рассматриваемого пути. Если цель уже найдена, то SL содержит список состояний пути решения.
NSL (New State List) – список новых состояний, он содержит вершины, подлежащие рассмотрению, т.е. список вершин, потомки которых еще не были порождены и рассмотрены.
DE (Dead Ends) – список тупиков, т.е. список вершин, потомки которых уже были исследованы, но не привели к цели. Если состояние из этого списка снова встречается в процессе поиска, то оно обнаруживается в списке DE и исключается из рассмотрения.
При описании алгоритма поиска с возвратами на графах общего вида (не только для деревьев) необходимо учитывать возможность повторного появления состояний, чтобы избежать их повторного рассмотрения, а также петель, ведущих к зацикливанию алгоритма поиска пути. Это обеспечивается проверкой каждой вновь порожденной вершины на ее вхождение в один из трех вышеуказанных списков. Если новое состояние обнаружится хотя 6ы в одном из двух списков SZT или DE, значит, оно уже рассматривалось, и его следует проигнорировать.
Поиск с возвратами в данном случае является поиском на основе данных, при котором корень дерева связывается с начальным состоянием, а потомки узлов анализируются для построения пути к цели. Этот же алгоритм можно интерпретировать и как поиск от цели. Для этого целевую вершину следует взять в качестве корня дерева и анализировать совокупность предков для нахождения пути к начальному состоянию. При использовании цели вида 2 (см. подраздел 3.1.2) этот алгоритм должен определить целевое состояние, исследуя путь для SL.
Поиск с возвратами (backtrack) – это алгоритм поиска на графе пространства состояний. Алгоритмы поиска на графах, которые будут рассматриваться далее, включая поиск в глубину (depth-first), поиск в ширину (breadth-first) и поиск по первому наилучшему совпадению (best-first search), используют идеи поиска с возвратами, в том числе следующие.
1. Формируется список неисследованных состояний (NSL), для того чтобы иметь возможность возвратиться к любому из них.
2. Поддерживается список " неудачных" состояний (DE), чтобы оградить алгоритм от проверки бесполезных путей.

3. Поддерживается список узлов (SL) текущего пути, который возвращается по достижении цели.
4. Каждое новое состояние проверяется на вхождение в эти списки, чтобы предотвратить зацикливание.
В следующем разделе рассматриваются алгоритмы с использованием списков, подобные алгоритму поиска с возвратами.Эти алгоритмы, среди которых поиск в глубину, поиск в ширину и поиск по первому наилучшему совпадению(глава 4), отличаются от поиска с возвратамиболее гибкими средствами и стратегиями поиска.
SL≠ [ ]&
& CS=
=FIRST(SL)
| CS –> DL
DEL(SL)
DEL(NSL)
|
CS – текущее состояние
SL – список текущих состояний
NSL – список открытых, но не просмотренных состояний
PL – список тупиковых состояний
FIRST(…) – взятие первого элемента списка
→ – занесение элементов в список
DEL – удаление первого элемента списка
Выделяются 2 блока операторов, связанных с прямым движением в глубину пространства, при этом длина SL будет увеличиваться, и возвратным движением с укорачивающимся SL.
Рис. 36.
|