собрать( или : ДД, Дер, нет, или : НовДД, нет) :-
встав( Дер, ДД, НовДД), !. % Нет решения ИЛИ-списка
собрать( или : [], _, никогда, _, никогда) :- !.
% Больше нет кандидатов
собрать( или:ДД, _, никогда, или:ДД, нет) :- !.
% Есть еще кандидаты
собрать( и : ДД, Дер, да, и : [Дер Э ДД], да ) :-
всереш( ДД), !. % Есть решение И-списка
собрать( и : _, _, никогда, _, никогда) :- !.
% Нет решения И-списка
собрать( и : ДД, Дер, ДаНет, и : НовДД, нет) :-
встав( Дер, ДД, НовДД), !. % Пока нет решения И-списка
% 'расшлист' формирует дерево из вершины и ее преемников
расшлист( Верш, С, дер( Верш, F, С, Оп : Поддеревья)) :-
Верш---> Оп : Преемники,
оценить( Преемники, Поддеревья),
оценка( Оп : Поддеревья, H), F is С + H.
оценить( [], []).
оценить( [Верш/С | ВершиныСтоим], Деревья) :-
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. Пример отношений, определяющих конкретную задачу: поиск маршрута
Давайте теперь сформулируем задачу нахождения маршрута как задачу поиска в И/ИЛИ-графе,
