J. Boutheina and K. Ghédira (Tunisia)
Constraint satisfaction problems, Min-conflict-heuristic, informed backtracking algorithm, Maintaining Arc Consistency algorithm, and backjumping algorithm.
This paper addresses Constraint Satisfaction Problems (CSP), known to be NP-complete, by a family of repair based algorithms. The basic idea of these algorithms is the informed backtracking algorithm (IBt). This latter consists in taking an initial inconsistent assignment and incrementally repairing constraint violations until a solution is achieved. It is guided by a simple ordering heuristic for repairing constraint violations: the Min conflict-heuristic. Although IBt has advantages when compared with the simple backtracking, its efficiency can be improved by enriching it with other simple methods. Two main enhancements of this basic scheme have been proposed: The first new algorithm may be viewed as a strengthening of the IBt process by maintaining full arc consistency. The resulting algorithm is referred to as informed maintaining arc consistency (IMAC). The second enhancement consists in doing intelligent backtracks when the search leads to a dead-end and to integrate the constraint propagation within this backjumping process. To show the advantages of these approaches, experimental comparisons between both IBt and IMAC are given.
Important Links:
Go Back
