Beginning Java Data Structures and Algorithms

A* Search

The A* search algorithm is a very common algorithm when solving path-finding problems. It also solves the shortest path problem, enhancing Dijkstra's algorithm with the introduction of a heuristic to guide the search. A heuristic is a practical estimate of a given cost, not guaranteed to be optimal or perfect, but sufficient for the immediate goals, or to guide a search. Its basic idea is that, when adding this heuristic to the estimated distance already computed for a node, one can guide the search towards the goal and avoid visiting certain vertices.

For example, if we use the Euclidean distance (for example, the straight line distance between two points) from our location to the exit of a given maze, we can guide the search towards ...