Leaf(N,F, С)

F = C + h(N) Случай 2. Дерево поиска с поддеревьями OR

N) F = C + minF.

tr**(N,F,C,oe:rri,T2,..,])

Случай 3. Дерево поиска с поддеревьями AND

F=C + lFt

tree[ N, F, С, and:[T1 ,T2,...]}

СлучаЙ4. Лист дерева решения

solvedieaf(N, F>

F=C

N}F=C + F,

Случай 5. Дерево решения с корнам в узле OR С

soivedtieef N, F, T)

f=c + 2fi

Случай 6. Дерево решения с корнем в узла AND С

soJvedtree{ N, F, and:[T1,T2,...))

Puc. 13.10. Представление дерева поиска

Глава 13, Декомпозиция задач и графы AND/OR

Список поддеревьев всегда упорядочен в соответствии с возрастающими , F-значениями. Одно из поддеревьев уже может быть решено. Такие поддеревья нахо­дятся в конце списка. Теперь перейдем к описанию программы, приведенной в лис­тинге 13.2. Она имеет следующее отношение верхнего уровня: andor( Mode, SolutionTree)

где Mode - начальный узел поиска. Эта программа формирует дерево решения (если оно существует), такое, что можно надеяться, что это решение — оптимальное. Дей­ствительно ли такое решение имеет минимальную стоимость, зависит от эвристиче­ской функции h, используемой в данном алгоритме. Существует теорема, в которой рассматривается такая зависимость от h. Эта теорема аналогична теореме допустимо­сти, касающейся использования пространства состояний при поиске по заданному критерию, который рассматривался в главе 12 (алгоритм А*). Предположим, что COST(N) обозначает стоимость дерева решения узла N с минимальной стоимостью. Если для каждого узла N в графе AND/OR эвристическая оценка h(N) < COST(N), то отношение апаог гарантирует нахождение оптимального решения. А если функ­ция h не соответствует этому условию, то найденное решение может оказаться неоп­тимальным. Тривиальной эвристической функцией, которая удовлетворяет данному условию допустимости, является h = 0 для всех узлов. Безусловно, что недостаток такой функции состоит в отсутствии эвристического потенциала.

Листинг 13.2. Программа поиска в графе AND/OR по заданному критерию

/* Поиск в графе AND/OR по заданному критерию

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

Дерево поиска представляет собой одно из следующих отношений:

tree( Node, F, С, SubTrees) дерево возможных решений

leaf( Mode, F, С) лист дерева поиска

solvedtree! Node, F, SubTrees) дерево решения

solvedleaf( Mode, F) лист дерева решения

С - это стоимость дуги, направленной к узлу Mode

F = С + Hj где Н - эвристическая оценка оптимального поддерева решения с корнем в узле Node

Список поддеревьев SubTrees всегда упорядочен таким образом; {1) все поддеревья с решениями находятся в конце списке; (2) другие поддеревья [для которых еще не найдены решения) упорядочены по возрастающим F-змачениям

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

:- ОрС 600, х£х,--- > ) .

aildOEE Mode, SolutionTree) :-

expand! leaf ( Node, 0, 0) , »999, SolutionTree, yes). % Предполагается, что

% любое F-значенке не превышает 9999

* Процедура expand( Tree, Bound, NewTree, Solved)

в Развертызает дерево Tree в пределах Bound, формируя дерево NewTree,

s ДЛЯ которого "состояние решения" определяется переменной Solved

294 Часть II. Применение языка Prolog й области искусственного интеллекта

% Случай 1. Превышен предел Bound

expand{ Tree, Bound, Tree, no} :-

f [ Tree, Fj, F > Bound, !. % Превышен предел Bound

I Во всех остальных случаях F =< Bound

% Случай 2. Обнаружена цель

expandt leaf( Node, F, C) , _, SOlvedleaf[ Node, F) , yes) :-goal(Wode), !.

% Случай 3. Развертывание лист-узла

expand! leaf( Mode, F, C) , Bound, NewTree, Solved) :-{ expandnodei Node, C, TreeU, ! ,

expand; Treel, Bound, NewTree, Solved); Solved = never, ! ) , % Преемники отсутствуют, тупиковый конец

% Случай 4. Развертывание дерева

expand! tree[ Mode, F, С, SubTrees), Bound, NewTree, Solved) :-Boundl is Bound - C,

expandlist [ SubTrees, Boundl, NewSubs, Solvedl) , continue( Solvedl, Node, C, NewSubs, Bound, NewTree, Solved),

% expandlistt Trees, Bound, NewTrees, Solved)

% 'развертывает список деревьев Trees в пределах Bound, формируя список

I NewTrees, для которого "состояние решения" определяется переменной Solved

expandlistC Trees, Bound, NewTrees, Solved] :-

selecttree{ Trees, Tree, OtherTrees, Bound, Boundl),

exoand! Tree, Boundl, NewTree, Solvedl),

combine ! OtherTrees, NewTree, Solvedl, NewTrees, Solved).

I Процедура continue принимает решение в отношении дальнейших действий % после развертывания списка деревьев

continue! yes, Node, с, SubTrees, _, solvedtree(Mode,F,SubTrees), yes) :-backup{ SubTrees, K) , F is С t H_r !.

continuet never, _, _, _, _, _, never) :- !.

continue,- no. Node, C, SubTrees, Bound, NewTree, Solved) :-backupt SubTrees, H) , F is С + H, !, expandt treeCNode, F, C, SubTrees), Bound, MewTree, Solved).

| Процедура combine объединяет результаты развертывания дерева и списка деревьев

combine! or:_, Tree, yes, Tree, yes) :- !. * Найдено решение для списка OR

combine[ or:Trees, Tree, no, or:NewTrees, no) :-

insert( Tree, Trees, NewTrees}, !• % Решение для спискаOR еще не найдено

combine,- or» lb , never, , never) :- !. % Узлов, для которых возможно

% развертывание, больше нет

combine С or:Trees, _, never, or:Trees, no) :- !. % Еще есть узлы, для которых

% возможно развертывание

combine; and:Trees, Tree, yes, and:[Tree Trees], yes) :-

allsolved(Trees), !. % Найдено решение для списка AND

combine; and:_, _, never, _, never) :- !. % Решение для списка AND

% найти невозможно

Глава 13. Декомпозиция задач и графы AND/OR

combine( and:Trees, Tree, YesNo, and:NewTrees, no) :-

insert; Tree, Trees, NewTrees), !. % Решение для списка AND еше не найдено

i Процедура expandnode формирует дерево, состоящее из узла и его преемников

expandnode) Node, С, tree ( Node, F, С, Op:SubTrees)) :-

Node--- > Op successors,

evaluate! Successors, SubTrees), backup) OpiSubTrees, Ш, F is С + H.

evaluate) [] , []) .

evaluate) [Node/Cl NodesCosts], Trees) :-

h{ Node, H), F is С + К,

evaluate( NodesCosts, Treesl) ,

insert! leaf( Node, F, C) , Treesl, Trees) .

% Процедура allsolved проверяет, для всех ли деревьев в списке деревьев * найдено решение

allsolved) []) .

allsolved([Tree|Trees]) : -

solved(Tree >, allsolved(Treesl.

solved; solvedtree (_,_,_)) .

solved ( soivedieaf (_,_)) .

f ( Tree, F) :- % Извлечь F-эначение для дерева.

arg( 2, Tree, :-";,!. % F - ЭТО второй параметр в отношении Tree

% insert) Tree, Trees, NewTrees): вставляет дерево Tree в список деревьев Trees, - формируя список NewTrees

insert; Т, [] , [Т]) :- ! .

insert) T, [T1|TS], [T,T1|TS]) :-solved (Tl), !.

insert) T, [TUTS], [TllTsl]) :-solved(T),

insert) T, Ts, Tsl), ! .

insert) T, [TllTs], [T,Tl|Ts]) :-f ( T, F. , f(Tl, Fl), F =< Fl, ! .

insertCT, [TllTs], [Tl|T5l]l :-

insert С т, ts, Tsl) .

% Процедура backup находит все резервные копии F-значений для списка I деревьев AND/OR

backup! or:[Treel_) , F) :- % Первое дерево в списке OR является наилучшим t ( Tree, F) , ! .

backup) and: [] , 0) :- ! .

backupf and:[Treel|Trees], F) :-

ft Treel, Fl),

backup) and:Trees_r F2} ,

F is Fl + F2, !.

backup) Tree, F) :-

Часть К. Применение языка Prolog в области искусственного интеллекта

F( Tree, F).

% Bound - это предел развертывания для деревьев из списка Trees, % Boundl - предел развертывания для BestTree

selecttree( Op:[Treel, Tree, o_P:[], Bound, ВоиЫ) :- !. Ъ Единственное дерево,

3 для которого возможноразвертывание

selecttreet Op: [Tree |Trees} , Tree, Op:Trees, Bound, Boundl) :-backup{ Op:Trees, F) , [ Op = or, !, mint Bound, F, Boundl); Op = and, Boundl is Bound - F).

mini A, a, A) :- A < в, ! .

mint А, Б, m .

Ключевым отношением в программе, приведенной в листинге 13.2, является сле­дующее:

expand( Tree, Bound, Treel, Solved)

где Tree и Bound - "входные" параметры, a Treel и Solved - "выходные". Значе­ния этих параметров описаны ниже.

• Tree. Дерево поиска, которое должно быть развернуто.

• Bound. Предел для F-значения, в котором разрешено развертывание дерева Tree.

• Solved. Индикатор, значение которого указывает на один из следующих трех
случаев.

• Solved = yes. Дерево Tree может быть развернуто в заданных пределах таким образом, чтобы оно представляло собой дерево решения Treel.

• Solved - no. Дерево Tree может быть развернуто в дерево Treel таким образом, что F-значение дерева Treel превышает предел Bound и не найдено поддерево решения до того, как F-значение превысило предел Bound.

• Solved = never. Дерево Tree не содержит решения.

В зависимости от описанных выше случаев, Treel представляет собой дерево ре­шения, полученное в результате развертывания дерева Tree непосредственно за пре­делы Bound, или неконкретизированную переменную (в случае Solved = never). Процедура

expandlistc Trees, Bound, Treesl, Solved)

аналогична процедуре expand. Как и в процедуре expand, Bound представляет собой предел развертывания дерева, a Solved — индикатор того, что произошло во время развертывания ("yes", "г:с" или "never"). Но первым параметром этой процедуры является список деревьев (список AND или список OR), как показано ниже. Trees - qx:IT1, T2,... ] или Trees = and:!-:, T2, ... ]

Процедура expandlist выбирает в списке Trees наиболее перспективное дерево Т (в соответствии с F-значением). Благодаря используемому упорядочению подде­ревьев это — всегда первое дерево в списке Trees. Наиболее перспективное поддере­во развертывается с новым пределом Boundl, Значение Boundl зависит от Bound, a также от других деревьев в списке Trees. Если Trees представляет собой список OR, то Boundl меньше Bound и равен F-значению дерева в списке Trees со следую­щим по порядку критерием оптимальности (F-значением), Если Trees — список AND, то Boundl равен значению Bound за вычетом суммы F-знйЧений остальных де-

Глава 13,Декомпозиция задач и графы AND/OR

ревьев в списке Trees. Состав списка Treesl зависит от ситуации, обозначенной ин­дикатором Solved. В том случае, если Solved = no, список Treesl представляет собой список Trees с наиболее перспективным деревом из списка Trees, разверну­тым в пределах Boundl. В случае Solved = yes, список Treesl является решением списка Trees (найденным в пределах Bound), Если Solved = never, список Treesl представляет собой не конкретизированную переменную.

Процедура continue, которая вызывается после развертывания списка деревьев, определяет, какие действия должны выполняться в дальнейшем, в зависимости от результатов выполнения процедуры expandlist. Она формирует дерево решения, обновляет дерево поиска и продолжает его развертывание или же сигнализирует о ситуации "never" (в том случае, если было обнаружено, что список деревьев не со­держит решения).

Еще одна процедура, combine ( otherTrees, NewTree, Solvedl, HewTrees, Solved)

объединяет в себе средства представления нескольких объектов, которые обрабаты­ваются процедурой expandlist. Здесь NewTree - дерево, развернутое в списке де­ревьев процедуры expandlist, OtherTrees — остальные, неизменившиеся деревья в списке деревьев, a Solvedl - индикатор "состояния решения" для NewTree. Б про­цедуре combine обрабатывается несколько ситуаций, в зависимости от значения Solvedl и от того, является ли список деревьев списком AND или списком OR. На­пример, в предложении combiner, or:_. Tree, yes, Tree, уез) .

указано, что в случае, если список деревьев представляет собой список OR, только что развернутое дерево было решено и его дерево решения — Tree, то найдено реше­ние для всего списка и этим решением является само дерево Tree. Назначение дру­гих случаев можно проще всего понять из кода самой процедуры combine.

Для отображения дерева решения может быть определена процедура, аналогичная процедуре show (см. листинг 13.1). Разработку такой процедуры оставляем в качест­ве упражнения для читателя.