A* search: finding a path cleverly with a heuristic
The same maze, three methods. Dijkstra opens 311 cells and finds the shortest path; greedy opens 117 but brings back a path 34% longer. A* is not somewhere between the two, it takes the best of both.
4 steps
175 XP
A free account is needed
Start the lesson →
Sources
- Hart, P. E., Nilsson, N. J. & Raphael, B. 1968 · A Formal Basis for the Heuristic Determination of Minimum Cost Paths · IEEE Trans. Systems Science and Cybernetics, 4(2)
- Russell, S. & Norvig, P. 2020 · Artificial Intelligence: A Modern Approach, 4. baskı, Bölüm 3.5 · Pearson
- Pohl, I. 1970 · Heuristic Search Viewed as Path Finding in a Graph (ağırlıklı A*) · Artificial Intelligence, 1(3-4)
ML Academy · an interactive machine learning course that runs in your browser ·
All lessons