2015-07-14
352
Будем представлять пространство состояний при помощи отношения предиката
После (Х,Y)
которое истинно тогда, когда в пространстве состояний существует разрешенный ход из вершины Х в вершину Y. Будем говорить, что Y - это преемник вершины Х. Если с ходом связаны их стоимости, мы добавим третий аргумент, стоимость хода:
После (X,Y,S)
Эти отношения можно задавать в программе явным образом при помощи набора соответствующих фактов. Однако такой подход непрактичен и нереален для тех типичных случаев, когда пространство состояний устроено достаточно сложно.
Поэтому отношение следования «после ()» обычно определяется при помощи правил
вычисления вершин - приемников
некоторой заданной вершины
Другим вопросом является способ представления состояний, т.е. самих вершин. Это представление должно быть компактно, но в то же время обеспечивать эффективное выполнение необходимых операций:
операций вычисления вершин - приемников.
а возможно и стоимостей соответвующих ходов.
Для рассматриваемого примера проблемную ситуацию (состояние) можно представить как список столбиков. При этом каждый столбик представляется списком кубиков, из которых он составлен. Кубики упорядочены в списке так, что самый верхний находится во главе списка. «Пустые» столбики изображаются как пустые списки.
Тогда исходную ситуацию (состояние) можно записать как терм вида:
[[c,a,b],[ ],[ ]]
Целевая ситуация – это любая конфигурация кубиков, содержащая столбик, составленный из всех кубиков в нужном порядке. Таких состояний три:
[[a,b,c],[ ],[ ]],
[[ ],[a,b,c],[ ]],
[[ ],[ ],[a,b,c]].
Отношения следования может быть описано на Прологе, исходя из следующего правила:
«Состояние 2» есть приемник «Состояния 1» если в «состоянии 1» имеется два столбика «Столб 1» и «Столб 2», такие, что верхний кубик из «Столб 1» можно поставить сверху на «Столб 2» и получить при этом «Состояние 2».
При этом целевое условие может быть также представлено в виде правила:
Цель(состояние):-принадлежит([a,b,c],Состояние)
Т. е. нашей целью является поиск такой проблемной ситуации, представляющей собой список столбиков, в которой один из столбиков содержит список кубиков в назначенном нами порядке.
