Power JavaDeveloping Intelligent Systems With Java and Prolog
- By by Lalit Pant
- April 18, 2000
Listing 3.
/* Prolog definition of the A-star search algorithm (astar.pro) */
/* A* search Algorithm */
astar_search(Start, Goal) :-
% find a solution
astar_search_helper([0-[Start]], [ ], Goal, Sol),
% send result to java
report_result(Sol),
% backtrack
fail.
astar_search_helper([ Val-[Goal | Path] | MoreOPEN], CLOSED, Goal, Val-[Goal | Path]).
astar_search_helper([Val-[Node | Path] | MoreOPEN], CLOSED, Goal, Sol) :-
% find all nodes adjacent to the current node
% and calculate the cost of each
findall(
Val1-[Next,Node | Path],
(
next_node(Node, MoreOPEN, CLOSED, Goal, Next),
get_cost(Next, [Node | Path], Goal, Val1)
),
NewNeighbors
),
% add the new nodes to the OPEN list
append(NewNeighbors, MoreOPEN, TmpOPEN2),
% move the most promising node to the top
move_smallest_to_top(TmpOPEN2, NewOPEN),
% continue search with new nodes
astar_search_helper(NewOPEN, [Node | CLOSED], Goal, Sol).
/*
Finds the neighbors of a node, given the goal and the OPEN and CLOSED
Lists. This predicate is used in the main algo (instead of the get_next predicate) so that we may generate multiple solutions. Without this,
when the goal enters the MoreOPEN list, further solutions are not
generated. That is not be a problem if we want to find only the 'best'
solution to the problem. But if we do want to generate more solutions,
we need to explicitly test to see if the Next node is the goal. If it
is, we *do* add it to the open list, unless the whole path to the goal
is already on the list (and this is not an alternative path).
*/
next_node(Node, MoreOPEN, CLOSED, Goal, Next) :-
get_next(Node, Next),
Next == Goal,
not(lmember( _-[Next|_], MoreOPEN)).
next_node(Node, MoreOPEN, CLOSED, Goal, Next) :-
get_next(Node, Next),
Next \== Goal,
not(lmember( _-[Next|_], MoreOPEN)),
not(lmember( Next, CLOSED)).
/* Finds neighbors of a node */
get_next(Node, Next) :-
Node \== Goal,
(arc(Node, Next,_);arc(Next,Node,_)).
/* Moves the path with the lowest 'cost' to the top of the list */
move_smallest_to_top([ ], [ ]).
move_smallest_to_top([Val-X|L], [S|R]) :-
find_smallest(L, Val-X, S, R).
find_smallest([ ], T, T, [ ]).
find_smallest([Val1-X | L], Val-T, S, [Val-T | R]) :-
Val1 < Val, !,
find_smallest(L, Val1-X, S, R).
find_smallest([Val1-X | L], Val-T, S, [Val1-X| R]) :-
% Val <= Val1
find_smallest(L, Val-T, S, R).
/* Calculates estimated cost of Path to Goal via Next */
get_cost(Next, Path, Goal, Val) :-
% g(n) - cost of path so far
path_cost([Next|Path], Val1),
% h(n) - cost from Next to goal
goal_cost(Next, Goal, Val2),
Val is Val1 + Val2,
!.
/* Calculates path cost */
path_cost(Nodes, Val) :-
path_cost_helper(Nodes, 0, Val),
!.
path_cost_helper([Node], Val, Val).
path_cost_helper([Top,Next|Nodes], X, Val) :-
distance_road(Top,Next,Dist),
Y is X + Dist,
path_cost_helper([Next|Nodes], Y, Val).
distance_road(A,B,Dist) :-
(arc(A,B,Dist);arc(B,A,Dist)),
!.
/* Calculates goal cost */
goal_cost(Node, G, Val) :-
distance_point(Top,Next,Val),
!.
distance_point(A,B,Dist) :-
city(A, X1, Y1),
city(B, X2, Y2),
distance_calc(X1, Y1, X2, Y2, Dist),
!.
/* Reverses path and calls the java 'result' predicate to report result
*/
report_result(Val-Cities) :-
reverse(Cities, NewCities),
result(Val-NewCities),
!.
/* Graph Data */
city(a, 2, 2).
city(b, 8, 2).
city(c, 14, 4).
city(d, 10, 6).
city(e, 6, 8).
city(f, 16, 10).
city(g, 8, 12).
city(h, 12, 14).
arc(a, b, 7).
arc(a, e, 8).
arc(b, d, 5).
arc(e, d, 5).
arc(d, c, 5).
arc(e, f, 11).
arc(e, g, 5).
arc(g, h, 5).
arc(f, h, 6).