Inconsistent heuristics

Uzi Zahavi, Ariel Felner, Jonathan Schaeffer, Nathan SturtevantNational 2007

Abstract

In the field of heuristic search it is well-known that improving the quality of an admissible heuristic can significantly decrease the search effort required to find an optimal solution. Existing literature often assumes that admissible heuristics are consistent, implying that consistency is a desirable attribute. To the contrary, this paper shows that an inconsistent heuristic can be preferable to a consistent heuristic. Theoretical and empirical results show that, in many cases, inconsistency can be used to achieve large performance improvements.
BibTeX
@inproceedings{zahavi2007inconsistent,
  author = {Uzi Zahavi and Ariel Felner and Jonathan Schaeffer and Nathan Sturtevant},
  title = {{Inconsistent heuristics}},
  booktitle = {National},
  year = {2007},
}

Loading related content...

Figure