Editing A* search algorithm (section)

==== 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.