Building a Heuristic for Greedy Search

Proceedings of the International Symposium on Combinatorial Search, 8

Volume

Vol. 8 No. 1 (2015): Eighth Annual Symposium on Combinatorial Search

Full Papers

Suboptimal heuristic search algorithms such as greedy best-first search allow us to find solutions when constraints of either time, memory, or both prevent the application of optimal algorithms such as A*. Guidelines for building an effective heuristic for A* are well established in the literature, but we show that if those rules are applied for greedy best-first search, performance can actually degrade. Observing what went wrong for greedy best-first search leads us to a quantitative metric appropriate for greedy heuristics, called Goal Distance Rank Correlation (GDRC). We demonstrate that GDRC can be used to build effective heuristics for greedy best-first search automatically.

10.1609/socs.v6i1.18352