%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
% %
% Musterloesung (Thomas Linke, Christian Anger, Mai 2001) %
% %
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
%
% search(+Frontier,-Path) succeeds iff Path is the path in the graph to
% the goal node specified in is_goal/1 using A* search
% loopchecking is provided
% Frontier-elements are of the form node(NameOfNode,PathToNode,CostOfPath)!!
%
search(Frontier,[Node|Path]) :-
choose(node(Node,Path,_PathCost),Frontier,_),
is_goal(Node).
search(Frontier,Result) :- % loopchecking
choose(node(Node,Path,_),Frontier,RestOfFrontier),
member(Node,Path),
search(RestOfFrontier,Result).
search(Frontier,Result) :-
choose(node(Node,Path,PathCost),Frontier,RestOfFrontier),
notin(Node,Path), % again loopchecking
neighbors(Node,NeighboringNodes),
add_paths(NeighboringNodes,node(Node,Path,PathCost),NewFrontierElements),
add_to_frontier_A_star(NewFrontierElements,RestOfFrontier,NewFrontier),
search(NewFrontier,Result).
%
% neighbors(+Node,-NeighboringNodes)
% successors of node Node are NeigboringNodes
%
neighbors(Node,NeighboringNodes):-
findall(Neighbor, arc(Node,Neighbor,_), NeighboringNodes).
%
% add_paths(+NeighboringNodes,+node(Node,Path,PathCost),-NewFrontierElements) is
% true if NewFrontierElements is the list of new frontier elements to replace frontier
% element node(Node,Path,PathCost) for each node in NeighboringNodes, where
% NeighboringNodes is a list of neighbors of node Node.
%
add_paths([],_,[]).
add_paths([Succ|Rest],node(Node,Path,PathCost),
[node(Succ,[Node|Path],NewPathCost)|FrontierElements]) :-
arc(Node,Succ,Cost),
NewPathCost is PathCost + Cost,
add_paths(Rest,node(Node,Path,PathCost),FrontierElements).
%
% add_to_frontier for A_Star
%
add_to_frontier_A_star(Node,Frontier1,Frontier2) :- !,
mergeinto_A_star(Node,Frontier1,Frontier2).
%
% mergeinto_A_star(NodeList,Frontier1,Frontier2) is true if when NodeList
% is added to Frontier1, the result is Frontier2
% assuming Frontier1 is in sorted order determinded by f, Frontier2 will be
% in sorted order determinded by f = g + h.
%
mergeinto_A_star([],L,L).
mergeinto_A_star([H|T],L1,L3) :-
insertinto_A_star(H,L1,L2),
mergeinto_A_star(T,L2,L3).
%
% insertinto_A_star(Node,Frontier1,Frontier2) is true if Frontier2 contains
% the elements of Frontier1 with node Node inserted into the position
% determined by the f value of Node
%
insertinto_A_star(E,[],[E]).
insertinto_A_star(node(N,P,PC),
[node(N1,P1,PC1)|R],
[node(N,P,PC),node(N1,P1,PC1)|R]):-
h(N,NC),
F is NC + PC,
h(N1,NC1),
F1 is NC1 + PC1,
F =< F1.
insertinto_A_star(node(N,P,PC),
[node(N1,P1,PC1)|R],
[node(N1,P1,PC1)|R1]) :-
h(N,NC),
F is NC + PC,
h(N1,NC1),
F1 is NC1 + PC1,
F > F1,
insertinto_A_star(node(N,P,PC),R,R1).
%
% notin(E,L) is true if E is not in list L
%
notin(_,[]).
notin(E,[H|T]) :-
E \== H,
notin(E,T).
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
% Hilfestellung %
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
%
% choose(-Node,+Frontier,-RestOfFrontier) chooses first element from
% frontier
%
choose(Node,[Node|Frontier],Frontier).
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
% Graph, Heuristik und Zielknoten %
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
%
% arcs with costs
% arc(+StartNode,-NextNode,-Cost)
%
arc('Bal. Camboriú','Brusque',43).
arc('Bal. Camboriú','Itajaí',9).
arc('Blumenau','Brusque',40).
arc('Blumenau','Itajaí',47).
arc('Blumenau','Jaraguá',67).
arc('Blumenau','Rio do Sul',89).
arc('Brusque','Bal. Camboriú',43).
arc('Brusque','Blumenau',40).
arc('Caçador','Jaraguá',301).
arc('Caçador','Mafra',204).
arc('Garuva','Joinville',36).
arc('Garuva','São Bento',74).
arc('Itajaí','Bal. Camboriú',9).
arc('Itajaí','Blumenau',47).
arc('Itajaí','Joinville',94).
arc('Jaraguá','Caçador',301).
arc('Jaraguá','Blumenau',67).
arc('Jaraguá','Joinville',53).
arc('Jaraguá','São Bento',45).
arc('Joinville','Garuva',36).
arc('Joinville','Itajaí',94).
arc('Joinville','Jaraguá',53).
arc('Joinville','São Bento',68).
arc('Mafra','Caçador',204).
arc('Mafra','São Bento',65).
arc('Rio do Sul','Blumenau',89).
arc('Rio do Sul','Lages',134).
arc('São Bento','Garuva',74).
arc('São Bento','Jaraguá',45).
arc('São Bento','Joinville',68).
arc('São Bento','Mafra',65).
%
% heuristic function
% h(+Node,-EstimateToGoalNode)
%
h('Bal. Camboriú' ,275).
h('Blumenau' ,219).
h('Brusque' ,203).
h('Caçador' ,162).
h('Garuva' ,353).
h('Itajaí' ,266).
h('Jaraguá' ,275).
h('Joinville' ,310).
h('Mafra' ,265).
h('Rio do Sul' ,134).
h('São Bento' ,320).
h('Lages' ,0).
%
% problem: find goal l
%
is_goal('Lages').
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
% Tests %
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
test(Path):-
search([node('Joinville',[],0)],Path).