Power JavaDeveloping Intelligent Systems With Java and Prolog

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).

Featured

Most   Popular
Upcoming Events

AppTrends

Sign up for our newsletter.

Terms and Privacy Policy consent

I agree to this site's Privacy Policy.