Иван Братко - Программирование на языке Пролог для искусственного интеллекта

Существует тривиальная нижняя грань, а именно:

h ( n ) = 0, для всех вершин n пространства состояний.

И при таком значении h допустимость гарантирована. Однако такая оценка не имеет никакой эвристической силы и ничем не помогает поиску. А*-алгоритм при h =0 ведет себя аналогично поиску в ширину. Он, действительно, превращается в поиск в ширину, если, кроме того, положить с ( n , n' )=1 для всех дуг ( n , n' ) пространства состояний. Отсутствие эвристической силы оценки приводит к большой комбинаторной сложности алгоритма. Поэтому хотелось бы иметь такую оценку h , которая была бы нижней гранью h * (чтобы обеспечить допустимость) и, кроме того, была бы как можно ближе к h * (чтобы обеспечить эффективность). В идеальном случае, если бы нам была известна сама точная оценка h *, мы бы ее и использовали: А*-алгоритм, пользующийся h *, находит оптимальное решение сразу, без единого возврата.

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

Если мы хотим применить программу поиска с предпочтением, показанную на рис. 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-координат