ЕстьРеш1, ЕстьРеш, Реш).

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

% Тупиковое дерево - нет решений

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

f( Дер, F), F > Предел. % Рост остановлен

продолжить( _, _, _, _, да, да, Реш).

продолжить( П, д( В, F/G, [Д1, ДД]), Предел, Дер1,

ЕстьРеш1, ЕстьРеш, Реш):-

( ЕстьРеш1 = нет, встав( Д1, ДД, НДД);

ЕстьРеш1 = никогда, НДД = ДД),

опт_f( НДД, F1),

расширить( П, д( В, F1/G, НДД), Предел, Дер1,

ЕстьРеш, Реш).

преемспис( _, [ ], [ ]).

преемспис( G0, [В/С | ВВ], ДД) :-

G is G0 + С,

h( В, Н), % Эвристика h(B)

F is G + Н,

преемспис( G0, ВВ, ДД1),

встав( л( В, F/G), ДД1, ДД).

% Вставление дерева Д в список деревьев ДД с сохранением

% упорядоченности по f-оценкам

встав( Д, ДД, [Д | ДД] ) :-

f( Д, F), опт_f( ДД, F1),

F =< F1, !.

встав( Д, [Д1 | ДД], [Д1 | ДД1] ) ) :-

встав( Д, ДД, ДД1).

% Получение f-оценки

f( л( _, F/_ ), F). % f-оценка листа

f( д( _, F/_, _ ) F). % f-оценка дерева

опт_f( [Д | _ ], F) :- % Наилучшая f-оценка для

f( Д, F). % списка деревьев

опт_f( [ ], Fмакс) :- % Нет деревьев:

мaкс_f( Fмакс). % плохая f-оценка

мин( X, Y, X) :-

Х =< Y, !.

мин( X, Y, Y).

Рис. 12. 3. Программа поиска с предпочтением.

Аргументы процедуры расширить имеют следующий смысл:

Путь Путь между стартовой вершиной и корнем дерева Дер.

Дер Текущее (под)дерево поиска.

Предел Предельное значение f– оценки, при котором допускается расширение.

Дер1 Дерево Дер, расширенное в пределах ограничения Предел;

f– оценка дерева Дер1 больше, чем Предел ( если только при расширении не была обнаружена целевая вершина).

ЕстьРеш Индикатор, принимающий значения "да", "нет" и "никогда".

Решение Решающий путь, ведущий из стартовой вершины через дерево Дер1

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

Переменные Путь, Дер, и Предел– это "входные" параметры процедуры расширить в том смысле, что при каждом обращении к расширить они всегда конкретизированы. Процедура расширить порождает результаты трех видов. Какой вид результата получен, можно определить по значению индикатора ЕстьРеш следующим образом: