Назад | Содержание| Вперёд 12. 2. Поиск c предпочтениемприменительно к голо...

Назад | Содержание| Вперёд

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

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

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

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

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

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

Пример:

1 2 3

8 4

7 6 5

1 2 3

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

[2/2, 1/3, 2/3, 3/3, 3/2, 3/1, 2/1, 1/1, 1/2]

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

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

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

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

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

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

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

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

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

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

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

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

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

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

Р is Рх + Py.

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

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

Р is B-A.

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

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

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

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

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

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

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

Н is Р + 3*Уп.

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

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

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

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

Р 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/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(а),

упоряд = 6.

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

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

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

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

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

сумрасст <=h*

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

Упражнение

12. 2. Введите в программупоиска с предпочтением, приведенную на рис. 12.3,подсчет числа вершин, порожденных в процессепоиска. Один из простых способов это сделать -хранить текущее число вершин в виде факта,устанавливаемого при помощи assert.Всегда, когда порождаются новые вершины,уточнять это значение при помощи retract и assert.Проведите эксперименты с различнымиэвристическими функциями задачи "игра ввосемь" с целью оценить их эвристическую силу.Используйте для этого вычисленное количествопорожденных вершин.

Назад | Содержание| Вперёд

Оглавление