Principles and Practice of Constraint Programming - CP 2010
Principles and Practice of Constraint Programming - CP 2010
复制标题
约束规划原理与实践 - CP 2010
DOI：
10.1007/978-3-642-15396-9_15
复制
发表时间：
2010
期刊：
影响因子：
--
通讯作者：
Cooper M
中科院分区：
文献类型：
--
作者：
Cooper M
约束满足问题（CSP）是人工智能领域的一个核心问题。在确定确保此类问题可处理性的特性方面已经作出了相当大的努力。本文研究了软约束问题的混合可跟踪性；也就是说，保证给定软约束问题的可跟踪性的属性，但这些属性不仅依赖于实例的底层结构（例如树状结构）或仅依赖于实例中的软约束类型（例如子模块化）。首先给出了实例结构中由禁止子图定义的两类混合软约束问题。这些类允许二进制清晰约束与任意一元软约束的特定组合。然后，我们引入联合赢家性质，使我们能够定义一类具有软二元约束和一元约束的新型混合可处理软约束问题。这个类泛化了带有任意一元软约束的theSoftAllDiffconstraint。我们证明了联合赢家性质在多项式时间内易于识别，并提出了一类满足联合赢家性质的软约束问题的基于最大流量的多项式时间算法。此外，我们表明，如果成本函数只能取两个不同的值，则该类是最大的。
The constraint satisfaction problem (CSP) is a central generic problem in artificial intelligence. Considerable effort has been made in identifying properties which ensure tractability in such problems. In this paper we study hybrid tractability of soft constraint problems; that is, properties which guarantee tractability of the given soft constraint problem, but properties which do not depend only on the underlying structure of the instance (such as being tree-structured) or only on the types of soft constraints in the instance (such as submodularity).We firstly present two hybrid classes of soft constraint problems defined by forbidden subgraphs in the structure of the instance. These classes allow certain combinations of binary crisp constraints together with arbitrary unary soft constraints.We then introduce the joint-winner property, which allows us to define a novel hybrid tractable class of soft constraint problems with soft binary and unary constraints. This class generalises theSoftAllDiffconstraint with arbitrary unary soft constraints. We show that the joint-winner property is easily recognisable in polynomial time and present a polynomial-time algorithm based on maximum-flows for the class of soft constraint problems satisfying the joint-winner property. Moreover, we show that if cost functions can only take on two distinct values then this class is maximal.