A* Shortest Path Algorithm

From GM-RKB
Jump to: navigation, search

An A* Shortest Path Algorithm is a shortest path algorithm that uses a uniform-cost heuristic that assigns a weight to each open node equal to the weight of the edge to that node plus the approximate distance between that node and the finish.



References

2017

  1. Cite error: Invalid <ref> tag; no text was provided for refs named Zeng
  2. Cite error: Invalid <ref> tag; no text was provided for refs named nilsson

2016

  • http://en.wikipedia.org/wiki/Pathfinding#A*_algorithm
    • QUOTE: A* is a variant of Dijkstra's algorithm commonly used in games. A* assigns a weight to each open node equal to the weight of the edge to that node plus the approximate distance between that node and the finish. This approximate distance is found by the heuristic, and represents a minimum possible distance between that node and the end. This allows it to eliminate longer paths once an initial path is found. If there is a path of length x between the start and finish, and the minimum distance between a node and the finish is greater than x, that node need not be examined.[1]

      A* uses this heuristic to improve on the behavior relative to Dijkstra's algorithm. When the heuristic evaluates to zero, A* is equivalent to Dijkstra's algorithm. As the heuristic estimate increases and gets closer to the true distance, A* continues to find optimal paths, but runs faster (by virtue of examining fewer nodes). When the value of the heuristic is exactly the true distance, A* examines the fewest nodes. (However, it is generally impractical to write a heuristic function that always computes the true distance.) As the value of the heuristic increases, A* examines fewer nodes but no longer guarantees an optimal path. In many applications (such as video games) this is acceptable and even desirable, in order to keep the algorithm running quickly.

2012b

2009

1968

  • (Hart et al., 1968) ⇒ Peter E. Hart, Nils J. Nilsson, and Bertram Raphael. (1968). “A Formal Basis for the Heuristic Determination of Minimum Cost Paths". In: IEEE Transactions on Systems Science and Cybernetics SSC4, 4(2). doi:10.1109/TSSC.1968.300136.