Toggle navigation
?
users online
Logout
Open hangout
Open chat for current file
% nacteni: /* ['5.3_15.pl']. */ ?- op(600, xfx, --->). ?- op(500, xfx, :). andor(Node,SolutionTree) :- biggest(Bound),expand(leaf(Node,0,0),Bound,SolutionTree,yes). % Case 1: bound exceeded, in all remaining cases F =< Bound expand(Tree,Bound,Tree,no) :- f(Tree,F),F>Bound,!. % Case 2: goal encountered expand(leaf(Node,F,_C),_,solvedleaf(Node,F),yes) :- goal(Node),!. % Case 3: expanding a leaf expand(leaf(Node,_F,C),Bound,NewTree,Solved) :- expandnode(Node,C,Tree1),!, (expand(Tree1,Bound,NewTree,Solved);Solved=never,!). % Case 4: expanding a tree expand(tree(Node,_F,C,SubTrees),Bound,NewTree,Solved) :- Bound1 is Bound-C, expandlist(SubTrees,Bound1,NewSubs,Solved1), continue(Solved1,Node,C,NewSubs,Bound,NewTree,Solved). expandlist(Trees,Bound,NewTrees,Solved) :- selecttree(Trees,Tree,OtherTrees,Bound,Bound1), expand(Tree,Bound1,NewTree,Solved1), combine(OtherTrees,NewTree,Solved1,NewTrees,Solved). continue(yes,Node,C,SubTrees,_,solvedtree(Node,F,SubTrees),yes) :- bestf(SubTrees,H), F is C+H,!. continue(never,_,_,_,_,_,never) :- ! . continue(no,Node,C,SubTrees,Bound,NewTree,Solved) :- bestf(SubTrees,H), F is C+H,!,expand(tree(Node,F,C,SubTrees),Bound,NewTree,Solved). % slide 16 combine(or:_,Tree,yes,Tree,yes) :- !. combine(or:Trees,Tree,no,or:NewTrees,no) :- insert(Tree,Trees,NewTrees),!. combine(or:[],_,never,_,never) :- ! . combine(or:Trees,_,never,or:Trees,no) :- !. combine(and:Trees,Tree,yes,and:[Tree|Trees],yes) :- allsolved(Trees),!. combine(and:_,_,never,_,never) :- ! . combine(and:Trees,Tree,_YesNo,and:NewTrees,no) :- insert(Tree,Trees,NewTrees),!. expandnode(Node,C,tree(Node,F,C,Op:SubTrees)) :- Node ---> Op:Successors, evaluate(Successors,SubTrees),bestf(Op:SubTrees,H),F is C+H. evaluate([],[]). evaluate([Node/C|NodesCosts],Trees) :- h(Node,H),F is C+H,evaluate(NodesCosts,Trees1), insert( leaf(Node,F,C),Trees1,Trees). allsolved([]). allsolved([Tree|Trees]) :- solved(Tree),allsolved(Trees). solved(solvedtree(_,_,_)). solved(solvedleaf(_,_)). % slide 17 f(Tree,F) :- arg(2,Tree,F),! . insert(T ,[],[ T]) :- ! . insert(T,[T1|Ts],[T,T1|Ts]) :- solved(T1),!. insert(T,[T1|Ts],[T1|Ts1]) :- solved(T), insert(T,Ts,Ts1),! . insert(T,[T1|Ts],[T,T1|Ts]) :- f(T,F), f(T1,F1),F=<F1,!. insert(T,[T1|Ts],[T1|Ts1]) :- insert(T,Ts,Ts1). % First tree in OR-list is best bestf(or:[Tree|_], F) :- f(Tree,F), !. bestf(and:[],0) :- ! . bestf(and:[Tree1|Trees],F) :- f(Tree1,F1),bestf(and:Trees,F2),F is F1+F2,!. bestf(Tree,F) :- f(Tree,F). selecttree(Op:[Tree],Tree,Op:[],Bound,Bound) :- !. % The only candidate selecttree(Op:[Tree|Trees],Tree,Op:Trees,Bound,Bound1) :- bestf(Op:Trees,F), (Op=or,!,min(Bound,F,Bound1);Op=and,Bound1 is Bound-F). min(A,B,A) :- A<B,!. min(_A,B,B).
true