我正在努力学习人工智能：一种现代方法，以便减轻我天生的愚蠢。在尝试解决一些练习时，我遇到了“谁拥有斑马”问题，即 第 5 章。这是这里的一个主题，但回复大多解决了这个问题“如果您可以自由选择问题解决软件，您将如何解决这个问题？”
我承认 Prolog 是解决此类问题的一种非常合适的编程语言，并且有一些可用的优秀软件包，例如 Python 中的软件包，如排名靠前的答案所示，也是独立的。唉，这些都没有帮助我以书中概述的方式“度过难关”。
这本书似乎建议建立一组双重或全局约束，然后实施提到的一些算法来找到解决方案。我在想出一组适合对问题进行建模的约束时遇到了很多麻烦。我正在自己研究这个问题，所以我无法联系教授或助教来帮助我渡过难关——这就是我请求你帮助的地方。
我认为与本章中的示例几乎没有相似之处。
我渴望建立双重约束，并首先创建（逻辑上等效的）25 个变量：nationality1、nationality2、nationality3、.. 国籍5、pet1、pet2、pet3、...pet5、< code>drink1 ... drink5 等等，其中的数字表示房子的位置。
这对于构建一元约束很好，例如
挪威人住在第一所房子：
nationality1 = { :norway }.
但大多数约束是通过一个共同的门牌号将两个这样的变量组合起来的，例如
瑞典人有一只狗：
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 }, ... )
我本身并不是在寻找解决方案；而是在寻找解决方案。我正在寻找如何以与本书方法兼容的方式对这个问题进行建模的开始。任何帮助表示赞赏。
I'm struggling my way through Artificial Intelligence: A Modern Approach in order to alleviate my natural stupidity. In trying to solve some of the exercises, I've come up against the "Who Owns the Zebra" problem, Exercise 5.13 in Chapter 5. This has been a topic here on SO but the responses mostly addressed the question "how would you solve this if you had a free choice of problem solving software available?"
I accept that Prolog is a very appropriate programming language for this kind of problem, and there are some fine packages available, e.g. in Python as shown by the top-ranked answer and also standalone. Alas, none of this is helping me "tough it out" in a way as outlined by the book.
The book appears to suggest building a set of dual or perhaps global constraints, and then implementing some of the algorithms mentioned to find a solution. I'm having a lot of trouble coming up with a set of constraints suitable for modelling the problem. I'm studying this on my own so I don't have access to a professor or TA to get me over the hump - this is where I'm asking for your help.
I see little similarity to the examples in the chapter.
I was eager to build dual constraints and started out by creating (the logical equivalent of) 25 variables: nationality1, nationality2, nationality3, ... nationality5, pet1, pet2, pet3, ... pet5, drink1 ... drink5 and so on, where the number was indicative of the house's position.
This is fine for building the unary constraints, e.g.
The Norwegian lives in the first house:
nationality1 = { :norway }.
But most of the constraints are a combination of two such variables through a common house number, e.g.
The Swede has a dog:
nationality[n] = { :sweden } AND pet[n] = { :dog }
where n can range from 1 to 5, obviously. Or stated another way:
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 }
...which has a decidedly different feel to it than the "list of tuples" advocated by the book:
( X1, X2, X3 = { val1, val2, val3 }, { val4, val5, val6 }, ... )
I'm not looking for a solution per se; I'm looking for a start on how to model this problem in a way that's compatible with the book's approach. Any help appreciated.
发布评论
评论（4）
有几个用于 CSP 求解的库：
还有更多。这些可用于有效的约束求解。
另一方面，如果您想实现通用约束求解器，则可以实现 CSP 求解器的想法：构建约束图，其中节点是约束变量并约束连接。为每个变量存储可能的域，并构建通知机制。当相关变量发生变化时，约束会收到通知，然后开始传播过程：通过查看相关变量的当前值，减少可能变量的域。
传播示例：
传播可能还不够。在这种情况下，使用回溯/回跳搜索：我们尝试选择单个变量的值，传播更改等。
该算法被认为相当快，而且很容易理解。我有一些实现可以非常有效地解决我们的特殊问题。
There are several libraries for CSP solving:
And there are many more. These can be used for efficient constraint solving.
On the other hand if you want to implement your general constraint solver, an idea to implement a CSP Solver: build a constraint graph, where the nodes are the constraint variables and constraints the connections. For every variable store the possible domain, and build a notification mechanism. The constraints are notified when its related variables change, and then start a propagation process: by looking at the current values of the related variables reduce the domains of possible variables.
Propagation example:
It is possible that propagation is not enough. In this case a backtracking/backjumping search is used: we try to select the value of a single variable, propagate the changes, etc.
This algorithm is considered quite fast while it is easy to understand. I have some implementation that solves our special case of problems very efficiently.
感谢大家提供一些有用的信息！
我真正需要的提示是在交通堵塞时出现的。不是将国籍、宠物等分配给房屋（名为
country1、country2、pet1、pet2的变量），我需要做的就是为域中的元素分配房屋！示例：这使我能够为我的约束找到简单的公式，如下所示：
我还没有完成（仅在这部分时间推杆），但一旦我解决了，我将发布一个完整的解决方案。
更新：大约两周后，我在 Clojure 中提出了一个可行的解决方案：
这是 292 行，但其中有很多调试/诊断代码。总而言之，我很高兴能够在 Clojure 中管理出一个相当简短的解决方案。函数式编程带来了一些挑战，但我设法保持了相当一致的函数式风格。
欢迎批评！
对于任何关心的人，解决方案如下：
Thanks to everyone for some helpful information!
The hint I really needed came to me in a traffic jam. Rather than assigning nationalities, pets etc. to houses (variables named
country1,country2,pet1,pet2), what I needed to do was assign houses to the elements of the domain! Example:This allowed me to find simple formulations for my constraints, like this:
I'm not done yet (puttering at this only part time) but I will post a complete solution once I work it out.
Update: About 2 weeks later, I've come up with a working solution in Clojure:
This is 292 lines, but there's a lot of debug/diagnostic coding in there. In all, I'm pretty happy to have managed a reasonably short solution in Clojure. Functional programming made for a bit of a challenge but I managed to maintain a pretty consistent functional style.
Criticism welcome though!
For anyone who cares, here's the solution:
警告：我不确定这就是您要搜索的内容，因为我还没有阅读人工智能：一种现代方法，但我认为接下来的内容仍然很有趣。
Edi Weitz 在这个谜语上有一个有趣的页面，其中有解释来源在 Common Lisp 以及 C++ 和 Common Lisp 的其他来源中，没有详细的注释。我发现 Klaus Betzler 的 C++ 源代码特别有趣（为了更加清晰而重新格式化了一点）：
Warning: I'm not sure this is what are you searching for, because I haven't read Artificial Intelligence: A Modern Approach, but I think what follow is interesting nonetheless.
Edi Weitz has an interesting page on this riddle, with explained source in Common Lisp and other sources in C++ and Common Lisp without detailed comments. I found the C++ source by Klaus Betzler particularly interesting (reformatted a little for enhanced clarity):
以下是如何对二元约束满足问题进行建模
所有谜题中给出的线索添加约束。没有任何限制，任何组合都是可能的。
因此，您想要做的是使用消除，这实际上与您在示例中使用的方法相反。具体方法如下：
您需要一个矩阵，其中每个国籍占一行，每个布尔属性占一列（“住在红房子”、“住在蓝房子” ", "有一只狗", ...)
该矩阵中的每个单元格应该
最初设置为 TRUE。
然后你遍历列表
并尝试将它们应用到
你的矩阵。例如，线索
“英国人生活在红色之中
house.” 设置了每个单元格
“红房子”列为 FALSE，除非
对于英语方面的人
国籍线。
跳过涉及属性的线索
尚未推断出。例如：“温斯顿吸烟者拥有蜗牛。” -- 好吧，如果尚未确定谁抽烟温斯顿或谁拥有蜗牛，那么现在跳过此约束。
顺便说一句，这也是解决数独谜题等问题的方法。
Here's how you model a binary constraints satisfaction problem
All the clues given in the riddle add constraints. With no constraints any combination is possible.
So what you want to do is to use elimination, which is actually the opposite approach of what you used in your examples. Here's how:
You need a matrix with one row for each nationality, and one column for each boolean attribute ("lives in a red house", "lives in a blue house", "has a dog", ...)
Each cell in this matrix should
initially be set to TRUE.
Then you iterate through the list of
constraints and try to apply them to
your matrix. For example, the clue
"The Englishman lives in the red
house." sets each of the cells in the
"red house" column to FALSE except
for the one on the English
nationality line.
Skip clues that refer to attributes
that are not yet inferred. For example: "The Winston smoker owns snails." -- well, if it is not yet determined who smokes Winston or who owns snails then skip this constraint for now.
This is also, by the way, how you solve sudoku puzzles and the like.