|
|
 |
 |
 | | | | |
 |
|||
 |
||||||
          |
 |
 |
||||
|
The Star of the Search Algorithms (A* Search)
The
best-established algorithm for the general searching of optimal paths
is A* (pronounced "A-star"). This heuristic search ranks each node by
an estimate of the best route that goes through that node. The typical
formula is expressed as:
f(n) = g(n) + h(n)
where:
f(n) is the score assigned to node n
g(n) is the actual cheapest cost of
arriving at n from the start
h(n) is the heuristic estimate of the
cost to the goal from n
So it combines
the tracking of the previous path length of Dijkstra's algorithm, with
the heuristic estimate of the remaining path from best-first search. The
algorithm proper is seen in Listing
3. Since some nodes may be processed more than once-from finding
better paths to them later-we use a new list called Closed to keep track
of them.
|
|
|
Features
