如何使用双图转换将n-ary CSP转换为二进制CSP

Question

当我读到这本书 - 人工智能(一种现代方法)时,我遇到了以下句子,描述了将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]
• y :: [1,2,3]
• z :: [1,2,3]

作者说你需要再创建两个变量,每个变量一个.它们的定义如下:

• 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个元素"(实际上你可以将它分成两个更简单的约束)