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

собрать( или:ДД, _, никогда, или:ДД, нет) :- !.

  % Есть еще кандидаты

собрать( и : ДД, Дер, да, и : [Дер Э ДД], да ) :-

 всереш( ДД), !.             % Есть решение И-списка

собрать( и : _, _, никогда, _, никогда) :- !.

  % Нет решения И-списка

собрать( и : ДД, Дер, ДаНет, и : НовДД, нет) :-

 встав( Дер, ДД, НовДД), !.  % Пока нет решения И-списка

% "расшлист" формирует дерево из вершины и ее преемников

расшлист( Верш, С, дер( Верш, 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, а также от того, является ли список деревьев И-списком или ИЛИ-списком. Например, предложение

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