3

この質問は、python パッケージの制約( http://labix.org/python-constraintを参照)、特に組み込みの " AllEqualConstraint " に関するものです。4 つの変数を含む問題では、最初の 2 つと次の 2 つが等しくなるように強制したいと思います。

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

私は2つの解決策しか得られません:

for sol in p.getSolutions():
  print sol

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

つまり、次の4つが表示されると予想されます。

> {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制約の影響を受ける変数だけでなく、すべての変数のすべての割り当てが含まれます。これは、入力した変数を気にしないことを意味します。潜在的な解のすべての変数が等しいことを常にテストします。これが、そうでない場合に 2 つの解を見逃す理由です。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。

したがって、独自の手動の制約を指定する必要がありますが、これはそれほど難しくありません。適切な数の変数を取る関数である可能性があるためです ( でラップされるFunctionConstraintため、すべてを気にする必要はありません)。に渡される他のものConstraint.__call__)。

したがって、制約として必要なのは、2 つの変数を取り、それらが等しいかどうかを返す関数です。operator.eq法案にうまく適合します：

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

探している結果が得られるはずです。

したがって、これを 2 つ以上の変数にスケーリングすると、独自の関数を作成できます。

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ます。bcd

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等しくないはずの制約を課して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、その例ではすべての変数が制約に参加するケースをテストする独自の docstring を除いて (どの例にもありません)、そのためバグ表示されません。

于 2012-08-29T14:37:02.583 に答える