Others view: universal edit button ♦ Nussinov algorithm ♦ XOR gate ♦ RSA encryption algorithm ♦ Complex integral ♦ 2D Fast Fourier Transform ♦ Welcome ♦ rss.xml ♦ wave interference ♦ Suffix tree ♦

A star algorithm

A* is the graph search and traversal algorithm that makes use of some additional function that decreases when we are approaching the goal node in the graph.

A* algorithm. You can set another node as goal with the right mouse click. Drag to connect the nodes. In the combo box, you can select other algorithms as well.
The helper function (called heuristic function) needs no be precise but it must not overestimate the distance till the goal. If the graph exists in real world space (roads, railways, computer networks, etc), the good value for this function is the spatial ("euclidean") distance till the goal node. Heuristic function must be known for every node in the graph (it is zero for the goal node). Dijkstra algorithm is a separate case of A* algorithm where heuristic function is always zero (0).

The algorithm

Same as Dijkstra algorithm, the algorithm assigns the "distance value" to every node. This value is the distance (cost) to reach the node from the initial (starting) node. This value is of course zero for the initial node itself. At the start of the algorithm, it is set to be infinite for all other nodes in the graph. The algorithm also needs to remember the collection of already visited nodes. The "current node" is initially set to the initial node.

The algorithm can be implemented as following:

  1. For current node, calculate the tentative distance for all its unvisited neighbours. For example, if current node (A) has distance of 7, and an edge connecting it with another node has a traversing cost of 2, the distance to B through A will be 7+2=9. If some larger distance has been previously assigned to this node, overwrite the distance.
  2. Mark the current node as visited. A visited node will not be checked ever again. The distance, assigned to this node, is now is final and minimal.
  3. For the next visit, select the node n that has the smallest value of d(n) + h(n), where d is the tentative distance (not different from Dijkstra algorithm) and h is the previously described heuristic function (say Euclidean distance between the n and the goal node.
  4. Set the unvisited node with the smallest distance (from the start node, considering all nodes in graph) as the next "current node" and continue from step 1.

The algorithms terminates when the goal node becomes the current node. The found path is not stored in the algorithm data structures and must be separately recorded. If the algorithm works as expected, it visits only part of all nodes in the graph (nodes that are clearly not in the shortest patch are not visited).

This algorithm is similar to the algorithm of the car driver that prefers roads bringing him geographically closer to the goal. This usually works well enough in the real world roads. Surely it is possible to imagine "traps" when it is not possible to cross some obstacle close to the goal and it is necessary to return back searching for another way, but this is not frequent.

In the worst case the algorithm running time is exponential to the length of the existing shortest path, but under some better circumstances it should be polynomial[1]. If the h(n) is useful, it should outperform the plain Dijkstra search algorithm.

Improvements

A* is a breadth first algorithm and as such consumes huge memory to keep the data of current proceeding nodes[2] . The search can be more efficient if the machine searches not just for the path from the source to the target, but also in parallel for the path from the target to the source (the answer is found when these two searches meet at some point).

References

  1. 1 A* algorithm page on Wikipedia
  2. 2 Lei Niu, Guobin Zhuo. An improved real 3D algorithm for difficult path finding situation.