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
	% backtrack

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
		Val1-[Next,Node | Path], 
		next_node(Node, MoreOPEN, CLOSED, Goal, Next),
		get_cost(Next, [Node | Path], Goal, Val1)
	% 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) :-
	Y is X + Dist,
	path_cost_helper([Next|Nodes], Y, Val).

distance_road(A,B,Dist) :-
/* Calculates goal cost */
goal_cost(Node, G, 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),

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


Upcoming Events


Sign up for our newsletter.

I agree to this site's Privacy Policy.