| タイトル | Minimizing conflicts: A heuristic repair method for constraint-satisfaction and scheduling problems |
| 本文（外部サイト） | http://hdl.handle.net/2060/19930006097 |
| 著者（英） | Minton, Steve; Laird, Phil; Philips, Andrew; Johnston, Mark |
| 著者所属（英） | NASA Ames Research Center |
| 発行日 | 1992-06-01 |
| 言語 | eng |
| 内容記述 | This paper describes a simple heuristic approach to solving large-scale constraint satisfaction and scheduling problems. In this approach one starts with an inconsistent assignment for a set of variables and searches through the space of possible repairs. The search can be guided by a value-ordering heuristic, the min-conflicts heuristic, that attempts to minimize the number of constraint violations after each step. The heuristic can be used with a variety of different search strategies. We demonstrate empirically that on the n-queens problem, a technique based on this approach performs orders of magnitude better than traditional backtracking techniques. We also describe a scheduling application where the approach has been used successfully. A theoretical analysis is presented both to explain why this method works well on certain types of problems and to predict when it is likely to be most effective. |
| NASA分類 | CYBERNETICS |
| レポートNO | 93N15286
NASA-TM-108121
FIA-92-21
NAS 1.15:108121 |
| 権利 | No Copyright |
