1. Introduction
Recently we’ve looked into Dijkstra’s Algorithm as a way to find the shortest route between any two points. Here we’re going to look at the A* algorithm, which is a more efficient extension of this.
2. A* Algorithm
A* is a relatively simple adjustment to Dijkstra’s algorithm, making it a Best-First Search instead.
This works by having two scoring mechanisms for each node. One is identical to the one used in Dijkstra’s algorithm. The second is a heuristic score for how close a node is to the target node. We then use these to store two different scores against each node – the score for reaching the node on the current route, and the score for selecting a node to visit next.
This has a subtle but significant impact on the way the algorithm works. It means that we always prefer nodes that are closer to our target and avoid visiting nodes that are further away. That, in turn, makes our algorithm more efficient since we’ll be heading in the correct general direction at each step.
Interestingly, if we have a heuristic that always returns 0 then the A* Algorithm is identical to Dijkstra’s Algorithm. This one score is the only difference between the two.
2.1. Pseudocode
The core of the algorithm is very similar to the one we saw for Dijkstra’s algorithm. We just need to take in to account the additional scoring heuristic.
algorithm AStar(graph, startNode, targetNode):
// INPUT
// graph = the graph to search
// startNode = the starting node of the path
// targetNode = the target node of the path
// OUTPUT
// The shortest path from startNode to targetNode using the A* algorithm
for node in graph:
node.score <- infinity
node.heuristicScore <- infinity
node.visited <- false
startNode.score <- 0
startNode.heuristicScore <- 0
while true:
currentNode <- nodeWithLowestScore(graph)
currentNode.visited <- true
for nextNode in currentNode.neighbors:
if not nextNode.visited:
newScore <- calculateScore(currentNode, nextNode)
if newScore < nextNode.score:
nextNode.score <- newScore
nextNode.heuristicScore <- newScore +
calculateHeuristicScore(nextNode, targetNode)
nextNode.routeToNode <- currentNode
if currentNode = targetNode:
return buildPath(targetNode)
if nodeWithLowestScore(graph).score = infinity:
throw NoPathFound
algorithm nodeWithLowestScore(graph):
// INPUT
// graph = the graph from which to find the node with the lowest score
// OUTPUT
// result = the node with the lowest heuristic score that has not been visited
result <- null
for node in graph:
if not node.visited and (result is null
or node.heuristicScore < result.heuristicScore):
result <- node
return result
Our nodeWithLowestScore algorithm is identical to the one from our previous article, only working off of heuristicScore instead. This will then select the node that we believe is the best next node, based on our heuristic. calculateScore and buildPath are also identical to before, giving us the best route through the graph based on the actual scores to reach each node.
2.2. Heuristic Scores
The only part that is missing is our heuristic. This is not something that can easily be described since it is tied to the type of graph that we are finding a path through. The only requirement is that the heuristic score and the actual scores are consistent with each other.
For example, in a geographical graph, this might be based on physical distances between nodes in the graph. Our actual scores could be the number of meters on the route between two nodes, and our heuristic score could be the number of meters on the straight line between the two nodes.
This would then prioritize steps that take us closer to the target, under the hope that these are going to generate a more efficient path. We’d only start to move away from our target if there is no better choice.
3. Properties of A*
The A* algorithm has several properties that make it a fantastic choice for a general-purpose pathfinding algorithm.
3.1. Termination and Completeness
The property of termination means that the algorithm will reach a stop state – that is, it will either find a solution, or it will reach a point where it can no longer progress.
The property of completeness means that the algorithm will always find a solution if there is one to be found.
If we are working on a finite graph where every connection between nodes has a non-negative cost, then the A* algorithm is guaranteed both to terminate and to be complete.
If we are working on an infinite graph, then there are certain conditions under which a solution is guaranteed to be found, but if these are not met, then the algorithm may never terminate.
3.2. Admissibility
The heuristic is considered to be admissible if it never returns a cost that is greater than the optimal cost for the same route. For example, if the most efficient route between two nodes has a cost of n then an admissible heuristic will never return a cost that is greater than this.
Within A*, if the heuristic used is admissible and the algorithm returns a solution, then it is guaranteed that this solution will be the optimal one. If the heuristic is not admissible, then the algorithm may prefer less optimal routes, though this won’t stop it from finding a solution.
If the heuristic is admissible, then we are guaranteed to find the optimal solution. However, if there are multiple paths that all have the same cost, then they will all get explored, which will cause a higher overall processing cost. By relaxing the admissibility criteria, we can avoid this situation, but at the risk of an overall worse solution.
Instead, we can relax the admissibility criteria but only within certain bounds. This will allow us to discover a path that is optimal enough, but doing so in a more efficient way.
4. Complexity
The time complexity of A* depends on the quality of the heuristic function. In a worst-case, the algorithm can be O(b^d), where b is the branching factor – the average number of edges from each node, and d is the number of nodes on the resulting path.
The better the heuristic function, the less of these nodes need to be visited, and so the complexity drops. We can describe the result of the heuristic function as the effective branching factor – the average number of edges from each node that we need to visit.
Dijkstra’s Algorithm has an effective branching factor that is exactly the same as the overall branching factor. A perfectly optimal heuristic function will give us an effective branching factor of 1 – i.e., from every node, we’ll only ever have one edge to visit. The reality is likely somewhere between, and where on this scale will determine the time complexity of the search.
The space complexity of standard A* is always O(b^d), since we need to track every node in the graph at all times, even ones that we’ve never visited and are never going to. There are optimizations around this that can be made by only adding nodes to our algorithm as they become relevant, or by forgetting nodes as they become less relevant. Still, these all have potential impacts on the overall output.
5. Conclusion
Here we’ve studied how the A* algorithm works, including some details on what can make it work better or worse in some cases. We’ve previously seen a practical implementation of this.