A*
Is a graph traversal and path search algorithm, which is often used in many fields of computer science due to its completeness, optimality, and optimal efficiency. One major practical drawback is its O(b^d) space complexity, as it stores all generated nodes in memory. Thus, in practical travel-routing systems, it is generally outperformed by algorithms which can pre-process the graph to attain better performance, as well as memory-bounded approaches; however, A* is still the best solution in many cases. A* achieves better performance by using heuristics to guide its search. [Source: Wikipedia]
Complexity
| Name | Best time | Space | Comments |
|---|---|---|---|
| A* | bd | bd | |
| A* | v + e | v + e | Same as above |
* Where v = number of visited vertices; e = number of visited edges
* Where b = branching factor of the tree/graph, d = depth of the goal node.