Читаем Prolog полностью

        реш( решлист( _ , _) ).

        f( Дер, F) :-                                                              % Извлечь F-оценку дерева

                arg( 2, Дер, F),  !.                                            % F - это 2-й аргумент Дер

% встав( Дер, ДД, НовДД) вставляет Дер в список

% деревьев ДД; результат - НовДД

        встав( Д, [ ], [Д] ) :-   !.

        встав( Д, [Д1 | ДД], [Д, Д1 | ДД] ) :-

                реш( Д1),  !.

        встав( Д, [Д1 | ДД], [Д1 | ДД1] ) :-

                реш( Д),

                встав( Д, ДД, ДД1),  !.

        встав( Д, [Д1 | ДД], [Д, Д1 | ДД] ) :-

                f( Д, F), f( Д1, F1), F=< F1,  !.

        встав( Д, [Д1 | ДД], [ Д1 | ДД1] ) :-

                встав( Д, ДД, ДД1).

% "оценка" находит "возвращенную" F-оценку И / ИЛИ-списка деревьев

        оценка( или :[Дер | _ ], F) :-

                                        % Первое дерево ИЛИ-списка - наилучшее

                f( Дер, F),  !.

        оценка( и :[ ], 0) :-   !.

        оценка( и : [Дер1 | ДД], F) :-

                f( Дер1, F1),

                оценка( и : ДД, F2),

                F is F1 + F2,  !.

        оценка( Дер, F) :-

                f( Дер, F).

% Отношение выбор( Деревья, Лучшее, Остальные, Предел, Предел1):

% Остальные - И / ИЛИ-список Деревья без его "лучшего" дерева

% Лучшее; Предел - ограничение для Списка Деревья, Предел1 -

% ограничение для дерева Лучшее

        выбор( Оп : [Дер], Дер, Оп : [ ], Предел, Предел) :-  !.

                                                               % Только один кандидат

        выбор( Оп : [Дер | ДД], Дер, Оп : ДД, Предел, Предел1) :-

                оценка( Оп : ДД, F),

                ( Оп = или,  !,  мин( Предел, F, Предел1);

                Оп = и, Предел1 is Предел - F).

        мин( А, В, А) :- А < В,   !.

        мин( А, В, В).

Рис. 13. 12.  Программа поиска с предпочтением в И / ИЛИ-графе.

Еще одна процедура

        собрать( ОстДер, НовДер, ЕстьРеш1, НовДеревья, ЕстьРеш)

связывает между собой несколько объектов, с которыми работает расширспис. НовДер - это расширенное дерево, взятое из списка деревьев процедуры расширспис, ОстДер - остальные, не измененные деревья из этого списка, а ЕстьРеш1 указывает на "решающий статус" дерева НовДер. Процедура собрать имеет дело с несколькими случаями в зависимости от значения ЕстьРеш1, а также от того, является ли список деревьев И-списком или ИЛИ-списком. Например, предложение

        собрать( или : _, Дер, да, Дер, да).

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

Для отображения решающего дерева можно определить процедуру, аналогичную процедуре отобр (рис. 13.8). Оставляем это читателю в качестве упражнения

.

13. 4. 3.    Пример отношений, определяющих конкретную задачу: поиск маршрута

Давайте теперь сформулируем задачу нахождения маршрута как задачу поиска в И / ИЛИ-графе, причем сделаем это таким образом, чтобы наша формулировка могла бы быть непосредственно использована процедурой и_или рис. 13.12. Мы условимся, что карта дорог будет представлена при помощи отношения

        связь( Гор1, Гор2, Р)

означающего, что между городами Гор1 и Гор2 существует непосредственная связь, а соответствующее расстояние равно Р.   Далее, мы допустим, что существует отношение

        клпункт( Гор1-Гор2, Гор3)

имеющее следующий смысл: для того, чтобы найти маршрут из Гор1 в Гор2, следует рассмотреть пути, проходящие через Гор3 ( Гор3 - это "ключевой пункт" между Гор1 и Гор2). Например, на карте рис. 13.1  f   и  g  - это ключевые пункты между  а   и  z:

        клпункт( a-z, f).                 клпункт( a-z, g).

Мы реализуем следующий принцип построения маршрута:

Для того, чтобы найти маршрут между городами   X  и  Z,  необходимо:

    (1)        если между   X  и  Z  имеются ключевые пункты  Y1,   Y2,  ...,  то найти один из путей:

путь из  X  в  Z  через  Y1,  или

путь из  X  в  Z  через  Y2,  или

...

    (2)        если между   X  и  Z  нет ключевых пунктов, то найти такой соседний с  X   город  Y,  что существует маршрут из  Y  в  Z.

Таким образом, мы имеем два вида задач, которые мы будем представлять как

    (1)        X-Z                             найти маршрут из  X  в  Z

    (2)        X-Z через Y               найти маршрут из  X  в  Z,  проходящий через   Y