Landmarks, Critical Paths and Abstractions: What’s the Difference Anyway?

Graph Search Engineering

计算机科学;物理学

Extended Abstract

PID  :  82464

学科分类：计算机科学（综合）

来源: CEUR

【 摘 要 】

ctions: pattern databases [2], mergeandshrink abstractions [5], andstructural patterns [8] 4. landmarks: LAMA’s hLM [13], and the admissible landmark heuristics hL and hLA [7] These four ideas have been developed in relative isolation: apart from Haslum and Geffner’s result [4] that hmax is a special case of the hm family (hmax = h1), we are not aware of any published formal connections between these approaches. In this work, we prove further results that relate the quality of admissible (optimistic) heuristics from the above four families. Admissible heuristics have a clear notion of dominance: if h(s)h(s) for all states s, then h is superior or equal to h in terms of heuristic quality, with provable consequences for the performance of optimal search algorithms [12]. Dagstuhl Seminar Proceedings 09491Graph Search Engineering