The A algorithm* is a shortest path algorithm for weighted graphs. It can outperform Dijkstra’s algorithm by using problem-specific heuristic functions in the wavefront sorting and ordering, so it’s broadly used for its efficiency. It essentially looks into the most promising partial solutions first, i.e., it acts as a best-first search.
The heuristic function must not overpredict, to guarantee the best path.
It has a worst-case time complexity of . We keep roughly the same complexity as UCS.
Properties
A* is a complete algorithm so long as:
- The branching factor is finite, and the solution has a finite cost.
- Every action has a finite cost .
- is non-negative for every node that can be reached from the initial node.
- is finite for a node that can be extended to reach a goal node.
A* is also optimal, so long as the heuristic is admissible, i.e., that the estimates are less than the actual costs.
By theorem, A* with a non-negative, admissible heuristic, always finds an optimal cost solution if a solution exists, so long as:
- The branching factor is finite.
- Every action has a finite cost .
The above also holds if the heuristic is consistent AND we use cycle checking.
slide 25: finds path SBG non-optimal, which motivates next slides
slide 27:
A* with cycle checking — would not eliminate any promising nodes even when cycle checking is applied, it must be the minimum cost path to a goal state
IDA* — time much more costly, but linear space