Editing A* search algorithm (section)

===Optimality and consistency===

Algorithm A is optimally efficient with respect to a set of alternative algorithms '''Alts''' on a set of problems '''P''' if for every problem P in '''P''' and every algorithm A′ in '''Alts''', the set of nodes expanded by A in solving P is a subset (possibly equal) of the set of nodes expanded by A′ in solving P. The definitive study of the optimal efficiency of A* is due to Rina Dechter and Judea Pearl.<ref name=":1">{{cite journal
 | first = Rina
 | last = Dechter
 |author2= Judea Pearl
 | title = Generalized best-first search strategies and the optimality of A*
 | journal = [[Journal of the ACM]]
 | volume = 32
 | issue = 3
 | pages = 505–536
 | year = 1985
 | doi = 10.1145/3828.3830
 | s2cid = 2092415
 | doi-access = free
 }}
</ref>
They considered a variety of  definitions of '''Alts''' and '''P'''  in combination with A*'s heuristic being merely admissible or being both [[Consistent heuristic|consistent]] and admissible.  The most interesting positive result they proved is that A*, with a consistent heuristic, is optimally efficient with respect to all admissible A*-like search algorithms on all "non-pathological" search problems.  Roughly speaking, their notion of the non-pathological problem is what we now mean by "up to tie-breaking".  This result does not hold if A*'s heuristic is admissible but not consistent. In that case, Dechter and Pearl showed there exist admissible A*-like algorithms that can expand arbitrarily fewer nodes than A* on some non-pathological problems.

Optimal efficiency is about the ''set'' of nodes expanded, not the ''number'' of node expansions (the number of iterations of A*'s main loop).  When the heuristic being used is admissible but not consistent, it is possible for a node to be expanded by A* many times, an exponential number of times in the worst case.<ref name="Martelli">{{cite journal
 | first = Alberto
 | last = Martelli
 | title = On the Complexity of Admissible Search Algorithms
 | journal = [[Artificial Intelligence]]
 | volume = 8
 | issue = 1
 | pages = 1–13
 | year = 1977
 | doi = 10.1016/0004-3702(77)90002-9
 }}
</ref>
In such circumstances, Dijkstra's algorithm could outperform A* by a large margin. However, more recent research found that this pathological case only occurs in certain contrived situations where the edge weight of the search graph is exponential in the size of the graph and that certain inconsistent (but admissible) heuristics can lead to a reduced number of node expansions in A* searches.<ref name="Felner2011">{{cite journal | first = Ariel | last = Felner | author2 = Uzi Zahavi | title = Inconsistent heuristics in theory and practice | journal = [[Artificial Intelligence]] | volume = 175 | issue = 9–10 | pages = 1570–1603 | year = 2011 | doi = 10.1016/j.artint.2011.02.001| doi-access = free }}</ref><ref name="Zhang2009">{{cite conference | first1 = Zhifu | last1 = Zhang | author2 = N. R. Sturtevant | date = 2009 | title = Using Inconsistent Heuristics on A* Search | conference = Twenty-First International Joint Conference on Artificial Intelligence |url=https://www.aaai.org/ocs/index.php/IJCAI/IJCAI-09/paper/viewPDFInterstitial/413/726 |pages=634–639}}</ref>