08-现实世界的应用

3.7　现实世界的应用

正如本章开头所述，约束满足问题的求解程序通常可用于日程安排。有几个人需要参加会议，那么这几个人就是变量，而值域由他们时间表中的空闲时间组成，约束则可能涉及会议需要哪些人员一起参加。

动作规划（motion planning）也可能用到约束满足问题的求解程序。不妨想象一个需要安装在管道内的机械臂，它包括了约束（管道壁）、变量（关节）和值域（关节可能做出的动作）。

求解约束满足问题在计算生物学中也有应用。可以认为化学反应需要的是分子间的约束。当然，正如常见的AI一样，它在游戏中也有应用。下面有一道习题就是编写数独求解程序，用约束满足问题求解方案可以解决很多逻辑谜题。

本章构建了一种简单的回溯式、深度优先搜索的解题框架。不过若能添加启发式信息——可以指导搜索过程的直觉（还记得A*吗？），就能够极大地提高搜索性能。有一种比回溯更新的技术叫作约束传播（constraint propagation），也是一种现实世界应用中的高效方案。要获得更多信息，请查看Stuart Russell和Peter Norvig的《人工智能：一种现代的方法（第3版）》（Artificial Intelligence: A Modern Approach）（Pearson，2010）的第6章。