1985 Reports

# Generating Admissible Heuristics by Criticizing Solutions to Relaxed Models

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.

## Subjects

## Files

- cucs-219-85.pdf application/pdf 1.27 MB Download File

## More About This Work

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