1、第五章 约束满足问题,Review:Last Chapter,Best-first searchHeuristic functions estimate costs of shortest pathsGood heuristics can dramatically reduce search costGreedy best-first search expands lowest h incomplete and not always optimalA*search expands lowest g+h complete and optimal also optimally efficient(
2、up to tie-breaks,for forward search)Admissible heuristics can be derived from exact solution of relaxed problems,Review:Last Chapter,Local search algorithms the path to the goal is irrelevant;the goal state itself is the solutionkeep a single current state,try to improve itHill-climbing searchdepend
3、ing on initial state,can get stuck in local maximaSimulated annealing searchescape local maxima by allowing some“bad”moves but gradually decrease their frequencyLocal beam searchKeep track of k states rather than just oneGenetic algorithms,本章大纲,CSP examples Backtracking search for CSPs Problem struc
4、ture and problem decompositionLocal search for CSPs,Constraint satisfaction problems(CSPs),Standard search problem:state is a“black box“any old data structure that supports goal test,eval,successor任何可以由目标测试、评价函数、后继函数访问的数据结构CSP:state is defined by variables Xi with values from domain（值域）Digoal test i
5、s a set of constraints specifying allowable combinations of values for subsets of variables每个约束包括一些变量的子集，并指定这些子集的值之间允许进行的合并Simple example of a formal representation language（形式化表示方法）Allows useful general-purpose（通用的，而不是问题特定的）algorithms with more power than standard search algorithms,Example:Map-Colo
6、ring,变量 WA,NT,Q,NSW,V,SA,T值域 Di=red,green,blue约束:adjacent regions must have different colorse.g.,WA NT,or(if the language allows this),or(WA,NT)(red,green),(red,blue),(green,red),(green,blue),Example:Map-Coloring,Solutions are assignments satisfying all constraints,e.g.,WA=red,NT=green,Q=red,NSW=gre
7、en,V=red,SA=blue,T=green,Constraint graph（约束图）,Binary CSP:每个约束与2个变量有关约束图:节点是变量,边是约束,General-purpose CSP algorithms（通用CSP算法）use the graph structure to speed up search.E.g.,Tasmania is an independent subproblem!,CSP的种类,离散变量 finite domains 有限值域:n 个变量,值域大小d O(dn)完全赋值e.g.,Boolean CSPs/布尔CSP问题(NP-complete
8、)infinite domains 无限值域(integers,strings,etc.)e.g.,job scheduling,variables are start/end days for each job不能通过枚举来描述值域，只能用约束语言,e.g.,线性约束可解,非线性约束不可解连续值域的变量e.g.,哈勃望远镜观测的开始、结束时间线性规划问题linear constraints solvable in polynomial time by linear programming(LP)methods,约束的种类,Unary（一元）约束只限制单个变量的取值,e.g.,SA green
9、Binary（二元）约束 与两个变量有关,e.g.,SA WAHigher-order（高阶）约束 involve 3 or more variables,e.g.,cryptarithmetic（密码算数）column constraints偏好约束(soft constraints),e.g.,red is better than greenoften representable by a cost for each variable assignment（个体变量赋值的耗散）约束优化问题,Example:密码算数,变量:F T U W R O X1 X2 X3值域:0,1,2,3,4,5
10、,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,约束超图,Real-world CSPs,Assignment problems（分配问题）e.g.,who teaches what class who reviews which papersTimetabling problems（时间表安排问题）e.g.,which class is offered when and where?Hardware configuration（硬件配置问题）Transportation
11、 scheduling（交通调度）Factory scheduling（工厂调度）Floorplanning（平面布置）Notice that many real-world problems involve real-valued variables,列举分配,指数时间 dnBut complete can we be clever about exponential time algorithms?,形式化描述标准搜索(incremental增量形式化),从简单直白的方法开始，状态被定义为已被赋值的变量初始状态:空的赋值,后继函数:给一个未赋值变量赋值使之不与当前状态冲突 fail 如果没
12、有合法赋值 目标测试:检验当前赋值是否完全1.This is the same for all CSPs!2.Every solution appears at depth n with n variables use depth-first search3.Path is irrelevant,so can also use complete-state formulation（完全状态形式化）4.b=(n-l)d at depth l,hence n!dn leaves!,Backtracking search回溯搜索,变量赋值具有可交换性,也就是说 WA=red then NT=gree
13、n same as NT=green then WA=red 在搜索树的每个节点上只考虑单个变量的可能赋值b=d and there are dn leavesDepth-first search for CSPs with single-variable assignments is calledbacktracking search回溯搜索是处理CSP问题最基础的无信息搜索算法Can solve n-queens for n 25,回溯搜索,Backtracking example,Backtracking example,Backtracking example,Backtracking
14、 example,提高回溯效率,General-purpose methods can give huge gains in speed:1.哪一个变量应该被下一个赋值?2.赋值应该以什么样的顺序被尝试?3.能更早察觉到不可避免的失败吗?4.Can we take advantage of problem structure?,Minimum remaining values,Minimum remaining values 最少剩余值(MRV):选择“合法”取值最少的变量,Why min rather than max?被称为“最受约束变量”或“失败优先”启发式,Degree heurist
15、ic（度启发式）,在MRV无法抉择时启动度启发式度启发式:通过选择涉及对其它未赋值变量的约束数最大的变量,提高回溯效率,General-purpose methods can give huge gains in speed:1.哪一个变量应该被下一个赋值?2.赋值应该以什么样的顺序被尝试?3.能更早察觉到不可避免的失败吗?4.Can we take advantage of problem structure?,最少约束值,一个变量被选定,choose the least constraining value（最少约束值）:这个选择的值是在约束图中排除邻居变量的可选值最少的 需注意的是可能需
16、要经过一些计算来确定这个值,结合以上启发式来解决1000 queens 是可行的,提高回溯效率,General-purpose methods can give huge gains in speed:1.哪一个变量应该被下一个赋值?2.赋值应该以什么样的顺序被尝试?3.能更早察觉到不可避免的失败吗?4.Can we take advantage of problem structure?,Forward checking前向检验,Idea:保持记录未赋值变量的剩余合法值当任一变量没有合法值时结束搜索,前向检验,Idea:保持记录未赋值变量的剩余合法值当任一变量没有合法值时结束搜索,前向检验,
17、Idea:保持记录未赋值变量的剩余合法值当任一变量没有合法值时结束搜索,前向检验,Idea:保持记录未赋值变量的剩余合法值当任一变量没有合法值时结束搜索,Constraint propagation 约束传播,前向检验将信息从已赋值变量传播到未赋值变量，但是并不能提前检测出所有矛盾:,NT and SA cannot both be blue!约束传播必须反复应用直到不在有矛盾,Arc consistency 弧相容,最简单的传播形式是使每条弧相容X Y 是相容的，当且仅当对变量X中的任意值x 都存在相容赋值y,Arc consistency 弧相容,最简单的传播形式是使每条弧相容X Y 是相
18、容的，当且仅当对变量X中的任意值x 都存在相容赋值y,Arc consistency 弧相容,最简单的传播形式是使每条弧相容X Y 是相容的，当且仅当对变量X中的任意值x 都存在相容赋值y,如果 X 失去了一个值,X 的邻居需要再次核对,Arc consistency 弧相容,最简单的传播形式是使每条弧相容X Y 是相容的，当且仅当对变量X中的任意值x 都存在相容赋值y,如果 X 失去了一个值,X 的邻居需要再次核对弧相容能比前向检验更早发现矛盾被运行于搜索前的预处理，或者每一次赋值后,弧相容算法AC-3,O(n2d3)(but detecting all is NP-hard),提高回溯效率
19、,General-purpose methods can give huge gains in speed:1.哪一个变量应该被下一个赋值?2.赋值应该以什么样的顺序被尝试?3.能更早察觉到不可避免的失败吗?4.Can we take advantage of problem structure?,本章大纲,CSP examples Backtracking search for CSPs Problem structure and problem decomposition Local search for CSPs,问题的结构,T岛和大陆是不连通的约束图中的连通域是可辨认的,问题的结构,假
20、设每个子问题有总共n个变量中的c个变量最差情况下的工作量为O(n/c dc)，是n的线性函数E.g.,n=80,d=2,c=20280=4 billion years at 10 million nodes/sec4 220=0.4 seconds at 10 million nodes/sec,树状结构的CSPs,Theorem:if the constraint graph has no loops,the CSP can be solved in O(n d2)time任何一个树状结构的CSP问题可以在变量个数的线性时间内求解Compare to general CSPs,where w
21、orst-case time is O(dn)这个性质同样适用于逻辑与概率推理:一个重要的例子：语法约束与推理复杂度之间的关系,Algorithm for树状结构的CSPs,1.任选一个节点作为树的根节点，从跟节点到叶节点按顺序排列，每个节点的父节点都在它的前面,2.令j从n到2,在弧(Parent(Xj),Xj)上应用弧相容算法，从Xj的值域中删除必要的值3.令j从1到n,赋给变量 Xj 与变量Parent(Xj)相容的值Complexity:O(n d2),近似树状结构,调整:删除一个变量，修建其邻居的值域,割集调整:删除一组变量（环割集）使剩下的约束图为一颗树环割集大小c 运行时间 O(
22、dc(n-c)d2),当c很小时比直接回溯有巨大的节省寻找最小的环割集是一个NP难题，但存在有效的近似算法,本章大纲,CSP examples Backtracking search for CSPs Problem structure and problem decomposition Local search for CSPs,CSPs的迭代算法,爬山算法、模拟退火算法是处理完全状态的形式化问题（所有变量已被赋值）的典型算法应用到CSPs:允许状态有未满足的约束条件操作者再次分配变量值变量选择:随机选择任意有冲突的变量选择新值的时候采用 min-conflicts（最小冲突）启发式:cho
23、ose value that violates the fewest constraints选择会造成与其它变量的冲突最小的值i.e.,爬山算法 中 h(n)=total number of violated constraints,Example:4-Queens,状态:4 queens in 4 columns(44=256 states)行动:move queen in column目标测试:no attacks评价:h(n)=number of attacks,最小冲突的性能,在n皇后问题上，给定随机的初始状态，最小冲突算法的运行时间大体上独立于问题大小，具有很高的性能(e.g.,n=
24、10,000,000)对随机生成的CSP以上结论一般成立，除了一个狭窄的范围比,Example:3-SAT problems,每个约束涉及到3个变量,Speedup1:模拟退火算法,Idea:用一些”坏的”移动来避开局部极大值但逐步减小其频率If 新状态比现有状态好，移动到新状态Else 否则以某个小于1的概率接受该移动此概率随温度“T”降低而下降,Speedup2:minmax optimization,Speedup2:minmax optimization,Summary,CSPs 是一类特殊的问题:状态被定义为一组固定的变量值目标测试被变量取值间的约束所定义回溯=深度优先搜索的一种形式，对每个节点的单一变量赋值变量排序和取值选择启发式大大提升搜索效率前向检验能够在矛盾之前提前阻止赋值约束传播(e.g.,弧相容)做了一些附件的工作去约束取值和发现矛盾The CSP representation allows analysis of problem structure树状的 CSPs 能够在线性时间内解决迭代最小冲突算法在实践中经常是很有效的,作业,5.6，5.8，5.9,
