Actions for The min-conflicts heuristic : Experimental and theoretical results

Email RIS file
Bookmark
Report an Issue

The min-conflicts heuristic : Experimental and theoretical results

Author
Philips, Andrew B.
Published
Sep 1, 1991.
Physical Description
1 electronic document
Additional Creators
Laird, Philip, Johnston, Mark D., and Minton, Steven
Online Version

Availability

I Want It
I Want It

Finding items...

Restrictions on Access
Unclassified, Unlimited, Publicly available.
Free-to-read Unrestricted online access
Summary
This paper describes a simple heuristic method for solving large-scale constraint satisfaction and scheduling problems. Given an initial assignment for the variables in a problem, the method operates by searching through the space of possible repairs. The search is guided by an ordering heuristic, the min-conflicts heuristic, that attempts to minimize the number of constraint violations after each step. We demonstrate empirically that the method performs orders of magnitude better than traditional backtracking techniques on certain standard problems. For example, the one million queens problem can be solved rapidly using our approach. We also describe practical scheduling applications where the method has been successfully applied. A theoretical analysis is presented to explain why the method works so well on certain types of problems and to predict when it is likely to be most effective.
Other Subject(s)
Collection
NASA Technical Reports Server (NTRS) Collection.
Note
Document ID: 19920016200.
Accession ID: 92N25443.
NAS 1.15:107877.
NASA-TM-107877.
FIA-91-25.
Terms of Use and Reproduction
No Copyright.
View MARC record | catkey: 15675465