第108页 约束满足问题

前言：为一本翻译的书打分，总会考虑两方面：第一方面是原版是否出色，第二个方面则是译者翻译质量如何。翻译图书，一直以来就是个“费力不讨好”的活，尤其是翻译经典书籍。有的人做得很好，比如阮一峰（翻译的书有《黑客与画家》和《Joel谈软件》，都是由奇葩出版社 - 人民邮电出版社 - 出版的），有的人做的则比较差，比如......。我相信那些译者们已经很努力地去做好了，只不过能力不济，或者还不够下功夫 - 更多时候，我认为后者的可能性更大点。

CSP（Constraint Satisfaction Problems）其实算是一大类问题，构成这类问题的主要成分有：待求解的变量，变量的值域，对变量的值域，问题的状态。求解CSP问题则是要找到问题中所有变量的一个或者全部完全赋值。
研究CSP的目的在于找到一个通用的算法结构来求解，从更高的层面来考虑问题，然后对它们进行总结。算法的详细过程见111页的图5.3。

约束满足问题的局部搜索的能力让我非常惊讶。看起来这种迭代的方法（尤其是通常还带有难以揣摩的初始值）似乎有点小道理，但是经常比较慢，而且还不一定能够找到完全解。然而，就像书中的例子显示的那样（见112页的图5.5），局部搜索的效率几乎是最原始的回溯方法的1000倍！
最小冲突对许多CSP都令人吃惊的有效，尤其是在给出了合理的初始状态的情况下。

同样的情况也发生在EM（Expectation Maximum）算法身上，不过EM算法可以保证迭代过程是收敛的。

我们的先验知识的确可以是欺骗性的，所以“是骡子是马，拉出来遛遛”，做好实验才是根本啊！