Editing A* search algorithm (section)

==Complexity==

As a heuristic search algorithm, the performance of A* is heavily influenced by the quality of the heuristic function <math display="inline">h(n)</math>. If the heuristic closely approximates the true cost to the goal, A* can significantly reduce the number of node expansions. On the other hand, a poor heuristic can lead to many unnecessary expansions.

===Worst-Case Scenario===
In the worst case, A* expands all nodes <math display="inline">n</math> for which <math display="inline">f(n)=g(n)+h(n) \leq C^{*}</math>, where <math display="inline">C^{*}</math> is the cost of the optimal goal node.

==== Why can’t it be worse ====
Suppose there is a node <math display="inline">N'</math> in the open list with <math display="inline">f(N') > C^{*}</math>, and it's the next node to be expanded. Since the goal node has <math display="inline">f(goal)=g(goal)+h(goal)=g(goal)=C^{*}</math>, and <math display="inline"> f(N') > C^{*} </math>, the goal node will have a lower f-value and will be expanded before <math display="inline">N'</math>. Therefore, A* never expands nodes with <math display="inline"> f(n) > C^{*} </math>.

==== Why can’t it be better ====
Assume there exists an optimal algorithm that expands fewer nodes than <math display="inline"> C^{*} </math> in the worst case using the same heuristic. That means there must be some node <math display="inline"> N' </math> such that <math display="inline"> f(N') < C^{*} </math>, yet the algorithm chooses not to expand it.

Now consider a modified graph where a new edge of cost <math display="inline"> \varepsilon </math> (with <math display="inline"> \varepsilon > 0 </math>) is added from <math display="inline"> N' </math> to the goal. If <math display="inline"> f(N')+\varepsilon<C^{*} </math>, then the new optimal path goes through <math display="inline"> N' </math>. However, since the algorithm still avoids expanding <math display="inline"> N' </math>, it will miss the new optimal path, violating its optimality.

Therefore, no optimal algorithm including A* could expand fewer nodes than <math display="inline"> C^{*} </math> in the worst case.

==== Mathematical Notation ====
The worst-case complexity of A* is often described as <math display="inline">O(b^d)</math>, where <math>b</math> is the branching factor and <math display="inline">d</math> is the depth of the shallowest goal. While this gives a rough intuition, it does not precisely capture the actual behavior of A*.

A more accurate bound considers the number of nodes with <math display="inline">f(n) \leq C^{*}</math>. If <math>\varepsilon</math> is the smallest possible difference in <math display="inline">f</math>-cost between distinct nodes, then A* may expand up to:
{{center|<math>O\left(\frac{C^{*}}{\varepsilon}\right)</math>}}

This represents both the time and space complexity in the worst case.

===Space Complexity===

The [[space complexity]] of A* is roughly the same as that of all other graph search algorithms, as it keeps all generated nodes in memory.<ref name=":2" /> In practice, this turns out to be the biggest drawback of the A* search, leading to the development of memory-bounded heuristic searches, such as [[Iterative deepening A*]], memory-bounded A*, and [[SMA*]].