Ariel Felner

Optimization-based heuristics may offer very good estimates. But, calculating them may be time consuming, especially if the optimization problem is intractable. This raises the question of their applicability. This paper summarizes early work from the year 2000 on optimization-based heuristics in the context of PDBs for the Tile-Puzzle. We show that an admissible heuristic based on Vertex-Cover (VC) can be calculated in reasonable time over a large collection of small PDBs. When larger PDBs are involved we suggest the idea of using another lookup table that precalculates and stores all possible relevant VC values. This table can be later looked up in a constant time during the search. We discuss the conditions under which this idea can be generalized. Experimental results demonstrate the applicability of these two ideas on the 15- and 24-Puzzle. The first idea appeared in (Felner, Korf, and Hanan 2004) but the second idea is presented here for the first time.