17

当我阅读《人工智能（一种现代方法）》一书时，我遇到了以下句子，描述了将 n 元约束搜索问题转换为二进制问题的方法：

将 n 元 CSP 转换为二元 CSP 的另一种方法是对偶图转换：创建一个新图，其中原始图中的每个约束都有一个变量，原始图中的每对约束都有一个二元约束共享变量的图形。例如，如果原始图具有变量 {X, Y, Z} 和约束 ⟨(X, Y, Z), C1⟩ 和 ⟨(X, Y ), C2⟩，则对偶图将具有变量 {C1, C2 } 具有二元约束 ⟨(X, Y ), R1 ⟩，其中 (X, Y ) 是共享变量，R1 是定义共享变量之间约束的新关系，由原始 C1 和 C2 指定。

我不太了解书中提供的示例，任何人都可以帮助以另一种方式解释它，并且可以更好地提供一个具体的例子吗？感谢：D

4

1 回答 1

21

假设您的问题有以下限制：

  • 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 的第一个和第二个元素”（实际上您可以将其拆分为两个更简单的约束）
于 2014-04-05T13:37:12.870 回答