A Measure of Quality for IDA* Heuristics

Authors

  • Robert K. P. Clausecker Zuse Institute Berlin
  • Florian Schintke Zuse Institute Berlin

Keywords:

Analysis Of Search Algorithms, Combinatorial Puzzles, Self-configuring And Self-tuning Algorithms, Time, Memory, And Solution Quality Trade-offs

Abstract

We present a novel way to judge the performance of IDA* heuristics. With this measure of heuristic quality η, different heuristics for the same problem space can be compared objectively without regards to a particular problem instance. We show how η can be used to model the performance expectations of PDB heuristics. By drawing histograms of the contributions of different parts of the search space to η, we show what parts are most critical to the quality of a heuristic and contribute to the long-standing question on what h values are most critical to the performance of an IDA* heuristic.

Downloads

Published

2021-07-21