Упражнение

12.1.  Определите отношения после, цель и h для задачи поиска маршрута рис. 12.2. Посмотрите, как наш алгоритм поиска с предпочтением будет вести себя при решении этой задачи. 

12.2. Поиск c предпочтением применительно к головоломке "игра в восемь"

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

/* Процедуры, отражающие специфику головоломки

"игра в восемь".

Текущая ситуация представлена списком положений фишек;

первый элемент списка соответствует пустой клетке.

Пример:

 ┌───┐

3│123│ Эта позиция представляется так:

2│8 4│ [2/2, 1/3, 2/3, 3/3, 3/2, 3/1, 2/1, 1/1, 1/2]

1│765│

 └───┘

  123

"Пусто" можно перемещать в любую соседнюю клетку,

т.е. "Пусто" меняется местами со своим соседом.

*/

после( [Пусто | Спис], [Фшк | Спис1], 1) :-

  % Стоимости всех дуг равны 1

 перест( Пусто, Фшк, Спис, Спис1).

  % Переставив Пусто и Фшк, получаем СПИС1

перест( П, Ф, [Ф | С], [П | С] ) :-

 расст( П, Ф, 1).

перест( П, Ф, [Ф1 | С], [Ф1 | C1] ) :-

 перест( П, Ф, С, C1).

расст( X/Y, X1/Y1, P) :-

  % Манхеттеновское расстояние между клетками

 расст1( X, X1, Рx),

 расст1( Y, Y1, Рy),

 P is Рх + Py.

расст1( А, В, P) :-

 P is А-В, P >= 0, ! ;

 P is B-A.

% Эвристическая оценка h равна сумме расстояний фишек

% от их "целевых" клеток плюс "степень упорядоченности",

% умноженная на 3

h( [ Пусто | Спис], H) :-

 цель( [Пусто1 | Цспис] ),

 сумрасст( Спис, ЦСпис, P),

 упоряд( Спис, Уп),

 H is P + 3*Уп.

сумрасст( [], [], 0).

сумрасст( [Ф | С], [Ф1 | C1], P) :-

 расст( Ф, Ф1, P1),

 сумрасст( С, Cl, P2),

 P is P1 + Р2.

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

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

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

 очки( Ф1, Ф2, Уп1),

 упоряд( [Ф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-координат

 принадлежит( Фшк-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( Верш, H)

Здесь 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, P)

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

Рис. 12.7.  Три стартовых позиции для "игры в восемь": (а) решение требует 4 шага; (b) решение требует 5 шагов; (с) решение требует 18 шагов.

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

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

h( Поз, H)

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

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

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

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

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

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

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

упоряд = 6.

Эвристическая оценка H вычисляется как сумма

H = сумрасст + 3 * упоряд

Эта эвристическая функция хорошо работает в том смысле, что она весьма эффективно направляет поиск к цели. Например, при решении головоломок   рис. 12.7(а) и (b) первое решение обнаруживается без единого отклонения от кратчайшего решающего пути. Другими словами, кратчайшие решения обнаруживаются сразу, без возвратов. Даже трудная головоломка  рис. 12.7 (с) решается почти без возвратов. Но данная эвристическая функция страдает тем недостатком, что она не является допустимой: нет гарантии, что более короткие пути обнаруживаются раньше более длинных. Дело в том, что для функции h  условие h ≤ h * выполнено не для всех вершин пространства состояний. Например, для начальной позиции рис. 12.7 (а)

h = 4 + 3 * 6 = 22,    h * = 4

С другой стороны, оценка "суммарное расстояние" допустима: для всех позиций

сумрасст ≤ h *

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