何为“条件约束”

快速入门

条件约束技术简介(英语) / For a brief technical tutorial, click here.

“条件约束”所要处理的核心问题就是“决策选择”；即，在复杂的条件约束下，集中处理大量的决策选择问题。决策选择问题在生活中普遍存在，其中大部分决策附带条件。处理此类问题，“条件约束”技术必不可少。例如，航空公司规划飞机、空乘人员和航班班次的排班问题就是一例典型的“决策选择”问题，所要满足的条件包括经济资源（如：有多少飞机和空乘人员可供调用等）和航空管制（如：何时允许飞机起飞等）。生产企业也面临“决策选择”问题，即如何规划在不同时段使用不同机器，雇佣不同工人生产不同的产品使得企业利润最大化。快递公司也面临“决策选择”，即如何排班才能将物品按照顾客要求准时送达。

“决策选择”是困难的，因为存在着巨量的决策组合；这种巨量的组合被称为“组合爆炸”。处理“组合爆炸”问题是计算机科学要解决的基本问题之一。正是因为“组合爆炸”的存在，密码才不易破解；同时计算机科学家们也在为处理巨量组合问题费尽心思（没有“组合爆炸”的困扰，计算机早就可以在象棋比赛中胜出人类）。

如果一个决策问题具有固定数量的决策选项，每个决策选项又有有限数量的选择可能，那么我们可以利用以上特点开发专门技术解决同类问题。这些技术大多采用“约束繁殖”算法。举航空公司排班问题为例，如果将“机长M”指定到“航班F”，那么“机长M”就无法被指定到与“航班F”时间冲突的其他航班上；从这看似简单的解题逻辑出发，可以开发出功用强大的解题技术。另外，现在流行的“启发式”算法对于提高解题速度发挥了很大作用。

要深入了解“条件约束”领域的更多内容，请选择英国埃塞克斯大学硕士课程中的 “Constraint Satisfaction for Decision Making” 模块的学习；或研读曾炳均E.P.K. Tsang著《Foundations of Constraint Satisfaction》。