如何使用双图转换将n元CSP转换为二进制CSP [英] How to convert n-ary CSP to binary CSP using dual graph transformation

问题描述

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

When I read the book -- Artificial Intelligence (a modern approach), I came across the following sentence describing the method to convert a n-ary Constraint Search Problem to a binary one:

将n元CSP转换为二进制图的另一种方法是对偶图
转换：创建一个新图，其中将有一个变量
表示原始图中每个约束，b表示每个原始图中每个共享
变量的约束。例如，如果原始图具有变量{X，Y，Z}
和约束⟨（X，Y，Z），C1⟩和⟨（X，Y），C2⟩，则对偶图
将具有二元约束⟨（X，Y），R1
variables的变量{C1，C2}，其中（X，Y）是共享变量，R1是新关系
，它定义了共享变量之间的约束，如原始C1和C2指定的
。

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

I don't quite get the example provided in the book, can anybody help to explain it in another way and may better provide a concrete example? thanks :D

推荐答案

比方说，您的问题有以下限制条件：

Let's say your problem has the following constraints:

• C1，涉及x，y和z：
  
  
  
  • x + y = z
  
  
  
  
  • x< y
  
  

  具有以下域：

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

  作者说，您需要再创建2个变量，每个约束一个。它们的定义如下：

  The author says that you need to create 2 more variables, one for each constraint. They are defined as follows:

  
  
  • c1 =< x，y，z>
  
  
  • c2 =< x，y>
  
  

  定义了c1和c2的域，以便它们不违反C1和C2，即：

  The domains of c1 and c2 are defined so that they don't violate C1 and C2, i.e.:

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

  c1和c2是对偶图的节点，但是首先您需要在它们之间定义一个约束，即R1：

  c1 and c2 will be the nodes of the dual graph, but first you need to define a constraint between them, i.e. R1:

  
  
  • R1： c1的第一个元素和第二个元素（x和y）必须分别等于c2的第一个元素和第二个元素（实际上，您可以将其分为两个更简单的约束）
  
  

  这篇关于如何使用双图转换将n元CSP转换为二进制CSP的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！