TY - GEN
A1 - Clausecker, Robert
T1 - The Quality of Heuristic Functions for IDA*
N2 - The aim of this thesis is to deepen our understand of how
IDA* heuristics influence the number of nodes expanded during
search. To this end, we develop Korf's formula for the number
of expanded nodes into a heuristic quality η which
expresses the quality of a heuristic function as a constant factor
on the number of expanded nodes, independent of a particular problem
instance.
We proceed to show how to compute η for some common kinds of
heuristics and how to estimate η by means of a random sample for
arbitrary heuristics. Using the value of η for some concrete
examples, we then inspect for which parts of the search space the
values of h(v) are particularly critical to the performance of the
heuristic, allowing us to build better heuristics for future problems.
This report originally appeared as a master thesis at Humboldt
University of Berlin.
T3 - ZIB-Report - 20-17
KW - IDA* heuristic search sampling random walks
Y1 - 2020
UR - https://opus4.kobv.de/opus4-zib/frontdoor/index/index/docId/7848
UR - https://nbn-resolving.org/urn:nbn:de:0297-zib-78489
SN - 1438-0064
ER -