home *** CD-ROM | disk | FTP | other *** search
/ Source Code 1992 March / Source_Code_CD-ROM_Walnut_Creek_March_1992.iso / msdos / cad / pcb.arc / ASTAR < prev    next >
Encoding:
Text File  |  1989-02-20  |  2.9 KB  |  53 lines
  1. A* Algorithm  (* heuristic search *)
  2.    (* Search a graph or state space, depending on the problem definition. *)
  3.    (* S is the start node, T is the goal node. *)
  4.    (* Open is an ordered list of nodes (ordered by lowest F value; see below),
  5.       also called a priority queue. Closed is a set of nodes (order doesn't
  6.       matter). In general, nodes that need to be searched are put on Open (at
  7.       the proper position). As they are searched, they are removed from Open
  8.       and put in Closed. Occasionally a newer, better route will be found to a
  9.       node after it has already been searched, in which case we remove it from
  10.       Closed and put it back on Open to be reconsidered. *)
  11.    (* G[x] is the distance already traveled to get from S to node x, and is
  12.       known exactly. H(x) is a function (heuristic) which returns an estimate
  13.       of the distance from node x to T. F[x] is the estimated distance from S
  14.       to T by going through node x, and is computed by F[x] = G[x] + H(x).
  15.       H(x) can be calculated for any node, but F[x] and G[x] only become
  16.       defined when node x is visited. *)
  17.    (* Pred is defined for each node, and is a list of "came from" indications,
  18.       so when we finally reach T, we traverse Pred to construct a path to
  19.       S. *)
  20.    (* Distance(x,y) is a function for calculating the distance between two
  21.       neighboring nodes. *)
  22. 1  Open <- {S}  (* a list of one element *)
  23.    Closed <- {}  (* the empty set *)
  24.    G[S] <- 0,  F[S] <- 0,  Pred[S] <- NULL,  found <- FALSE
  25.    WHILE Open <> {} and not found DO
  26. 5     x <- the first node on Open  (* node with smallest F value *)
  27.       Open <- Open - {x}  (* remove x from Open *)
  28.       Closed <- Closed + {x}  (* put x in Closed *)
  29.       IF x = T THEN found <- TRUE  (* we're done *)
  30.       ELSE  (* continue search through node x *)
  31. 10       let R be the set of neighboring nodes of x
  32.          FOR each y in R DO
  33.             IF y is not on Open or in Closed THEN
  34.                G[y] <- G[x] + Distance(x,y)
  35.                F[y] <- G[y] + H(y)  (* estimate solution path length *)
  36. 15             Pred[y] <- x  (* remember where we came from *)
  37.                Open <- Open + {y}  (* put y on Open *)
  38.             ELSE  (* y is on Open or in Closed *)
  39.                IF (G[x] + Distance(x,y)) < G[y] THEN
  40.                   (* we've found a better route to y *)
  41. 20                G[y] <- G[x] + Distance(x,y)
  42.                   F[y] <- G[y] + H(y)
  43.                   Pred[y] <- x  (* remember where we came from *)
  44.                   IF y is on Open THEN
  45.                      reposition y according to F[y]
  46. 25                ELSE  (* y is in Closed *)
  47.                      Closed <- Closed - {y}  (* remove y from Closed *)
  48.                      Open <- Open + {y}  (* put y on Open *)
  49.    IF found THEN
  50.       use Pred[T] to find Pred[Pred[T]] and so on until S is reached
  51. 30    (* this traces out the solution path in reverse *)
  52.    ELSE T cannot be reached from S
  53.