1985 Reports

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.