Introduction to the A* Algorithm (2014)

Excellent article - I recently worked on some pathfinding stuff and the material I found on A* was not that great but this is very well laid out. Important side note: A* or other "best path" algorithms are not always preferable - there are some situations where it makes sense to use even less ideal paths in exchange for greater speed and less memory usage - even ones that are faster than greedy-best-first search with A* shown here. If you…

The article doesn't explicitly state it in this manner in one concise place, but the way I would always think about A* from a "practical/easy-to-remember" perspective back when I was doing competitive programming is that they're all the same algorithm, but with different priorities on the priority queue: Breadth-first Search: Priority is order of discovery of edges (that is, no priority queue/just a regular queue) Dijkstra: Priority is distance so far + next edge distance A*: Priority is distance so…

There is an interesting probabilistic angle of this classic AI story with Machine Learning applications here: https://github.com/imagry/aleph_star (paper, presentation, etc).

This is a very nice introduction. Well done.