7848
eng
reportzib
0
--
2020-06-09
--
The Quality of Heuristic Functions for IDA*
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.
1438-0064
urn:nbn:de:0297-zib-78489
Robert Clausecker
Robert Clausecker
ZIB-Report
20-17
eng
uncontrolled
IDA* heuristic search sampling random walks
Graph and tree search strategies
Heuristic methods
Random walks on graphs
Sums of independent random variables; random walks
Sampling theory, sample surveys
Distributed Algorithms and Supercomputing
no-project
Clausecker, Robert
https://opus4.kobv.de/opus4-zib/files/7848/ZR-20-17.pdf