Prolog
Шрифт:
ЕстьРеш1, ЕстьРеш, Реш).
расширить( _, д( _, _, [ ]), _, _, никогда, _ ) :- !.
% Тупиковое дерево - нет решений
расширить( _, Дер, Предел, Дер, нет, _ ) :-
f( Дер, F), F > Предел. % Рост остановлен
продолжить( _, _, _, _, да, да, Реш).
ЕстьРеш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
к целевой вершине и имеющий стоимость, не превосходящую ограничение Предел (если такая целевая вершина была обнаружена).
Переменные Путь, Дер, и Предел– это "входные" параметры процедуры расширить в том смысле, что при каждом обращении к расширить они всегда конкретизированы. Процедура расширить порождает результаты трех видов. Какой вид результата получен, можно определить по значению индикатора ЕстьРеш следующим образом:
(1) ЕстьРеш = да.
Решение = решающий путь, найденный при расширении дерева Дер с учетом ограничения Предел.
Дер1 = неконкретизировано.
(2) ЕстьРеш = нет
Дер1 = дерево Дер, расширенное до тех пор, пока его f– оценка не превзойдет Предел (см. рис. 12.4).
Решение = неконкретизировано.
(3) ЕстьРеш = никогда.
Дер1 и Решение = неконкретизированы.
В последнем случае Дер является "тупиковой" альтернативой, и соответствующий процесс никогда не будет реактивирован для продолжения просмотра этого дерева. Случай этот возникает тогда, когда f– оценка дерева Дер не превосходит ограничения Предел, однако дерево не может "расти" потому, что ни один его лист не имеет преемников, или же любой преемник порождает цикл.