The Quality of Heuristic Functions for IDA*

Please always quote using this URN: urn:nbn:de:0297-zib-78489

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.

Metadaten
Author:	Robert Clausecker
Document Type:	ZIB-Report
Tag:	IDA heuristic search sampling random walks*
MSC-Classification:	05-XX COMBINATORICS (For finite fields, see 11Txx) / 05Cxx Graph theory (For applications of graphs, see 68R10, 81Q30, 81T15, 82B20, 82C20, 90C35, 92E10, 94C15) / 05C81 Random walks on graphs
	60-XX PROBABILITY THEORY AND STOCHASTIC PROCESSES (For additional applications, see 11Kxx, 62-XX, 90-XX, 91-XX, 92-XX, 93-XX, 94-XX) / 60Gxx Stochastic processes / 60G50 Sums of independent random variables; random walks
	62-XX STATISTICS / 62Dxx Sampling theory, sample surveys / 62D05 Sampling theory, sample surveys
CCS-Classification:	I. Computing Methodologies / I.2 ARTIFICIAL INTELLIGENCE / I.2.8 Problem Solving, Control Methods, and Search (F.2.2) / Graph and tree search strategies
	I. Computing Methodologies / I.2 ARTIFICIAL INTELLIGENCE / I.2.8 Problem Solving, Control Methods, and Search (F.2.2) / Heuristic methods
Date of first Publication:	2020/06/09
Series (Serial Number):	ZIB-Report (20-17)
ISSN:	1438-0064

Open Access