Неизвестно - Prolog

упоряд( [Ф2 | С], Первый, Уп2),

Уп is Уп1 + Уп2.

упоряд( [Последний], Первый, Уп) :-

очки( Последний, Первый, Уп).

очки( 2/2, _, 1) :- !. % Фишка в центре - 1 очко

очки( 1/3, 2/3, 0) :- !.

% Правильная последовательность - 0 очков

очки( 2/3, 3/3, 0) :- !.

очки( 3/3, 3/2, 0) :- !.

очки( 3/2, 3/1, 0) :- !.

очки( 3/1, 2/1, 0) :- !.

очки( 2/1, 1/1, 0) :- !.

очки( 1/1, 1/2, 0) :- !.

очки( 1/2, 1/3, 0) :- !.

очки( _, _, 2). % Неправильная последовательность

цель( [2/2, 1/3, 2/3, 3/3, 3/2, 3/1, 2/1, 1/1, 1/2] ).

% Стартовые позиции для трех головоломок

старт1( [2/2, 1/3, 3/2, 2/3, 3/3, 3/1, 2/1, 1/1, 1/2] ).

% Требуется для решения 4 шага

старт2( [2/1, 1/2, 1/3, 3/3, 3/2, 3/1, 2/2, 1/1, 2/3] ).

% 5 шагов

старт3( [2/2, 2/3, 1/3, 3/1, 1/2, 2/1, 3/3, 1/1, 3/2] ).

% 18 шагов

% Отображение решающего пути в виде списка позиций на доске

показреш( [ ]).

показреш( [ Поз | Спис] :-

показреш( Спис),

nl, write( '---'),

показпоз( Поз).

% Отображение позиции на доске

показпоз( [S0, S1, S2, S3, S4, S5, S6, S7, S8] ) :-

принадлежит Y, [3, 2, 1] ), % Порядок Y-координат

nl, принадлежит X, [1, 2, 3] ), % Порядок Х-координат

принадлежит( Фшк-X/Y,

[' '-S0, 1-S1, 2-S2, 3-S3, 4-S4, 5-S5, 6-S6, 7-S7, 8-S8]),

write( Фшк),

fail. %Возврат с переходом к следующей клетке

показпоз( _ ).

Рис. 12. 6. Процедуры для головоломки "игра в восемь",

предназначенные для использования программой поиска

с предпочтением рис. 12.3.

Существуют три отношения, отражающих специфику конкретной задачи:

после( Верш, Верш1, Ст)

Это отношение истинно, когда в пространстве состояний существует дуга стоимостью Стмежду вершинами Верши Верш1.

цель( Верш)

Это отношение истинно, если Верш- целевая вершина.

h( Верш, Н)

Здесь Н- эвристическая оценка стоимости самого дешевого пути из вершины Вершв целевую вершину.

В данном и следующих разделах мы определим эти отношения для двух примеров предметных областей: для головоломки "игра в восемь" (описанной в разделе 11.1) и планирования прохождения задач в многопроцессорной системе.

Отношения для "игры в восемь" показаны на рис. 12.6. Вершина пространства состояний - это некоторая конфигурация из фишек на игровой доске. В программе она задается списком текущих положений фишек. Каждое положение определяется парой координат X/Y. Элементы списка располагаются в следующем порядке:

(1) текущее положение пустой клетки,

(2) текущее положение фишки 1,

(3) текущее положение фишки 2,

...

Целевая ситуация (см. рис. 11.3) определяется при помощи предложения

цель( [2/2, 1/3, 2/3, 3/3, 3/2, 3/1, 2/1, 1/1, 1/2] ).

Имеется вспомогательное отношение

расст( K1, K2, Р)

Р - это "манхеттеновское расстояние" между клетками Kl и K2, равное сумме двух расстояний между Kl и K2: расстояния по горизонтали и расстояния по вертикали.

Рис. 12. 7. Три стартовых позиции для "игры в восемь": (а) решение требует

4 шага; (b) решение требует 5 шагов; (с) решение требует 18 шагов.

Наша задача - минимизировать длину решения, поэтому мы положим стоимости всех дуг пространства состояний равными 1. В программе рис. 12. 6. даны также определения трех начальных позиций (см. рис. 12.7).

Эвристическая функция h , запрограммирована как отношение

h( Поз, Н)

Поз- позиция на доске; Нвычисляется как комбинация из двух оценок:

(1) сумрасст- "суммарное расстояние" восьми фишек, находящихся в позиции Поз, от их положений в целевой позиции. Например, для начальной позиции, показанной на рис. 12.7(а), сумрасст= 4.

(2) упоряд- степень упорядоченности фишек в текущей позиции по отношению к тому порядку, в котором они должны находиться в целевой позиции. Величина упорядвычисляется как сумма очков, приписываемых фишкам, согласно следующим правилам:

фишка в центральной позиции - 1 очко;

фишка не в центральной позиции, и непосредственно за ней следует (по часовой стрелке) та фишка, какая и должна за ней следовать в целевой позиции - 0 очков.

то же самое, но за фишкой следует "не та" фишка - 2 очка.

Например, для начальной позиции рис.12.7(а),