National Conference on Artificial Intelligence · 1993 · 322 citations · 9 references
ComputingComputer ScienceAlgorithmic DesignAlgorithmsOptimizationConstrained OptimizationConstraint SatisfactionConstraint SolvingHeuristic OptimizationIterative SolversMetaheuristic OptimizationConstraint OptimizationConstraint Optimization ProblemsConstraint Satisfaction SearchConstraint-based OptimizationIterative ImprovementLocal SearchLocal Search Algorithms
A number of algorithms have recently been proposed that use iterative improvement (a form of hill-climbing) to solve constraint satisfaction problems. These techniques have had dramatic success on certain problems. However, one factor limiting their wider application is the possibility of getting stuck at non-solution local minima. In this paper we describe an iterative improvement algorithm, called Breakout, that can escape from local minima. We present empirical evidence that this method is very effective in cases where previous approaches have difficulty. Although Breakout is not theoretically complete, in practice it appears to almost always find solutions, for solvable problems. We prove that an idealized (but less efficient) version of the algorithm is complete.
9
A new method for solving hard satisfiability problems
Bart Selman, Hector J. Levesque, David G. M. Mitchell · 1992 · 1.2K citations
Where the really hard problems are
Peter Cheeseman, Bob Kanefsky, William M. Taylor · 1991 · 1K citations
Richard E. Korf · Artificial Intelligence · 1990 · 919 citations