Маршрут (Кон_город,Кон_город,[Кон_город])
маршрут (Город,Кон_город,[Город|Путь_до_конца]):-
дорога(город,город_к),
маршрут (Город_к,Кон_город,Путь_до_конца)
Процедуры поиска решений в пространстве состояний удобно рассматривать, используя граф состояний, на котором строится дерево решений.
Пространство состояний - это граф, вершины которого соответствуют ситуациям, встречающимся в задаче (проблемные ситуации), а решение задачи сводится к поиску пути в этом графе.
Процесс решения задачи включает в себя поиск в графе, при этом возникает проблема, как обрабатывать альтернативные пути поиска.
Рассмотрим пример простейшей задачи для интеллектуального робота по переупорядочиванию кубиков, поставленных друг на друга, как показано на рис. 8.7.
Рис. 8.7. Задача
Условия задачи:
1) На каждом шаге можно переставить только один кубик;
2) Кубик можно взять только тогда, когда верхняя поверхность свободна;
3) Кубик можно поставить либо на стол, либо на другой кубик.
Для того, чтобы построить требуемый план, интеллектуальный робот должен отыскать последовательность ходов, реализующих заданную трансформацию.
Эту задачу можно представить как задачу выбора среди множества возможных альтернатив.
В исходной ситуации альтернатива одна — поставить кубик C на стол.
После того как кубик C поставлен на стол, мы имеем три альтернативы:
1)поставить A на стол,
или
2) поставить A на C,
или
3) поставить C на A.
Как показывает рассмотренный пример с задачами такого рода связано два типа понятий:
- проблемные ситуации.
- разрешенные ходы или действия, преобразующие одни проблемные ситуации в другие.
Проблемные ситуации вместе с возможными ходами образуют направленный граф, называемый пространством состояний. Пространство состояний для этой простейшей задачи может быть изображено в виде полного графа представления задачи манипулирования кубиками (рис. 8.8).
Вершины графа соответствуют проблемным ситуациям, а дуги — разрешенным переходам из одних состояний в другие. Задача отыскания плана перемещения эквивалентна задаче построения пути между начальной ситуацией («стартовой» вершиной) и некоторой указанной заранее конечной ситуацией, называемой также целевой вершиной.
Для рассмотренной задачи решением является выделенный на графе путь.
 |
Рис. 8.8. Граф (пространство состояний)
Естественно, что для более сложных задач графическое представление пространства состояний не представляется возможным ввиду его сложности и большой размерности.
Каждому разрешенному ходу или действию можно приписать его стоимость. В рассматриваемой задачи, это будет указывать на то, что один кубик перемещать труднее, чем другие.
В тех случаях, когда каждый ход имеет стоимость, мы заинтересованы в отыскании решения минимальной стоимости.
Стоимость решения- это сумма стоимостей дуг, из которых состоит путь из стартовой вершины в целевую. И он может быть иной, чем в случае, когда стоимости не заданы.
Даже если стоимости не заданы, может возникнуть оптимизационная задача: найти кратчайшее решение.
Но прежде, чем говорить о возможных стратегиях поиска в пространстве состояний, давайте выясним, как можно представить пространство состояний в БЗ, используя для примера язык Пролог.