оценить( [Верш/С | ВершиныСтоим], Деревья) :-
h( Верш, H), F is С + H,
оценить( ВершиныСтоим, Деревья1),
встав( лист( Верш, F, С), Деревья1, Деревья).
% "всереш" проверяет, все ли деревья в списке "решены"
всереш([]).
всереш( [Дер | Деревья] ) :-
реш( Дер),
всереш( Деревья).
реш( решдер( _, _, _ ) ).
реш( решлист( _ , _) ).
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, P)
означающего, что между городами Гор1
и Гор2
существует непосредственная связь, а соответствующее расстояние равно P
. Далее, мы допустим, что существует отношение
клпункт( Гор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
Читать дальше