如何使用雙圖形變換

Question

當我讀了這本書n元CSP轉換爲二進制CSP - 人工智能（現代方法），我碰到下面的句子來描述方法來轉換一個n元約束搜索問題爲二進制一個：

另一種方法的n進制CSP轉換爲二進制一個是對偶圖 變換：創建一個新的曲線圖，其中將有一個可變 在原始圖中的每個約束，並且對於共享 變量的原始圖中的每對約束，一個二進制約束 。例如，如果原始圖具有變量{X，Y，Z} 和約束⟨（X，Y，Z），C1⟩和⟨（X，Y），然後C2⟩對偶圖 將具有變量{C1 ，C2}與二元約束⟨（X，Y）中，R1 ⟩，其中（X，Y）是共享變量和R1是一個新的關係 定義共享變量之間的約束，如由初始指定 C1和C2。

我不太清楚書中提供的例子，有人可以用另一種方式幫助解釋它，並且可能更好地提供一個具體的例子嗎？感謝：d

Answer 1

比方說，你的問題有以下限制：

• C1，其中包括X，Y和Z：
  • X + Y = Z
• C2，其涉及x和y：
  • x < y

與下列結構域：

• X :: [1,2,3]
• ÿ:: [1,2,3]
• Ž:: [1,2 3]

作者說你需要創建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（x和y）的第二個元素必須等於1號分別c2的第二個元素」（其實你可以用兩個簡單的約束條件將其分割）