% priklad Cesta mezi mesty pomoci AND/OR A*

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(700, xfx, --->),
   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].
% ...
X-Z ---> or:Problemlist :- city(X),city(Z), bagof((X-Z via Y)/0, key(X-Z,Y), Problemlist),!.


% a-l ---> or:[c-l/3,b-l/2].
% b-l ---> or:[e-l/3,d-l/2].
% ...
X-Z ---> or:Problemlist :- city(X),city(Z), bagof((Y-Z)/D, move(X,Y,D), Problemlist).

% a-z via l ---> and:[a-l/0,l-z/0].
% a-v via l ---> and:[a-l/0,l-v/0].
% ...
X-Z via Y ---> and:[(X-Y)/0,(Y-Z)/0]:- city(X),city(Z),key(X-Z,Y).

%goal(a-a). goal(b-b). ...
goal(X-X).

% heuristika h - podle hrany nebo ze stejneho statu=1, z ruzneho=2
h(X-X,0).
h(X-Z,C):-move(X,Z,C),!.
h(X-Z,C):-move(Z,X,C),!.
h(X-Z,2):-stateS(X),stateT(Z),!.
h(X-Z,2):-stateT(X),stateS(Z),!.
h(X-Z via _,2):-stateS(X),stateT(Z),!.
h(X-Z via _,2):-stateT(X),stateS(Z),!.
h(_-_,1).

biggest(99).

run:- 
    ['5.3_15.pl'], nl,
    write('Cesta mezi mesty, algoritmus AND/OR A*'), nl, nl,
    Start=a-z,
    write('Zadani: '), write(Start), nl,
    andor(Start,SolutionTree),
    write('Nalezene reseni:'),nl,
    write(SolutionTree).

% s heuristikou h1 vyzaduje hodne pameti (pro d=26)
%:- set_prolog_stack(local,  limit(256 000 000)). % vyzaduje 64-bit system
:- run.

% vim: set ft=prolog:

Cesta mezi mesty, algoritmus AND/OR A*

Zadani: a-z
Nalezene reseni:
solvedtree(a-z,11,solvedtree(a-z via l,11,and:[solvedtree(l-z,6,solvedtree(u-z,6,solvedtree(y-z,5,solvedleaf(z-z,3)))),solvedtree(a-l,5,solvedtree(c-l,5,solvedleaf(l-l,2)))]))