Реализация поиска на графах

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

Начнем рассмотрение алгоритмов с поиска с возвратами, поскольку это один из первых алгоритмов поиска в информатике, который допускает естественную реализацию в рекурсивной среде, ориентированной на использование стеков (раздел 5.1). Упрощенная версия поиска с возвратами на примере поиска в глубину (раздел 5.1) будет реализована в части VI на языках LISP и PROLOG.

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

Если исходное состояние S не удовлетворяет требованиям цели, то из списка его потомков, выбираем первый S_child1 этой вершине рекурсивно применяем процедуру поиска с возвратами. Если в результате поиска с возвратами в подграфе с корнем S_child1 цель не обнаружена, то повторяем процедуру для вершины-брата S_child2. Эта процедура продолжается до тех пор, пока один из потомков рассматриваемой вершины-брата не окажется целевым узлом, либо не выяснится, что рассмотрены уже все возможные потомки (все вершины-братья). Если же ни одна из вершин-братьев вершины 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 – текущее состояние

SL – список текущих состояний

NSL – список открытых, но не просмотренных состояний

PL – список тупиковых состояний

FIRST(…) – взятие первого элемента списка

→ – занесение элементов в список

DEL – удаление первого элемента списка

Выделяются 2 блока операторов, связанных с прямым движением в глубину пространства, при этом длина SL будет увеличиваться, и возвратным движением с укорачивающимся SL.

Рис. 36.