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 Hr !.
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:Treesr F2} ,
F is Fl + F2, !.
backup) Tree, F) :-
Часть К. Применение языка Prolog в области искусственного интеллекта
F( Tree, F).
% Bound - это предел развертывания для деревьев из списка Trees, % Boundl - предел развертывания для BestTree
selecttree( Op:[Treel, Tree, oP:[], 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). Разработку такой процедуры оставляем в качестве упражнения для читателя.