On the Dual Representation of Non-binary Semiring-based CSPs
On the Dual Representation of Non-binary Semiring-based CSPs
复制标题
基于非二进制半环的 CSP 的对偶表示
DOI：
--
复制
发表时间：
2000
期刊：
影响因子：
--
通讯作者：
R. Dechter
中科院分区：
文献类型：
--
作者：
J. Larrosa;R. Dechter
众所周知，任何非二进制CSP都可以重新表示为二进制CSP。在本文中，我们表明，相同的翻译方法可以适用于软约束框架。我们观察到，任何非二进制软约束CSP可以重新制定为一个问题，只有二元和一元的约束。有趣的是，翻译导致二元约束是硬的（强制性满足的条件）和一元约束是软的（在一组解决方案中的偏好标准）。我们阐述了我们的观察在半环为基础的框架。
It is well known that any non-binary CSP can be reformulated as a binary CSP. In this paper we show that the same translation methods can be applied in the soft constraints framework. We observe that any non-binary soft constraint CSP can be reformulated as a problem with only binary and unary constraints. Interestingly, the translation leads to binary constraints that are hard (de ne conditions of mandatory satisfaction) and unary constraints that are soft (de ne a preference criterion among the set of solutions). We elaborate our observation in the semiringbased framework.