Поиск с возвратами

Стратегии поиска в пространствах состояний

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

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

Дата добавления: 2014-01-07