第三章参考课件

1、约束程序研究与进展2内容提要一.概述二.研究现状3一.概述约束程序Constraint Programming，简称CP是围绕约束这一数学概念建立起来的关于程序设计和问题求解的方法论是研究基于约束的组合优化问题的推理和计算系统 Wegner和Doyle（ACM）4 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 comput

2、er solves it.Eugene C. Freuder 5标志事件1963年，Sutherland 研制了Sketchpad系统 1975年，Waltz 提出了相容性技术1987年，Jaffar和Lassez：约束逻辑程序1995年，召开专题国际会议CP1996年，具有战略意义的研究方向(ACM)1997年，“Constraints ”杂志创刊67研究对象约束(Constraint)约束满足问题 Constraint Satisfaction Problem, CSP三元组(V, D, C). V:变量集; D:变量论域; C: 约束集;求解(一个或所有解)典型问题：图着色，N-皇后8地

3、图着色问题变量集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)9解:满足所有约束的一组完全赋值WA = red, NT = green,Q = red,NSW = green,V = red,SA = blue,T = green地图着色问题10约束图二元 CSP: 每个约束是包含两个变量约束图:点表示变量，弧表

4、示约束11研究方向基本理论 约束求解算法软约束满足问题约束程序语言(系统)应用方面成为许多软件系统的核心技术12二.研究现状约束求解技术软约束满足问题资源13CSPs分类离散变量有限论域(finite domains):布尔论域，整数区间；无限论域(infinite domains):整数论域，字符串论域；连续变量时间实数区间14约束一元约束：每个约束只包含一个变量， 例如, SA green二元约束：约束包含两个变量,例如, SA WA多元约束：约束包含3个或者更多的变量,例如，字谜游戏约束15字谜游戏变量: F T U W R O X1 X2 X3论域：: 0,1,2,3,4,5,6,7,

5、8,9约束: Alldiff (F,T,U,W,R,O)O + O = R + 10 X1X1 + W + W = U + 10 X2X2 + T + T = O + 10 X3X3 = F, T 0, F 016约束的表示定义在变量集合 X1, , Xk上 的约束C(X1,X2, , Xk) 可看成是一个函数： C(X1,X2, , Xk) : DX1 DXk 0,1外延表示随机产生问题内涵表示表达式，函数，过程实际问题全局约束17外延表示（1）C(X,Y,Z) with DX = DY = DZ = 1, 2, 3XYZC(X,Y,Z)XYZC(X,Y,Z)XYZC(X,Y,Z)11112

6、110311011212120312011312130313012102210321012212221322012312231323013102310331013202320332013312331333118XYZC(X,Y,Z)XYZC(X,Y,Z)XYZC(X,Y,Z)111121103110112121203120113121303130121022103210122122213220123122313230131023103310132023203320133123313331外延表示（2）19XYZC(X,Y,Z)XYZC(X,Y,Z)XYZC(X,Y,Z)111121103110

7、112121203120113121303130121022103210122122213220123122313230131023103310132023203320133123313331外延表示（3）20XYZC(X,Y,Z)XYZC(X,Y,Z)XYZC(X,Y,Z)111121103110112121203120113121303130121022103210122122213220123122313230131023103310132023203320133123313331=X Y Z内涵表示21全局约束（global constraint）Alldifferent: : All

8、diff (F,T,U,W,R,O)Global Constraint Catalog(06.9.30)http:/www.emn.fr/xnfo/sdemasse/gccat/titlepage.htmlNicolas Beldiceanu 22求解技术系统搜索（回溯）相容性技术约束传播搜索回顾展望启发式策略不完备的搜索对称消除 Symmetry breaking变量对称，值对称计算智能（粒子群、遗传算法等）23思想反复为变量选择一个与当前部分解相容的值来把部分解扩展到完全解 顺序的实例化变量如果当前部分解不满足某个约束，就回溯到最近的变量实例化优点是完备的方法比GT方法效率高缺点发生“颠簸

9、”现象 顺序回溯（BacktrackingBT）2425BT的改进Dependency-directed BacktrackingBackjumping1BJ Graph-based BackjumpingGBBConflict-directed BackjumpingCBJDynamic Backtracking-DBbackchecking and backmarking让BT变得更“聪明”，从失败中获得经验 ，回溯到更高的层次jump here1.Rina Dechter and Daniel Frost.Backjump-based backtracking for constrain

10、t satisfaction problems. Artificial Intelligence, Volume 136, Issue 2, April 2002, ,147-188 26相容性技术1975年Waltz 提出的优点有效的压缩了问题的搜索空间 缺点是不完备的，通常不单独使用分类节点相容性弧相容性： AC-3, AC-4, Directional AC，边界相容性AC-3只检查可能由值的删除受到影响的约束 27弧相容性（Arc Consistency-AC ）1212121 21 21 2XYZXYZProblem:X:1,2, Y:1,2, Z:1,2 X = Y, X Z, Y

11、 ZMartin Cooper and Thomas Schiex.Arc consistency for soft constraints.Artificial Intelligence, Volume 154, Issues 1-2, April 2004, Pages 199-227 28AC不完备某个变量论域为空 =无解所有变量论域基数为1 = 解Problem:X:1,2, Y:1,2, Z:1,2 X Y, X Z, Y Z121212XYZ29约束传播搜索look back30BT+MAC31启发式策略变量选择启发式最先失败原则（First Fail Principle-FFP） 选择受约束