A* Shortest Path Algorithm

From GM-RKB
(Redirected from A*)
Jump to navigation Jump to search

An A* Shortest Path Algorithm is a shortest path algorithm that is a modification of Dijkstra's Algorithm that is optimized for a single destination.



References

2021

2017

  1. Zeng, W.; Church, R. L. (2009). "Finding shortest paths on real road networks: the case for A*". International Journal of Geographical Information Science. 23 (4): 531–543. doi:10.1080/13658810801949850. S2CID 14833639.
  2. Nilsson, Nils J. (2009-10-30). The Quest for Artificial Intelligence (PDF). Cambridge: Cambridge University Press. ISBN 9780521122931.

2016

  • (Wikipedia, 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

  • (Korf, 2009) ⇒ Richard E. Korf. (2009). “Artificial Intelligence Search Algorithms.” In: Algorithms and Theory of Computation Handbook. ISBN:1584888180
    • QUOTE: The A* algorithm [14] combines features of uniform-cost search and pure heuristic search to efficiently compute optimal solutions. A* is a best-first search in which the cost associated with a node is f(n) = g(n) + h(n), where g(n) is the cost of the path from the initial state to node n, and h(n) is the heuristic estimate of the cost of a path from node n to a goal. At each point a node with lowest f value is chosen for expansion. Ties among nodes of equal f value are broken in favor of nodes with lower h values. The algorithm terminates when a goal node is chosen for expansion. A* finds an optimal path to a goal if the heuristic function h(n) is admissible, meaning it never overestimates actual cost. … The main drawback of A*, and indeed of any best-first search, is its memory requirement. Since the open and closed lists are stored in memory, A* is severely space-limited in practice, and will exhaust the available memory on current machines in minutes.

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.