The Tractability of Global Constraints
The Tractability of Global Constraints
复制标题
全局约束的可处理性
DOI：
--
复制
发表时间：
2004
期刊：
影响因子：
--
通讯作者：
T. Walsh
中科院分区：
文献类型：
--
作者：
C. Bessiere;E. Hébrard;Brahim Hnich;T. Walsh
约束传播是约束规划成功的核心技术之一。快速算法用于在回溯搜索之前或期间修剪搜索空间。传播全局约束通常是棘手的。在本文中，我们描述了一些与约束传播相关的重要问题。例如，我们考虑两个问题：“这个问题是广义弧一致吗？”和“最大广义弧一致域是什么？”对于有限域变量，我们确定了这些问题的易处理性和难处理性之间的依赖关系。最后，我们证明了一系列全局约束的难解性。
Constraint propagation is one of the techniques central to the success of constraint programming. Fast algorithms are used to prune the search space either before or during backtracking search. Propagating global constraints is intractable in general. In this paper, we characterize a number of important questions related to constraint propagation. For example, we consider the two questions: "Is this problem generalized arc-consistent?" and "What are the maximal generalized arc-consistent domains?". We identify dependencies between the tractability and intractability of these questions for finite domain variables. Finally, we prove intractability for a range of global constraints.