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

% расширяет Дер в пределах ограничения Предел
% и порождает НовДер с "решающим статусом" ЕстьРеш.

% Случай 1: выход за ограничение
расширить( Дер, Предел, Дер, нет) :-
 f( Дер, F), F > Предел, !. % Выход за ограничение

% В остальных случаях F ≤ Предел
% Случай 2: встретилась целевая вершина
расширить( лист( Верш, F, С), _, решлист( Верш, F), да) : -
 цель( Верш), !.

% Случай 3: порождение преемников листа
расширить( лист( Верш, F,C), Предел, НовДер, ЕстьРеш) :-
 расшлист( Верш, С, Дер1), !,
 расширить( Дер1, Предел, НовДер, ЕстьРеш);
 ЕстьРеш = никогда, !. % Нет преемников, тупик

% Случай 4: расширить дерево
расширить( дер( Верш, F, С, Поддеревья),
 Предел, НовДер, ЕстьРеш) :-
 Предел1 is Предел - С,
 расширспис( Поддеревья, Предел1, НовПоддер, ЕстьРеш1),
 продолжить( ЕстьРеш1, Верш, С, НовПоддер, Предел,
 НовДер, ЕстьРеш).

% расширспис( Деревья, Предел, Деревья1, ЕстьРеш)
% расширяет деревья из заданного списка с учетом
% ограничения Предел и выдает новый список Деревья1
% с "решающим статусом" ЕстьРеш.
расширспис( Деревья, Предел, Деревья1, ЕстьРеш) :-
 выбор( Деревья, Дер, ОстДер, Предел, Предел1),
 расширить( Дер, Предел1, НовДер, ЕстьРеш1),
 собрать( ОстДер, НовДер, ЕстьРеш1, Деревья1, ЕстьРеш).

% "продолжить" решает, что делать после расширения
% списка деревьев
продолжить( да, Верш, С, Поддеревья, _,
 решдер( Верш, F, Поддеревья), да): -
 оценка( Поддеревья, H), F is С + H, !.
продолжить( никогда, _, _, _, _, _, никогда) :- !.
продолжить( нет, Верш, С, Поддеревья, Предел,
 НовДер, ЕстьРеш) :-
 оценка( Поддеревья, H), F is С + H, !,
 расширить( дер( Верш, F, С, Поддеревья), Предел,
 НовДер, ЕстьРеш).

% "собрать" соединяет результат расширения дерева со списком деревьев
собрать( или : _, Дер, да, Дер, да):- !. % Есть решение ИЛИ-списка
собрать( или : ДД, Дер, нет, или : НовДД, нет) :-
 встав( Дер, ДД, НовДД), !. % Нет решения ИЛИ-списка
собрать( или : [], _, никогда, _, никогда) :- !.
 % Больше нет кандидатов
собрать( или:ДД, _, никогда, или:ДД, нет) :- !.
 % Есть еще кандидаты
собрать( и : ДД, Дер, да, и : [Дер Э ДД], да ) :-
 всереш( ДД), !. % Есть решение И-списка
собрать( и : _, _, никогда, _, никогда) :- !.
 % Нет решения И-списка
собрать( и : ДД, Дер, ДаНет, и : НовДД, нет) :-
 встав( Дер, ДД, НовДД), !. % Пока нет решения И-списка

% "расшлист" формирует дерево из вершины и ее преемников
расшлист( Верш, С, дер( Верш, 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):