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

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

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

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

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

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

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

 G is G0 + С,

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

 F is G + H,

 преемспис( 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) :-

 X =< Y, !.

мин( X, Y, Y).

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

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

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

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

(1) ЕстьРеш = да

Решение = решающий путь, найденный при расширении дерева Дер с учетом ограничения Предел.

Дер1 = неконкретизировано.

(2) ЕстьРеш = нет

Дер1 = дерево Дер, расширенное до тех пор, пока его f-оценка не превзойдет Предел (см. рис. 12.4).

Решение = неконкретизировано.

(3) ЕстьРеш = никогда

Дер1 и Решение = неконкретизированы.

В последнем случае Дер является "тупиковой" альтернативой, и соответствующий процесс никогда не будет реактивирован для продолжения просмотра этого дерева. Случай этот возникает тогда, когда f-оценка дерева Дер не превосходит ограничения Предел, однако дерево не может "расти" потому, что ни один его лист не имеет преемников, или же любой преемник порождает цикл.

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

Дер = д( В, F/G, [Д | ДД ] )

означает следующее. Во-первых, расширению подвергается наиболее перспективное дерево Д. В качестве ограничения этому дереву выдается не Предел, а некоторое, возможно, меньшее значение Предел1, зависящее от f-оценок других конкурирующих поддеревьев ДД. Тем самым гарантируется, что "растущее" дерево — это всегда наиболее перспективное дерево, а переключение активности между поддеревьями происходит в соответствии с их  f-оценками. После того, как самый перспективный кандидат расширен, вспомогательная процедура продолжить решает, что делать дальше, а это зависит от типа результата, полученного после расширения. Если найдено решение, то оно и выдается, в противном случае процесс расширения деревьев продолжается.