Early Work on Optimization-Based Heuristics for the Sliding Tile Puzzle

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