Prolog

                                      % Наилучшая f-оценка для

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

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

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

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

             Х =< Y,   !.

        мин( X, Y, Y).

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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