algorithm - 如何使用对偶图变换将 n 元 CSP 转换为二进制 CSP

Question

当我读这本书 -- 人工智能(一种现代方法)时，我遇到了以下描述将 n 元约束搜索问题转换为二进制问题的方法的句子:

Another way to convert an n-ary CSP to a binary one is the dual graph transformation: create a new graph in which there will be one variable for each constraint in the original graph, and one binary constraint for each pair of constraints in the original graph that share variables. For example, if the original graph has variables {X, Y, Z} and constraints ⟨(X, Y, Z), C1⟩ and ⟨(X, Y ), C2⟩ then the dual graph would have variables {C1, C2} with the binary constraint ⟨(X, Y ), R1 ⟩, where (X, Y ) are the shared variables and R1 is a new relation that defines the constraint between the shared variables, as specified by the original C1 and C2.

我不太明白书中提供的例子，谁能帮忙用另一种方式解释一下，最好提供一个具体的例子？谢谢:D

Answer 1

假设您的问题具有以下约束:

• C1，其中涉及 x、y 和 z:
  • x + y = z
• C2，涉及 x 和 y:
  • x < y

具有以下域:

• x::[1,2,3]
• y::[1,2,3]
• z::[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)必须分别等于 c2 的第一个和第二个元素”(实际上您可以将其拆分为两个更简单的约束条件)