A*

A* (pronounced “A-star”) is a popular heuristic search algorithm used for pathfinding and graph traversal problems. It is an extension of the uniform-cost search algorithm, combining the advantages of both uniform-cost search and greedy best-first search.

The A* algorithm uses a heuristic function, denoted as h(n), which provides an estimate of the cost from a given node to the goal node. It also uses a cost function, denoted as g(n), which represents the actual cost incurred to reach a particular node from the start node. The algorithm maintains a priority queue of nodes to be expanded, ordered by the sum of g(n) and h(n) values.

The steps of the A* algorithm are as follows:

1. Initialize the open set with the start node and set its g-value to 0.
2. Initialize the closed set as an empty set.
3. While the open set is not empty:

3. Select the node with the lowest f(n) = g(n) + h(n) value from the open set.
4. If the selected node is the goal node, the path has been found. Terminate.
5. Move the selected node from the open set to the closed set.
6. Expand the selected node by considering its neighbors.
7. For each neighbor:

3. Calculate its tentative g-value by adding the cost of reaching the neighbor from the selected node.
4. If the neighbor is already in the closed set and the tentative g-value is higher than its current g-value, skip it.
5. If the neighbor is not in the open set or the tentative g-value is lower than its current g-value:

3. Set the neighbor’s g-value to the tentative g-value.
4. Set the neighbor’s parent as the selected node.
5. If the neighbor is not in the open set, add it to the open set.

4. If the open set is empty and a goal node has not been reached, then a path from the start node to the goal node does not exist.

A* guarantees to find the shortest path from the start node to the goal node, provided that the heuristic function h(n) satisfies certain conditions. The heuristic function must be admissible, meaning it never overestimates the actual cost, and it must be consistent (or monotonic), ensuring that the estimated cost from a node to its neighbor is not greater than the sum of the actual cost and the estimated cost from the neighbor to the goal.

The efficiency of A* depends on the quality of the heuristic function. If the heuristic provides accurate estimates, the algorithm can significantly reduce the search space and find the optimal path more quickly compared to uninformed search algorithms. However, if the heuristic is not well-suited for the problem domain, A* may expand unnecessary nodes and become less efficient.

The A* search algorithm, builds on the principles of Dijkstra’s shortest path algorithm to provide a faster solution when faced with the problem of finding the shortest path between two nodes. It achieves this by introducing a heuristic element to help decide the next node to consider as it moves along the path. You can read more about heuristics in the topic on complexity.

Dijkstra’s algorithm finds the shortest path between the start node and all other nodes. As well as being faster, the A* algorithm differs from Dijkstra’s in that it seeks only the shortest path between the start node and the target node.

Heuristics, sometimes called heuristic functions, are used to provide ‘good enough’ solutions to very complex problems where finding a perfect solution would take too much time. When you use heuristics, you trade accuracy, correctness, and exactness for speedy processing.

One of the drawbacks with Dijkstra’s algorithm is that it can (and will) evaluate paths that will never provide the shortest option. Imagine tring to find the shortest route on a map between London and Edinburgh. Anyone with a reasonable grasp of UK geography, would not bother to evaluate a route that went via Plymouth. The trade off between speed and accuracy is important. In some applications, accuracy is less important than computational time. For example, in a SatNav application a route that is calculated in seconds and is “short enough” is preferable to having to wait 10 minutes for the perfect route.

The A* algorithm uses a heuristic function to help decide which path to follow next. The heuristic function provides an estimate of the minimum cost between a given node and the target node. The algorithm will combine the actual cost from the start node – referred to as g(n) – with the estimated cost to the target node – referred to as h(n) – and uses the result to select the next node to evaluate. This is explained in more detail in the step-by-step method that follows.

Choosing a heuristic function

There is no single best heuristic to use in path finding, as every application is different. For example, if the cost relates to a distance, it could be estimated by calculating the “straight line” distance between the nodes, perhaps by using one of the following methods:

• Euclidian distance
• Manhattan distance
• Great circle distance

However, do remember that the weights on a graph do not always represent distance.

It is very important that the heuristic function does not overestimate costs. However, so long as the heuristic function provides an estimate that is less than or equal to the actual cost, A* will always find an optimal path and will generally find it much faster than Dijkstra’s algorithm.