DocumentCode :
3319750
Title :
Extended analysis of intelligent backtracking algorithms for the maximal constraint satisfaction problem
Author :
Padmanabhuni, Srinivas
Author_Institution :
Dept. of Comput. Sci., Alberta Univ., Edmonton, Alta., Canada
Volume :
3
fYear :
1999
fDate :
9-12 May 1999
Firstpage :
1710
Abstract :
Overconstrained systems refer to sets of soft constraints which do not permit a solution satisfying all the constraints. The overconstrainedness in such soft-constraint systems can be manifested in a wide variety of structures, including weighted constraints, partially ordered constraints, constraint hierarchies and references. The simplest among these formalisms is the maximal constraint satisfaction problem (CSP), where a solution is sought which satisfies the maximum number of constraints. In this paper, backtracking algorithms and their intelligent versions used in the ordinary CSP context, are studied in context of the maximal CSP. The algorithms of E.C. Freuder and R.J. Wallace (1995) for depth-first branch-and-bound and backjumping are extended to conflict-directed backjumping. A theoretical analysis of the problem of application of intelligent backtracking algorithms for maximal CSP is provided.
Keywords :
artificial intelligence; backtracking; constraint theory; operations research; optimisation; tree searching; conflict-directed backjumping; constraint hierarchies; depth-first branch-and-bound technique; intelligent backtracking algorithms; maximal constraint satisfaction problem; maximum constraint number; overconstrained systems; partially ordered constraints; references; soft constraints; weighted constraints; Algorithm design and analysis; Constraint theory; Educational institutions;
fLanguage :
English
Publisher :
ieee
Conference_Titel :
Electrical and Computer Engineering, 1999 IEEE Canadian Conference on
Conference_Location :
Edmonton, Alberta, Canada
ISSN :
0840-7789
Print_ISBN :
0-7803-5579-2
Type :
conf
DOI :
10.1109/CCECE.1999.804975
Filename :
804975
Link To Document :
بازگشت