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


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

另一种将n-ary CSP转换为二进制CSP的方法是双图   转换：创建一个新图形，其中将有一个变量   对于原始图中的每个约束，以及一个二进制约束   对于共享的原始图中的每对约束   变量。例如，如果原始图形具有变量{X，Y，Z}   和约束⟨（X，Y，Z），C1⟩和⟨（X，Y），C2⟩然后是双图   将有变量{C1，C2}与二元约束⟨（X，Y），R1   ⟩，其中（X，Y）是共享变量，R1是新关系   它定义了共享变量之间的约束，如指定的那样   由原来的C1和C2组成。

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


12483
2017-10-09 00:57


起源
在这里阅读关于二进制CSP的好（和简短）： ktiml.mff.cuni.cz/~bartak/constraints/binary.html - teejay

答案:

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

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

12
2018-04-05 13:37



热门问题

不使用eval / new函数的JavaScript模板库 当涉及内部类时，Java继承如何工作 .NET Windows服务的奇怪问题 在.ipa或.app下查找App ID 快速入门XSLT参考[关闭] 如何找出Android应用程序中未使用的资源 Ruby中并发的同步方法[重复] 将std :: chrono :: system_clock :: time_point转换为struct timeval并返回 Google Drive API V3（javascript）更新文件内容 Bootstrap 3.0 - 将元素推到底部 受密码保护的.NET ClickOnce部署？ 如何用postgresql安装wordpress coq Set或Type如何成为命题 硒滚动元素进入（中心）视图 在Spring Transaction JUnit测试中自动装配Hibernate会话的正确方法 Git的Dockerfile策略 如何在FOS_PICKFOLDER中使用IFileDialog，同时仍在对话框中显示文件名 在Firefox扩展中复制Google Chrome浏览器操作弹出效果 CakePHP找到MAX 芹菜 - 完成任务的召唤功能 从使用fmemopen创建的流中读取宽字符 .NET是否为每个程序集创建一个字符串实习池？ DefaultModelBinder不绑定嵌套模型 Navigator.MediaDevices.getUserMedia（）使用了哪些相机通信标准？ 选择命名空间名称时应该知道什么？ cout Swagger Codegen CLI Java客户端 - 如何正确使用它 一个很好的哈希函数用于采访整数，字符串？ Maven 3 ciManagement配置的目的是什么？ 如何通过语言文化获取代码页？
licensed under cc by-sa 3.0 with attribution.
隐私政策 往来