При решении задач путем поиска на основе данных либо от цели требуется найти путь от начального состояния к целевому на графе пространства состояний. Последовательность дуг этого пути соответствует упорядоченной последовательности этапов решения задачи. Если решатель задачи имеет в своем распоряжении оракула или иное непогрешимое средство предсказания для построения пути решения, то и поиска не требуется. Модуль решения задачи должен безошибочно двигаться прямо к цели, запоминая путь движения. Поскольку для интересных задач оракулов не существует, решатель дол-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), отличаются от поиска с возвратамиболее гибкими средствами и стратегиями поиска.
CS –> DL
DEL(SL)
DEL(NSL)
|
CS – текущее состояние
SL – список текущих состояний
NSL – список открытых, но не просмотренных состояний
PL – список тупиковых состояний
FIRST(…) – взятие первого элемента списка
→ – занесение элементов в список
DEL – удаление первого элемента списка
Выделяются 2 блока операторов, связанных с прямым движением в глубину пространства, при этом длина SL будет увеличиваться, и возвратным движением с укорачивающимся SL.
Рис. 36.