约束满足问题的局部搜索

5.3 约束满足问题的局部搜索

局部搜索算法（参见第4.3节）对求解许多CSP问题都是很有效的。它们使用完全状态的形式化：初始状态给每个变量都赋一个值，后继函数通常一次改变一个变量的取值。例如，在八皇后问题中，初始状态是8个皇后在8列上的一个随机布局，后继函数选择一个皇后并考虑把它移动到该列的其它位置。另一个可能性是从8个皇后开始，每列一个皇后，构成一组8行的排列（各个皇后分别在不同的行），通过交换两行上的皇后产生后继[23]。我们实际已经看到过一个求解CSP问题的局部搜索的例子：爬山法在n皇后问题上的应用（第4.3.1节）。应用WALKSAT（第7.6.2节）解决作为CSP的特殊情况的满足性问题，是另一个例子。

在为变量选择一个新值的时候，最明显的启发式是选择会造成与其它变量的冲突最小的值——最小冲突启发式。图5.8显示了该算法，图5.9图示了这个算法应用于八皇后问题的情况，它的评价在图5.5中给出。

图5.8 一个用局部搜索解决CSP问题的MIN-CONFLICTS算法。初始状态可以通过随机选择或者通过贪婪赋值过程依次为每个变量选择一个最小冲突的值。函数CONFLICTS统计一个特定值破坏约束的数量，在已知当前赋值的剩余值的情况下

图5.9 用最小冲突算法解决八皇后问题的一个两步的解。每一步选择一个皇后，在它所在列中重新分配位置。冲突的个数（在这个问题中是能攻击到的皇后的个数）在每个方格里列出来。算法将皇后移到最小冲突的方格里，最小冲突值有多个方格时则随机地选取其中之一

最小冲突对许多CSP都令人吃惊地有效，尤其是在给出了合理的初始状态的情况下。它的性能已经显示在图5.5中的最后一列。令人惊异的是，在n皇后问题上，如果你不计算皇后的初始放置，最小冲突算法的运行时间大体上独立于问题的大小。它甚至能在平均50步之内解决百万皇后问题（在进行了初始赋值之后）。这个不寻常的现象激发了20世纪90年代对于局部搜索以及容易和难的问题之间的区别的大量研究。例如，它用于安排哈勃太空望远镜的观察日程时间表，安排一周的观察日程所花费的时间从三周（！）减少到了10分钟。

局部搜索的另一个优势是当问题改变时它可以用于联机设置。这在调度问题中尤其重要。一周的航班日程表可能涉及上千次航班和上万人次的分配，但是一个机场的恶劣天气可能就会打乱原来的日程安排。我们希望以最小的改动来修改日程。这可以用从当前日程开始的局部搜索算法很容易地完成。一个使用新约束集的回溯搜索通常需要更多的时间，并且找到的解有可能要对当前日程进行很多改动。