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 U6 - http://nbn-resolving.de/urn/resolver.pl?urn:nbn:de:0297-zib-78489 SN - 1438-0064 ER - TY - GEN A1 - Clausecker, Robert T1 - Notes on the Construction of Pattern Databases N2 - This report aims to explain and extend pattern databases as a tool in finding optimal solutions to combination puzzles. Using sliding tile puzzles as an example, an overview over techniques to construct and use pattern databases is given, analysed, and extended. As novel results, zero aware additive pattern databases and PDB catalogues are introduced. This report originally appeared as a bachelor thesis at Humboldt University of Berlin under the title Notes on the Construction of Tablebases. T3 - ZIB-Report - 17-59 KW - pattern-database 15-puzzle 24-puzzle ida* heuristic-search pdb-catalogue zpdb Y1 - 2017 U6 - http://nbn-resolving.de/urn/resolver.pl?urn:nbn:de:0297-zib-65586 SN - 1438-0064 ER - TY - GEN A1 - Döbbelin, Robert A1 - Schütt, Thorsten A1 - Reinefeld, Alexander T1 - Building Large Compressed PDBs for the Sliding Tile Puzzle N2 - The performance of heuristic search algorithms depends crucially on the effectiveness of the heuristic. A pattern database (PDB) is a powerful heuristic in the form of a pre-computed lookup table. Larger PDBs provide better bounds and thus allow more cut-offs in the search process. Today, the largest PDB for the 24-puzzle is a 6-6-6-6 PDB with a size of 486 MB. We created 8-8-8, 9-8-7 and 9-9-6 PDBs that are three orders of magnitude larger (up to 1.4 TB) than the 6-6-6-6 PDB. We show how to compute such large PDBs and we present statistical and empirical data on their efficiency. The largest single PDB gives on average an 8-fold improvement over the 6-6-6-6 PDB. Combining several large PDBs gives on average an 12-fold improvement. T3 - ZIB-Report - 13-21 KW - heuristic search KW - pattern databases Y1 - 2013 U6 - http://nbn-resolving.de/urn/resolver.pl?urn:nbn:de:0297-zib-18095 SN - 1438-0064 ER - TY - THES A1 - Clausecker, Robert T1 - Notes on the Construction of Tablebases Y1 - 2017 ER -