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



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

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

line();

/*  Процедуры, отражающие специфику головоломки
"игра в восемь".
Текущая ситуация представлена списком положений фишек;
первый элемент списка соответствует пустой клетке.
Пример:

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.
                    %Возврат с переходом к следующей клетке

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

line();



Содержание раздела