.png){kind=icon}
.png){kind=icon}
Return
Decomposable constraints
.png){kind=icon}
PRE
AI
DOI：10.1016/S0004-3702(00)00051-5.png)
.png){kind=icon}
Original request for help.png){kind=icon}
Share.png){kind=icon}
Save
Abstract
En 中文
Many constraint satisfaction problems can be naturally and efficiently modelled using non-binary constraints like the all-different and global cardinality constraints. Certain classes of these nonbinary constraints are network decomposable as they can be represented by binary constraints on the same set of variables. We compare theoretically the levels of consistency which are achieved on non-binary constraints to those achieved on their binary decomposition. We present many results about the level of consistency achieved by the forward checking algorithm and its various generalizations to non-binary constraints. We also compare the level of consistency achieved by arc-consistency and its generalization to non-binary constraints, and identify special cases of non-binary decomposable constraints where weaker or stronger conditions, than in the general case, hold. We also analyze the cost, in consistency checks, required to achieve certain levels of consistency, and we present experimental results on benchmark domains that demonstrate the practical usefulness of our theoretical analysis. (C) 2000 Elsevier Science B.V. All rights reserved.
Keywords:
constraint satisfaction
search
decomposable constraints
generalized arc consistency
maintaining arc consistency
AI Summary
Key information extracted from the uploaded paper, including a brief overview, abstract, background, key highlights, visual analysis, and future outlook.
Journal
IF:
13.9
Papers:
6.1K
Citations:
1.9W
Organization
No organization information available