Представление пространства состояний в виде базы знаний

Будем представлять пространство состояний при помощи отношения предиката

После (х,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],Состояние)

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

16