% 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) :-
    backup(SubTrees,H), F is C+H,!.
continue(never,_,_,_,_,_,never) :- ! .
continue(no,Node,C,SubTrees,Bound,NewTree,Solved) :- backup(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),backup(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
backup(or:[Tree|_], F) :- f(Tree,F), !.
backup(and:[],0) :- ! .
backup(and:[Tree1|Trees],F) :- f(Tree1,F1),backup(and:Trees,F2),F is F1+F2,!.
backup(Tree,F) :- f(Tree,F).

selecttree(Op:[Tree],Tree,Op:[],Bound,Bound) :- !. % The only candidate
selecttree(Op:[Tree|Trees],Tree,Op:Trees,Bound,Bound1) :- backup(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).

% slide 18

move(a,b,2). move(a,c,3). move(b,e,3).
move(b,d,2). move(c,e,1). move(c,l ,2).
move(e,k,4). move(e,l,2). move(k,u,2).
move(k,x,3). move(u,v,5). move(x,y,3).
move(y,z,3). move(v,z,3). move(l,u,1).
move(d,k,1). move(u,y,2).

stateS(a). stateS(b). stateS(c). stateS(d). stateS(e).
stateT(u). stateT(v). stateT(x). stateT(y). stateT(z).
border(l). border(k).

key(M1-M2,M3) :- stateS(M1), stateT(M2), border(M3).

city(X) :- (stateS(X);stateT(X);border(X)).

% slide 20 - konstrukce grafu

?- op(560,xfx,via). % operatory X-Z a X-Z via Y

a-z ---> or:[a-z via k/0,a-z via l/0].
a-v ---> or:[a-v via k/0,a-v via l/0].
%...
a-l ---> or:[c-l/3,b-l/2].
b-l ---> or:[e-l/3,d-l/2].
%...
a-z via l ---> and:[a-l/0,l-z/0].
a-v via l ---> and:[a-l/0,l-v/0].
%...
goal(a-a). goal(b-b). %...

X-Z ---> or:Problemlist :- city(X),city(Z), bagof((X-Z via Y)/0, key(X-Z,Y), Problemlist),!.
X-Z ---> or:Problemlist :- city(X),city(Z), bagof((Y-Z)/D, move(X,Y,D), Problemlist).
X-Z via Y ---> and:[(X-Y)/0,(Y-Z)/0]:- city(X),city(Z),key(X-Z,Y).
goal(X-X).
