3

这个问题是关于 python 包约束（参见http://labix.org/python-constraint），特别是内置的“ AllEqualConstraint ”。在涉及 4 个变量的问题中，我想强制前两个和后两个相等，即：

p = Problem()
p.addVariables([1,2,3,4], [0,1])
p.addConstraint(AllEqualConstraint(), [1,2])
p.addConstraint(AllEqualConstraint(), [3,4])

我只有两个解决方案：

for sol in p.getSolutions():
  print sol

> {1: 1, 2: 1, 3: 1, 4: 1}
> {1: 0, 2: 0, 3: 0, 4: 0}

我希望看到四个，即：

> {1: 1, 2: 1, 3: 1, 4: 1}
> {1: 1, 2: 1, 3: 0, 4: 0}
> {1: 0, 2: 0, 3: 1, 4: 1}
> {1: 0, 2: 0, 3: 0, 4: 0}

我的问题是：任何人都可以确认这是包打算计算的内容以及其背后的原因是什么？

Ps：我已经联系了这个包的作者，但还没有得到回复。我知道这个包是相当有名的，并且之前在 StackOverflow 上也有过关于它的问题。

作为对 LVC 的回答：约束并不总是将约束应用于所有变量：

p = Problem()
p.addVariables([1,2,3], [0,1])
p.addConstraint(AllEqualConstraint(), [1,2])

给

> {1: 1, 2: 1, 3: 1}
> {1: 1, 2: 1, 3: 0}
> {1: 0, 2: 0, 3: 1}
> {1: 0, 2: 0, 3: 0}

正如预期的那样。如果AllEqualConstraint不尊重变量，它将非常有限。

4

2 回答 2

2

该模块的源代码包含它如何执行AllEqualConstraint：

def __call__(self, variables, domains, assignments, forwardcheck=False,
             _unassigned=Unassigned):
    singlevalue = _unassigned
    for value in assignments.values():
        if singlevalue is _unassigned:
            singlevalue = value
        elif value != singlevalue:
            return False

在每个中调用它的代码Solver执行以下操作：

for constraint, variables in vconstraints[variable]:
    if not constraint(variables, domains, assignments,
                      pushdomains):
        # Value is not good.
        break

assignments包含所有变量的所有赋值，而不仅仅是受约束影响的变量。这意味着它不关心您输入的变量- 它总是测试潜在解决方案中的所有变量是否相等，这就是为什么您错过了两个不是这种情况的解决方案。AllEqualConstraintaddConstraint

唯一一次AllEqualConstraint看这个variables论点是当它被称为forwardcheck真实时。在这种情况下，它会这样做：

if forwardcheck and singlevalue is not _unassigned:
    for variable in variables:
        if variable not in assignments:
            domain = domains[variable]
            if singlevalue not in domain:
                return False
            for value in domain[:]:
                if value != singlevalue:
                    domain.hideValue(value)

但是，提供的求解器似乎都没有调用forwardcheck除默认值以外的任何值的约束——在 is 的情况AllEqualConstraint下False。

因此，您必须指定自己的手动约束 - 但这并不难，因为它们可以只是接受适当数量变量的函数（它被包装在 a 中FunctionConstraint，所以您不需要关心所有传递给的其他东西Constraint.__call__）。

因此，您想要的约束是一个接受两个变量并返回它们是否相等的函数。operator.eq非常符合要求：

p.addConstraint(operator.eq, [1, 2])
p.addConstraint(operator.eq, [3, 4])

应该给你你正在寻找的结果。

因此，将其扩展到两个以上的变量，您可以编写自己的函数：

def all_equal(a, b, c):
    return a == b == c

或者，更一般地说：

def all_equal(*vars):
    if not vars:
       return True
    return all(var == var[0] for var in vars)
于 2012-08-29T12:29:35.470 回答
1

[评论太长了。]

您所做的编辑并未表明AllEqualConstraint尊重变量限制，只是它并不总是设法完全忽略它们。@lvc 注意到的代码段按照他所说的做了。如果您对其进行检测，您可以看到（为清楚起见，使用a, b, c,d作为变量名）

from constraint import *
p = Problem()
p.addVariables(list("abcd"), [0, 1])
p.addConstraint(AllEqualConstraint(), list("ab"))
p.addConstraint(AllEqualConstraint(), list("cd"))
print p.getSolutions()

最终产生

variables: ['c', 'd']
domains: {'a': [0, 1], 'c': [0, 1], 'b': [1], 'd': [1, 0]}
assignments: {'a': 1, 'c': 0, 'b': 1}
forwardcheck: [[1, 0]]
_unassigned: Unassigned
setting singlevalue to 1 from variable a
returning False because assigned variable c with value 0 != 1

事实上，正如@lvc 所说，它施加了一个a应该 equal的约束c，即使它不应该。我认为相关的循环应该更像

    for key, value in assignments.items():
        if key not in variables: continue

产生

[{'a': 1, 'c': 1, 'b': 1, 'd': 1}, {'a': 1, 'c': 0, 'b': 1, 'd': 0},
 {'a': 0, 'c': 1, 'b': 0, 'd': 1}, {'a': 0, 'c': 0, 'b': 0, 'd': 0}]

虽然我不知道代码是如何工作的，所以很难确定。这对我来说就像一个错误。这似乎不太可能，但它看起来不像AllEqualConstraint在代码库中的任何地方使用（在任何示例中），除了在它自己的文档字符串中，示例测试每个变量都参与约束的情况，因此错误不会出现。

于 2012-08-29T14:37:02.583 回答