Неизвестно - Prolog

(3) ЕстьРеш = никогда: Дерне содержит решения.

В зависимости от случая Дер1- это либо решающее дерево, либо Дер, расширенное до момента перехода через Предел; если ЕстьРеш = никогда, то переменная Дер1неинициализирована.

Процедура

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

аналогична процедуре расширить. Так же, как и в процедуре расширить, Пределзадает ограничение на рост дерева, а ЕстьРеш- это индикатор, указывающий, каков результат расширения ("да", "нет" или "никогда"). Первый аргумент - это, на этот раз, список деревьев (И-список или ИЛИ-список):

Деревья = или:[Д1, Д2, ...] или

Деревья = и : [Д1, Д2, ...]

Процедура расширсписвыбирает из списка Деревьянаиболее перспективное дерево (исходя из F -оценок). Так как деревья в списке упорядочены, таким деревом является первый элемент списка. Наиболее перспективное дерево подвергается расширению с новым ограничением Предел1. Значение Предел1зависит от Предел, а также от других деревьев списка. Если Деревья- это ИЛИ-список, то Предел1устанавливается как наименьшая из двух величин: Предели F -оценка следующего по "качеству" дерева из списка Деревья. Если Деревья- это И-дерево, то Предел1устанавливается равным Пределминус сумма F -оценок всех остальных деревьев из списка. Значение переменной Деревья1зависит от случая, задаваемого индикатором ЕстьРеш. Если ЕстьРеш = нет, то Деревья1- это то же самое, что и список Деревья, причем наиболее перспективное дерево расширено с учетом ограничения Предел1. Если ЕстьРеш = да, то Деревья1- это решение для всего списка Деревья(найденное без выхода за границы значения Предел). Если ЕстьРеш = никогда, то переменная Деревья1неинициализирована.

Процедура продолжить, вызываемая после расширения списка деревьев, решает, что делать дальше, в зависимости от результата срабатывания процедуры расширить. Эта процедура либо строит решающее дерево, либо уточняет дерево поиска и продолжает процесс его наращивания, либо выдает сообщение "никогда" в случае, когда было обнаружено, что список деревьев не содержит решения.

/* ПРОГРАММА И / ИЛИ-ПОИСКА С ПРЕДПОЧТЕНИЕМ

Эта программа порождает только одно решение. Гарантируется, что это решение самое дешевое при условии, что используемая эвристическая функция является нижней гранью реальной стоимости решающих деревьев.

Дерево поиска имеет одну из следующих форм:

дер( Верш, F, С, Поддеревья) дерево-кандидат

лист( Верш, F, C) лист дерева поиска

решдер( Верш, F, Поддеревья) решающее дерево

решлист( Верш, F) лист решающего дерева

С - стоимость дуги, ведущей в Верш

F = С + Н, где Н - эвристическая оценка оптимального решающего дерева с корнем Верш

Список Поддеревья упорядочен таким образом, что

(1) решающие поддеревья находятся в конце списка;

(2) остальные поддеревья расположены в порядке возрастания F-оценок

*/

:- ор( 500, xfx, :).

:- ор( 600, xfx, --->).

и_или( Верш, РешДер) :-

расширить( лист( Верш, 0, 0), 9999, РешДер, да).

% Предполагается, что 9999 > любой F-оценки

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

% расширяет Дер в пределах ограничения Предел

% и порождает НовДер с "решающим статусом" ЕстьРеш.

% Случай 1: выход за ограничение

расширить( Дер, Предел, Дер, нет) :-

f( Дер, F), F > Предел, !. % Выход за ограничение

% В остальных случаях F <= Предел

% Случай 2: встретилась целевая вершина

расширить( лист( Верш, F, С), _, решлист( Верш, F), да) : -

цель( Верш), !.

% Случай 3: порождение преемников листа

расширить( лист( Верш, F,C), Предел, НовДер, ЕстьРеш) :-

расшлист( Верш, С, Дер1), !,

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

ЕстьРеш = никогда, !. % Нет преемников, тупик

% Случай 4: расширить дерево

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

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

Предел1 is Предел - С,

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

продолжить( ЕстьРеш1, Верш, С, НовПоддер, Предел,

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