约束满足问题:特殊约束-资源约束

资源约束， 有时称为atmost约束。

? 例如， 用表示分配给四项任务的人员个数， 人员数总计不超过10人的约束记为
。

–如果每个变量的赋值为{3, 4, 5, 6}， 就不能满足atmost约束。

– 通过检验当前值域中的最小值之和就能检测出矛盾。

对于大型的整数值的资源限制问题， 用整数集合来表示每个变量的值域然后通过相容性检验方法逐步削减集合， 通常是不可能的。

– 取代办法： 值域用上界和下界来表示， 并通过边界传播来管理。

例、 假设有2次航班， 271和272， 它们分别有165和385个座位。每次航班可承载的初始值域为

Flight271∈ [0, 165]， Flight272∈ [0, 385]。

设又增加一个约束， 两次航班所承载的总乘客数必须是420。

通过边界传播约束， 可以把这两个值域削减到Flight271∈ [35, 165]， Flight272∈ [255, 385]。

? 如果对于每个变量X和它取值的上下界， 每个变量Y都存在某个取值满足X和Y之间的约束， 我们称该CSP问题是边界相容的。