17

本 -- 人工知能 (最新のアプローチ) を読んだとき、n-ary Constraint Search Problem を 2 項に変換する方法を説明している次の文に出くわしました。

n-ary CSP をバイナリ CSP に変換するもう 1 つの方法は、デュアル グラフ変換です。元のグラフの制約ごとに 1 つの変数があり、元のグラフの制約のペアごとに 1 つのバイナリ制約がある新しいグラフを作成します。変数を共有するグラフ。たとえば、元のグラフに変数 {X, Y, Z} と制約 ⟨(X, Y, Z), C1⟩ および ⟨(X, Y ), C2⟩ がある場合、双対グラフには変数 {C1, C2 があります。ここで、(X, Y ) は共有変数であり、R1 は共有変数間の制約を定義する新しい関係であり、元の C1 と C2 で指定されています。

本で提供されている例がよくわかりません。別の方法で説明するのを手伝ってくれる人はいますか?具体的な例を提供する方がよいでしょうか? ありがとう

4

1 に答える 1

21

問題に次の制約があるとします。

  • x、y、z を含む C1:
    • x + y = z
  • x と y を含む C2:
    • x < y

次のドメイン:

  • x :: [1,2,3]
  • y :: [1,2,3]
  • z :: [1,2,3]

著者は、制約ごとに 1 つずつ、さらに 2 つの変数を作成する必要があると述べています。それらは次のように定義されます。

  • c1 = < x、y、z >
  • c2 = < x, y >

c1 と c2 のドメインは、C1 と C2 に違反しないように定義されています。

  • c1 :: [ <1,2,3>, <2,1,3>, <1,1,2>]
  • c2 :: [<1,2>, <2,3>, <1,3>]

c1 と c2 は双対グラフのノードになりますが、最初にそれらの間の制約、つまり R1 を定義する必要があります。

  • R1: 「c1 の 1 番目と 2 番目の要素 (x と y) は、c2 の 1 番目と 2 番目の要素とそれぞれ等しくなければなりません」(実際には、2 つの単純な制約に分割できます)
于 2014-04-05T13:37:12.870 に答える