01-约束满足问题

第3章　约束满足问题

很多要用计算工具来解决的问题基本都可归类为约束满足问题（constraint-satisfaction problem，CSP）。CSP由一组变量构成，变量可能的取值范围被称为值域（domain）。要求解约束满足问题需要满足变量之间的约束。变量、值域和约束这3个核心概念很容易理解，它们的通用性决定了其对于求解约束满足问题的广泛适用性。

考虑一个示例。假设要安排Joe、Mary和Sue参加周五的会议。Sue至少得和另一个人一起参会。在此日程安排问题中，Joe、Mary和Sue这3个人可以是变量。每个变量的值域可以是他们各自的可用时间。例如，变量Mary的值域包括下午2点、下午3点和下午4点。此问题还有两个约束，其中一个是Sue必须参会，另一个是至少得有两个人参会。因此我们将为本约束满足问题的求解程序提供3个变量、3个值域和2个约束，且该求解程序无须用户精确说明做法就能解决问题。图3-1展示了这一示例。

类似Prolog和Picat这样的编程语言已经内置了解决约束满足问题的工具。其他语言中的常用技术是构建一个由回溯搜索和几种启发式信息组合而成的框架，加入启发式信息是为了提高搜索的性能。本章首先会构建一个CSP框架，将采用简单的递归回溯搜索法来求解约束满足问题，然后将使用该框架来解决几个不同的示例问题。