1、约束程序研究与进展约束程序研究与进展2内容提要内容提要一一.概述概述二二.研究现状研究现状3一一.概述概述l约束程序约束程序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 st
2、ates the problem,the computer solves it.Eugene C.Freuder 5标志事件标志事件l1963年，Sutherland 研制了Sketchpad系统 l1975年，Waltz 提出了相容性技术l19871987年，年，JaffarJaffar和和LassezLassez：约束逻辑程序：约束逻辑程序l19951995年，召开专题国际会议年，召开专题国际会议CPCPl19961996年，具有战略意义的研究方向年，具有战略意义的研究方向(ACM)(ACM)l19971997年，年，“Constraints Constraints”杂志创刊杂志创刊l67
3、研究对象研究对象l约束(Constraint)l约束满足问题l Constraint Satisfaction Problem,CSPl三元组(V,D,C).lV:变量集;D:变量论域;C:约束集;l求解(一个或所有解)l典型问题：图着色，N-皇后8地图着色问题地图着色问题l 变量集变量集V:WA,NT,Q,NSW,V,SA,T l 论域集论域集D:Di=red,green,bluel 约束集约束集C:相邻区域必须颜色不同相邻区域必须颜色不同 如如,WA NT,or(WA,NT)in(red,green),(red,blue),(green,red),(green,blue),(blue,re
4、d),(blue,green)9l 解解:满足所有约束的一组完全赋值满足所有约束的一组完全赋值WA=red,NT=green,Q=red,NSW=green,V=red,SA=blue,T=green地图着色问题地图着色问题10约束图约束图l二元二元 CSP:每个约束是包含两个变量每个约束是包含两个变量l约束图约束图:点表示变量，弧表示约束点表示变量，弧表示约束11研究方向研究方向l基本理论 l约束求解算法l软约束满足问题l约束程序语言(系统)l应用方面应用方面成为许多软件系统的核心技术12二二.研究现状研究现状l约束约束l求解技术求解技术l软约束满足问题软约束满足问题l资源资源13CSPs分
5、类分类l离散变量离散变量有限论域有限论域(finite domains):布尔论域，整数区间；布尔论域，整数区间；无限论域无限论域(infinite domains):整数论域，字符串论域；整数论域，字符串论域；l连续变量连续变量时间时间实数区间实数区间14约束约束l 一元约束：每个约束只包含一个变量，一元约束：每个约束只包含一个变量，例如例如,SA greenl 二元约束：约束包含两个变量二元约束：约束包含两个变量,例如例如,SA WAl 多元约束：约束包含多元约束：约束包含3个或者更多的变量个或者更多的变量,例如，字谜游戏约束例如，字谜游戏约束15字谜游戏字谜游戏l 变量变量:F T U
6、W R O X1 X2 X3l 论域：论域：:0,1,2,3,4,5,6,7,8,9l 约束约束:Alldiff(F,T,U,W,R,O)O+O=R+10 X1X1+W+W=U+10 X2X2+T+T=O+10 X3 X3=F,T 0,F 016约束的表示约束的表示l定义在变量集合定义在变量集合 X1,Xk上上 的约束的约束C(X1,X2,Xk)可看成是一个函数：可看成是一个函数：C(X1,X2,Xk):DX1 DXk 0,1l外延表示外延表示随机产生问题随机产生问题l内涵表示内涵表示表达式，函数，过程表达式，函数，过程实际问题实际问题全局约束全局约束17外延表示（外延表示（1）l C(X,Y
7、,Z)with DX=DY=DZ=1,2,3XYZC(X,Y,Z)XYZC(X,Y,Z)XYZC(X,Y,Z)11112110311011212120312011312130313012102210321012212221322012312231323013102310331013202320332013312331333118XYZC(X,Y,Z)XYZC(X,Y,Z)XYZC(X,Y,Z)111121103110112121203120113121303130121022103210122122213220123122313230131023103310132023203320133123
8、313331外延表示（外延表示（2）19XYZC(X,Y,Z)XYZC(X,Y,Z)XYZC(X,Y,Z)111121103110112121203120113121303130121022103210122122213220123122313230131023103310132023203320133123313331外延表示（外延表示（3）20X Y ZC(X,Y,Z)X Y ZC(X,Y,Z)X Y ZC(X,Y,Z)11 11211031 1011 21212031 2011 31213031 3012 10221032 1012 21222132 2012 31223132 3013
9、 10231033 1013 20232033 2013 31233133 31=X Y Z内涵表示内涵表示21全局约束（全局约束（global constraint）lAlldifferent:Alldiff(F,T,U,W,R,O)lGlobal Constraint Catalog(06.9.30)http:/www.emn.fr/xnfo/sdemasse/gccat/titlepage.htmlNicolas Beldiceanu 22求解技术求解技术l 系统搜索（回溯）系统搜索（回溯）l 相容性技术相容性技术l 约束传播搜索约束传播搜索 回顾回顾 展望展望l 启发式策略启发式策略l
10、 不完备的搜索不完备的搜索l 对称消除对称消除 Symmetry breaking 变量对称，值对称变量对称，值对称l 计算智能（粒子群、遗传算法等）计算智能（粒子群、遗传算法等）23l思想思想反复为变量选择一个与当前部分解相容的值来把部分解反复为变量选择一个与当前部分解相容的值来把部分解扩展到完全解扩展到完全解 顺序的实例化变量顺序的实例化变量如果当前部分解不满足某个约束，就回溯到最近的变量如果当前部分解不满足某个约束，就回溯到最近的变量实例化实例化l优点优点是完备的方法是完备的方法比比GT方法效率高方法效率高l缺点缺点发生发生“颠簸颠簸”现象现象 顺序回溯顺序回溯（Backtracking
11、BT）2425BT的改进的改进l Dependency-directed BacktrackingBackjumping1BJ Graph-based BackjumpingGBBConflict-directed BackjumpingCBJl Dynamic Backtracking-DBl backchecking and backmarking让让BT变得更变得更“聪明聪明”，从失败中获得经验，从失败中获得经验，回溯到更高的层次，回溯到更高的层次jump here1.Rina Dechter and Daniel Frost.Backjump-based backtracking fo
12、r constraint satisfaction problems.Artificial Intelligence,Volume 136,Issue 2,April 2002,147-188 26相容性技术相容性技术l1975年年Waltz 提出的提出的l优点优点有效的压缩了问题的搜索空间有效的压缩了问题的搜索空间 l缺点缺点是不完备的，通常不单独使用是不完备的，通常不单独使用l分类分类节点相容性节点相容性弧相容性：弧相容性：AC-3,AC-4,Directional AC，边界相容性边界相容性l AC-3 只检查可能由值的删除受到影响的约束只检查可能由值的删除受到影响的约束 27弧相容性弧
13、相容性（Arc Consistency-AC）1212121 21 21 2XYZXYZlProblem:X:1,2,Y:1,2,Z:1,2 X=Y,X Z,Y ZMartin Cooper and Thomas Schiex.Arc consistency for soft constraints.Artificial Intelligence,Volume 154,Issues 1-2,April 2004,Pages 199-227 28AC不完备不完备l 某个变量论域为空某个变量论域为空=无解无解l 所有变量论域基数为所有变量论域基数为1=解解l Problem:X:1,2,Y:1,2
14、,Z:1,2 X Y,X Z,Y Z121212XYZ29约束传播搜索约束传播搜索look back30BT+MAC31启发式策略启发式策略l变量选择启发式变量选择启发式最先失败原则（最先失败原则（First Fail Principle-FFP）选择受约束最强的变量进行实例化选择受约束最强的变量进行实例化l值选择启发式值选择启发式N皇后问题皇后问题,middle-out值选择值选择l和具体问题紧密相关和具体问题紧密相关学习学习 Counting Solutions32不完备的搜索不完备的搜索lBounded Backtrack SearchBBSlDepth-bounded Backtrack SearchDBSlIterative BroadeningIBlCredit Search CS33
