The A* Algorithm (A Star)
(from Elements of AI Using Common Lisp, by Tanimoto)
ALGORITHM A*
begin
input the start node S and the GOAL (or set of GOALS);
OPEN <- {S}; CLOSED <- NIL;
g(S) <- 0; pred(S) <- NIL; found <- false;
while OPEN is not empty and found is false do
begin
L <- the node on OPEN for which f is the least;
(or set of nodes if using a set of GOALS)
if L is a singleton then let X be its sole element
(NOTE: In our case, X is L because L is only one node)
remove X from OPEN and put X into CLOSED;
if X is a goal node then found <- true
else begin
generate the set SUCCESSORS of successors of X;
for each Y in SUCCESSORS do
if Y is not already on OPEN or on CLOSED then
begin
g(Y) <- g(X) + distance(X,Y);
f(Y) <- g(Y) + h(y);
pred(Y) <- X;
insert Y in OPEN;
end
else begin /* Y is on OPEN or on CLOSED */
Z <- pred(Y);
temp <- f(Y) - g(Z) - distance(Z,Y)
+ g(X) - distance(X,Y);
if temp < f(Y) then
begin
g(Y) <- g(Y) - f(Y) + temp; /* UPDATE OPEN */
f(Y) <- temp;
pred(Y) <- X;
if Y is on CLOSED then /* UPDATE CLOSED */
insert Y on OPEN and remove Y from CLOSED;
end;
end;
end;
end; /* end while loop */