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