Prolog

Неизвестно

расширспис( Деревья, Предел, Деревья1, ЕстьРеш) :-

выбор( Деревья, Дер, ОстДер, Предел, Предел1),

расширить( Дер, Предел1, НовДер, ЕстьРеш1),

собрать( ОстДер, НовДер, ЕстьРеш1, Деревья1, ЕстьРеш).

% "продолжить" решает, что делать после

расширения

% списка деревьев

продолжить( да, Верш, С, Поддеревья, _,

решдер( Верш, F, Поддеревья), да): -

оценка( Поддеревья, Н), F is С + H, !.

продолжить( никогда, _, _, _, _, _, никогда) :- !.

продолжить( нет, Верш, С, Поддеревья, Предел,

НовДер, ЕстьРеш) :-

оценка( Поддеревья, Н), F is С + Н, !,

расширить( дер( Верш, F, С, Поддеревья), Предел,

НовДер, ЕстьРеш).

% "собрать" соединяет результат расширения дерева со списком деревьев

собрать( или : _, Дер, да, Дер, да):- !. % Есть решение ИЛИ-списка

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

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

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

% Больше нет кандидатов

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

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

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

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

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

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

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

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

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

расшлист( Верш, С, дер( Верш, F,

С, Оп : Поддеревья)) :-

Верш---> Оп : Преемники,

оценить( Преемники, Поддеревья),

оценка( Оп : Поддеревья, Н), F is С + Н.

оценить( [ ], [ ]).

оценить( [Верш/С | ВершиныСтоим], Деревья) :-

h( Верш, Н), F is С + Н,

оценить( ВершиныСтоим, Деревья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) :-

% Первое дерево ИЛИ-списка - наилучшее