artificial-intelligence - 约束满足问题

Question

我正在努力通过Artificial Intelligence: A Modern Approach为了减轻我天生的愚蠢。在尝试解决一些练习时，我遇到了“谁拥有斑马”问题，Chapter 5 中的练习 5.13 .这是a topic here on SO但回答主要是针对“如果您可以自由选择可用的问题解决软件，您将如何解决这个问题？”的问题。

我接受 Prolog 是一种非常适合此类问题的编程语言，并且有一些很好的包可用，例如在 Python 中，如排名靠前的答案所示，也是独立的。唉，这些都不能帮助我以书中概述的方式“坚持下去”。

这本书似乎建议建立一组双重或全局约束，然后实现一些提到的算法以找到解决方案。我在想出一组适合对问题建模的约束时遇到了很多麻烦。我正在自己研究这个，所以我无法接触到教授或助教来帮助我克服困难——这就是我寻求你帮助的地方。

我发现与本章中的示例几乎没有相似之处。

我渴望建立双重约束，并从创建(逻辑等价的)25 个变量开始:nationality1 , nationality2 , nationality3 , ... nationality5 , pet1 , pet2 , pet3 , ... pet5 , drink1 ... drink5依此类推，其中的数字表示房屋的位置。

这对于构建一元约束很好，例如

The Norwegian lives in the first house:

nationality1 = { :norway }.

但是大多数约束是通过一个共同的门牌号组合两个这样的变量，例如。

The Swede has a dog:

nationality[n] = { :sweden } AND pet[n] = { :dog }

在哪里 n显然，范围可以从 1 到 5。或者换一种说法:

    nationality1 = { :sweden } AND pet1 = { :dog } 
XOR nationality2 = { :sweden } AND pet2 = { :dog } 
XOR nationality3 = { :sweden } AND pet3 = { :dog } 
XOR nationality4 = { :sweden } AND pet4 = { :dog } 
XOR nationality5 = { :sweden } AND pet5 = { :dog } 

......这与本书所倡导的“元组列表”有着截然不同的感觉:

( X1, X2, X3 = { val1, val2, val3 }, { val4, val5, val6 }, ... )

我本身并不是在寻找解决方案；我正在寻找如何以与本书方法兼容的方式对这个问题进行建模的开始。任何帮助表示赞赏。

Answer 1

有几个用于 CSP 求解的库:

Gecode (C++)

Choco (Java)

SICStus Prolog 中的 clp(*) 模块

还有更多。这些可用于有效的约束求解。

另一方面，如果你想实现你的通用约束求解器，一个实现 CSP 求解器的想法:构建一个约束图，其中节点是约束变量，约束连接。为每个变量存储可能的域，并建立一个通知机制。约束在其相关变量发生变化时得到通知，然后开始传播过程:通过查看相关变量的当前值来减少可能变量的域。

传播示例:

变量(带域):X - {1,2,3,4,5} - Y {1,2,3,4,5}

约束:X + Y < 4

当约束传播时，您可以推断，X 和 Y 都不能是 3、4 或 5，因为那样约束就会失败，所以新的域是:X- {1,2} Y - {1,2}

现在 X 和 Y 的两个域都更改了监听 X 和 Y 的约束，应该通知传播。

传播可能还不够。在这种情况下，使用回溯/回跳搜索:我们尝试选择单个变量的值，传播更改等。

该算法被认为非常快，但易于理解。我有一些实现可以非常有效地解决我们的特殊问题。