Поиск с возвратами
Стратегии поиска в пространствах состояний
Под стратегией поиска понимается алгоритм исследования пространства состояний при поиске пути от начального состояния к целевому, допускающий программную реализацию. Поэтому граф должен задаваться отношениями так, что соответствующие им предикаты можно было бы использовать в программе для представления множеств узлов и связывающих их путей.
Эти отношения могут быть представлено в турбо- прологовской программе явно, в виде множества фактов. Но такой вариант при наличии пространства состояний с сколько-нибудь значительной сложностью может оказаться практически неприемлемым или невозможным. Поэтому, чаще всего отношения определения узлов и их преемников задается системой правил, содержащих переменные (см. Пример 5.1.1. ).
В дальнейшем под раскрытием узла (вершины) будем понимать построение всех его преемников- потомков «первого поколения».
Стратегия поиска с возвратами использует в общем случае три списка вершин : список вершин, представляющий ациклический путь от текущей вершины до начальной -C;
список новых (не исследованных ранее) состояний ,соответствующих текущему –N;
список вершин – тупиков (среди их потомков целевой вершины не оказалось)- T.
Алгоритм поиска с возвратами запускается из начального состояния и следует по некоторому пути до тех пор, пока не достигнет цели либо не упрется в тупик. Если цель достигнута, поиск завершается, и в качестве решения задачи возвращается путь к цели. Если же поиск привел в тупиковую вершину, то алгоритм возвращается в ближайшую из пройденных вершин и исследует все ее вершины-братья, а затем спускается по одной из ветвей, ведущих от вершины-брата.
Алгоритм поиска с возвратами.
Присвоить значения: C=[];N = [S],T = [ ], где S –исходная вершина
1. Извлечь первую вершину XизспискаN ; если вершина Xцелевая, поместить ее в начало спискаC , работу закончить, принять в качестве решения (SOL)список C иначе перейти к следующему пункту.
2. Раскрыть X и удалить всех ее потомков принадлежащих хотя бы одному из названных трех списков; перейти к следующему пункту.
3. Если все потомки вершины Xбылиудалены, то удалить ее из списков CиN, поместить вершину X в список Tи, если N = [], констатировать неудачу (решение не найдено), иначеперейти к пункту 1; иначе перейти к следующему пункту.
4. Поместить оставшихся потомков вершиныXв начало списка N и перейти к пункту 1.
Алгоритм работает до тех пор, пока не достигнет цели либо не исследует все пространство состояний. На рис. 5.9. изображен процесс поиска с возвратами в гипотетическом пространстве состояний. Пунктирные стрелки указывают направление процесса поиска в пространстве состояний. Вершины пронумерованы в порядке их обхода до обнаружения целевой вершины G согласно изложенному алгоритму , путь [ A, C, G]является решением задачи.Приведем программу на языке Турбо- Пролог, реализующую этот алгоритм.В дальнейшем для определенности в программах будем использовать данные домена symbol и применять следующие обозначения:
s- тип данных symbol;
l- список с элементами типа s, l= s*;
eq (l, l)- предикат сравнения списков, принимающий истинное значение при совпадении его аргументов и ложное в противном случае;
udob (l, l, l)- предикат удаления элементов второго аргумента, принадлежащих и первому аргументу , принимает истинное значение, если третий аргумент равен результату указанного удаления и ложное в противном случае;
ap (l, l, l)- предикат присоединения первого аргумента в начало второго с помещением результата в третий аргумент
(системы правил определяющих эти три предиката , ввиду их простоты, в программах будут опускаться);
preemn (s, l)- предикат ,определяющий список l – преемников (потомков первого поколения) вершины s;
gs (s)- предикат, задающий целевую вершину
(два последних предиката зависят от решаемой задачи и поэтому их описание в общей программе не может быть приведено);
solve( , …, l) – предикат поиска пути l – решения задачи;
sol – предикат, задающий цель программы.