Generating Admissible Heuristics by Criticizing Solutions to Relaxed Models

Hansson, Othar; Mayer, Andrew E.; Yung, Moti

This paper examines one paradigm used to develop admissible heuristics: problem relaxation [10, 11,32]. This consists of three steps: simplify (or relax) a problem, solve the simplified problem, and use that solution as advice to guide the search for a solution to the original problem. We introduce an extension to this methodology which exploits the simplicity of relaxed models. By criticizing the feasibility of a relaxed solution, we arrive at a closer approximation of the solution to the original problem. This solution-criticism process recovers some of the information lost by relaxation. and yields more powerful admissible heuristics than by relaxation alone. We apply our methodology to the Traveling-Salesman problem and the N Puzzle. For the Traveling-Salesman Problem, it yields the well known. admissible minimum spanning tree heuristic. For the Eight and Fifteen Puzzles (in general the N puzzle), it yields a new heuristic which performs significantly better than all previously known heuristics.



More About This Work

Academic Units
Computer Science
Department of Computer Science, Columbia University
Columbia University Computer Science Technical Reports, CUCS-219-85
Published Here
November 7, 2011