第三章参考资料.ppt

* 启发式策略 变量选择启发式 最先失败原则（First Fail Principle-FFP） 选择受约束最强的变量进行实例化 值选择启发式 N皇后问题, middle-out值选择 和具体问题紧密相关 学习 Counting Solutions * 不完备的搜索 Bounded Backtrack Search－BBS Depth-bounded Backtrack Search—DBS Iterative Broadening－IB Credit Search —CS * * 07/16/96 * *## * 07/16/96 * *## * 07/16/96 * *## * 07/16/96 * *## 约束程序研究与进展 张永刚 * 内容提要 一.概述 二.研究现状 * 一.概述 约束程序 Constraint Programming，简称CP 是围绕约束这一数学概念建立起来的关于程序设计和问题求解的方法论 是研究基于约束的组合优化问题的推理和计算系统 Wegner和Doyle（ACM） * Constraint programming represents one of the closest approaches computer science has yet made to the Holy Grail of programming: the user states the problem, the computer solves it. Eugene C. Freuder * 标志事件 1963年，Sutherland 研制了Sketchpad系统 1975年，Waltz 提出了相容性技术 1987年，Jaffar和Lassez：约束逻辑程序 1995年，召开专题国际会议CP 1996年，具有战略意义的研究方向(ACM) 1997年，“Constraints ”杂志创刊 …… * * 研究对象 约束(Constraint) 约束满足问题 Constraint Satisfaction Problem, CSP 三元组(V, D, C). V:变量集; D:变量论域; C: 约束集; 求解(一个或所有解) 典型问题：图着色，N-皇后 * 地图着色问题 变量集V: WA, NT, Q, NSW, V, SA, T 论域集D: Di = {red,green,blue} 约束集C: 相邻区域必须颜色不同 如, WA ≠ NT, or (WA,NT) in {(red,green),(red,blue),(green,red), (green,blue),(blue,red),(blue,green)} * 解:满足所有约束的一组完全赋值 {WA = red, NT = green,Q = red,NSW = green, V = red,SA = blue,T = green} 地图着色问题 * 约束图 二元 CSP: 每个约束是包含两个变量 约束图:点表示变量，弧表示约束 * 研究方向 基本理论 约束求解算法 软约束满足问题 约束程序语言(系统) 应用方面 成为许多软件系统的核心技术 * 二.研究现状 约束 求解技术 软约束满足问题 资源 * CSPs分类 离散变量 有限论域(finite domains): 布尔论域，整数区间； 无限论域(infinite domains): 整数论域，字符串论域； 连续变量 时间 实数区间 * 约束 一元约束：每个约束只包含一个变量， 例如, SA ≠ green 二元约束：约束包含两个变量, 例如, SA ≠ WA 多元约束：约束包含3个或者更多的变量, 例如，字谜游戏约束 * 字谜游戏 变量: F T U W R O X1 X2 X3 论域：: {0,1,2,3,4,5,6,7,8,9} 约束: Alldiff (F,T,U,W,R,O) O + O = R + 10 · X1 X1 + W + W = U + 10 · X2 X2 + T + T = O + 10 · X3 X3 = F, T ≠ 0, F ≠ 0 * 约束的表示 定义在变量集合 X1, …, Xk上 的约束C(X1,X2, …, Xk) 可看成是一个函数： C(X1,X2, …, Xk) : DX1 × ? × DXk ? {0,1} 外延表示 随机产生问题 内涵表示 表达式，函数，过程 实际问题 全局约束 * 外延表示（1） C(X,Y,Z) with DX = DY = DZ = {1, 2, 3} X Y Z C(X,Y,Z) X Y Z C(X,Y,Z) X Y Z C(X,