Основные понятия. Пространством состояний задачи является граф, вершины которого соответствуют ситуациям, встречающимся в задаче (" проблемные ситуации")

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

Пространство состояний задачи определяет "правила игры":

- вершины пространства состояний соответствуют ситуациям;

- дуги соответствуют разрешенным ходам или действиям, или шагам решения задачи.

Конкретная задача определяется: пространством состояний; стартовой вершиной; целевым условием (т. е. условием, к выполнению которого нужно стремиться).

Целевыми называются вершины, удовлетворяющие целевым условиям.

Каждому разрешенному ходу или действию можно приписать его стоимость. В тех случаях, когда каждый ход имеет стоимость, мы заинтересованы в отыскании решения минимальной стоимости.

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

Будем представлять пространство состояний при помощи отношения after(X,Y), которое истинно тогда, когда в пространстве состояний существует разрешенный ход из вершины X в вершину Y. Будем говорить, что Y – это преемник вершины X. Если с ходами связаны их стоимости, мы добавим третий аргумент, стоимость хода C: after(X,Y,C).

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

Пример 1. Задача манипулирования кубиками.

Проблемная ситуация - список столбиков. Каждый столбик - список кубиков, из которых он составлен. Кубики упорядочены в списке таким образом, что самый верхний кубик находится в голове списка. "Пустые" столбики изображаются как пустые списки.

Отношение следования вытекает из правила:

Ситуация Sit2 - преемник ситуации Sit1, если в Sit1 имеется два столбика Stolb1 и Stolb2 такие, что верхний кубик из Stolb1 можно поставить сверху на Stolb2 и получить тем самым Sit2.

Поскольку все ситуации - списки столбиков, правило транслируется на Пролог так:

after(Stolbs,[Stolb1, [Up1|Stolb2],Rest]):-

delete([Up1|Stolb1],Stolbs,Stolbs1),

delete(Stolb2,Stolbs1,Rest).

delete(X,[X|L],L).

delete(X,[Y|L],[Y|L1]):- delete(X,L,L1).

Здесь:

- Stolbs - множество столбиков в ситуации Sit1;

- Stolbs1 - множество столбиков без первого столбика;

- Rest - множество столбиков без первого и второго.

Целевое условие в данном примере имеет вид:

goal(Sit):- member([a,b,c],Sit).

Алгоритм поиска программируется как отношение

solve(Start,Solution),

где

- Start - стартовая вершина пространства состояний,

- Solution - путь, ведущий из вершины Start в любую целевую вершину.

Для конкретного примера обращение к Пролог- системе имеет вид:

solve([[c,a,b],[],[]],Solution).

Исходная ситуация

[[c,a,b],[],[]].

Целевые ситуации:

[[a,b,c],[],[]]

[[],[a,b,c],[]]

[[],[],[a,b,c]]

Список Solution представляет собой план преобразования исходного состояния в состояние, в котором три кубика поставлены друг на друга в указанном порядке: [a,b,c].