《人工智能05约束满足问题(共55张PPT).pptx》由会员分享，可在线阅读，更多相关《人工智能05约束满足问题(共55张PPT).pptx（55页珍藏版）》请在taowenge.com淘文阁网|工程机械CAD图纸|机械工程制图|CAD装配图下载|SolidWorks_CaTia_CAD_UG_PROE_设计图分享下载上搜索。
1、第五章 约束满足问题培训专用Review:Last ChapterBest-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 efficien
2、t(up to tie-breaks,for forward search)Admissible heuristics can be derived from exact solution of relaxed problems培训专用Review:Last ChapterLocal 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 searchde
3、pending 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
4、 structure 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（值域）Digoa
5、l test is 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培训专用Examp
6、le:Map-Coloring变量 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-ColoringSolutions are assignments satisfying all constraints,e.g.,WA=red,NT=green,
7、Q=red,NSW=green,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/布尔C
8、SP问题(NP-complete)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（一元）约束只限制单个变
9、量的取值,e.g.,SA greenBinary（二元）约束 与两个变量有关,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
10、 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约束超图培训专用Real-world CSPsAssignment problems（分配问题）e.g.,who teaches what class who reviews which papersTimetabling problems（时间表安排问题）e.g.,which class is offered when and where?Hardware configuration（
11、硬件配置问题）Transportation 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增量形式化)从简单直白的方法开始，状态被定义为已被赋值的变量初始状态:空的赋值,后继函数:给一个未
12、赋值变量赋值使之不与当前状态冲突 fail 如果没有合法赋值 目标测试:检验当前赋值是否完全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回溯搜索变量赋值具有可交
13、换性,也就是说 WA=red then NT=green 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 examp
14、le培训专用Backtracking example培训专用Backtracking example培训专用提高回溯效率General-purpose methods can give huge gains in speed:1.哪一个变量应该被下一个赋值?2.赋值应该以什么样的顺序被尝试?3.能更早察觉到不可避免的失败吗?4.Can we take advantage of problem structure?培训专用Minimum remaining valuesMinimum remaining values 最少剩余值(MRV):选择“合法”取值最少的变量Why min rather
15、than max?被称为“最受约束变量”或“失败优先”启发式培训专用Degree heuristic（度启发式）在MRV无法抉择时启动度启发式度启发式:通过选择涉及对其它未赋值变量的约束数最大的变量培训专用提高回溯效率General-purpose methods can give huge gains in speed:1.哪一个变量应该被下一个赋值?2.赋值应该以什么样的顺序被尝试?3.能更早察觉到不可避免的失败吗?4.Can we take advantage of problem structure?培训专用最少约束值一个变量被选定,choose the least constrain
16、ing value（最少约束值）:这个选择的值是在约束图中排除邻居变量的可选值最少的 需注意的是可能需要经过一些计算来确定这个值结合以上启发式来解决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:保持记录未赋值变量的剩余合法值当任一变量没有合
17、法值时结束搜索培训专用前向检验Idea:保持记录未赋值变量的剩余合法值当任一变量没有合法值时结束搜索培训专用前向检验Idea:保持记录未赋值变量的剩余合法值当任一变量没有合法值时结束搜索培训专用前向检验Idea:保持记录未赋值变量的剩余合法值当任一变量没有合法值时结束搜索培训专用Constraint propagation 约束传播前向检验将信息从已赋值变量传播到未赋值变量，但是并不能提前检测出所有矛盾:NT and SA cannot both be blue!约束传播必须反复应用直到不在有矛盾培训专用Arc consistency 弧相容最简单的传播形式是使每条弧相容X Y 是相容的，当且
18、仅当对变量X中的任意值x 都存在相容赋值y培训专用Arc consistency 弧相容最简单的传播形式是使每条弧相容X Y 是相容的，当且仅当对变量X中的任意值x 都存在相容赋值y培训专用Arc consistency 弧相容最简单的传播形式是使每条弧相容X Y 是相容的，当且仅当对变量X中的任意值x 都存在相容赋值y如果 X 失去了一个值,X 的邻居需要再次核对培训专用Arc consistency 弧相容最简单的传播形式是使每条弧相容X Y 是相容的，当且仅当对变量X中的任意值x 都存在相容赋值y如果 X 失去了一个值,X 的邻居需要再次核对弧相容能比前向检验更早发现矛盾被运行于搜索前的
19、预处理，或者每一次赋值后培训专用弧相容算法AC-3O(n2d3)(but detecting all is NP-hard)培训专用提高回溯效率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
20、decomposition Local search for CSPs培训专用问题的结构T岛和大陆是不连通的约束图中的连通域是可辨认的培训专用问题的结构假设每个子问题有总共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培训专用树状结构的CSPsTheorem:if the constraint graph has no loops,the CSP can be so
21、lved in O(n d2)time任何一个树状结构的CSP问题可以在变量个数的线性时间内求解Compare to general CSPs,where worst-case time is O(dn)这个性质同样适用于逻辑与概率推理:一个重要的例子：语法约束与推理复杂度之间的关系培训专用Algorithm for树状结构的CSPs1.任选一个节点作为树的根节点，从跟节点到叶节点按顺序排列，每个节点的父节点都在它的前面2.令j从n到2,在弧(Parent(Xj),Xj)上应用弧相容算法，从Xj的值域中删除必要的值3.令j从1到n,赋给变量 Xj 与变量Parent(Xj)相容的值Comple
22、xity:O(n d2)培训专用近似树状结构调整:删除一个变量，修建其邻居的值域割集调整:删除一组变量（环割集）使剩下的约束图为一颗树环割集大小c 运行时间 O(dc(n-c)d2),当c很小时比直接回溯有巨大的节省寻找最小的环割集是一个NP难题，但存在有效的近似算法培训专用本章大纲CSP examples Backtracking search for CSPs Problem structure and problem decomposition Local search for CSPs培训专用CSPs的迭代算法爬山算法、模拟退火算法是处理完全状态的形式化问题（所有变量已被赋值）的典型算
23、法应用到CSPs:允许状态有未满足的约束条件操作者再次分配变量值变量选择:随机选择任意有冲突的变量选择新值的时候采用 min-conflicts（最小冲突）启发式:choose 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评价
24、:h(n)=number of attacks培训专用最小冲突的性能在n皇后问题上，给定随机的初始状态，最小冲突算法的运行时间大体上独立于问题大小，具有很高的性能(e.g.,n=10,000,000)对随机生成的CSP以上结论一般成立，除了一个狭窄的范围比培训专用Example:3-SAT problems每个约束涉及到3个变量培训专用Speedup1:模拟退火算法Idea:用一些”坏的”移动来避开局部极大值但逐步减小其频率If 新状态比现有状态好，移动到新状态Else 否则以某个小于1的概率接受该移动此概率随温度“T”降低而下降培训专用Speedup2:minmax optimization
25、培训专用Speedup2:minmax optimization培训专用SummaryCSPs 是一类特殊的问题:状态被定义为一组固定的变量值目标测试被变量取值间的约束所定义回溯=深度优先搜索的一种形式，对每个节点的单一变量赋值变量排序和取值选择启发式大大提升搜索效率前向检验能够在矛盾之前提前阻止赋值约束传播(e.g.,弧相容)做了一些附件的工作去约束取值和发现矛盾The CSP representation allows analysis of problem structure树状的 CSPs 能够在线性时间内解决迭代最小冲突算法在实践中经常是很有效的培训专用作业5.6，5.8，5.9培训
26、专用演讲完毕，谢谢观看！培训专用内容总结第五章 约束满足问题。1.哪一个变量应该被下一个赋值。1.哪一个变量应该被下一个赋值。度启发式:通过选择涉及对其它未赋值变量的约束数最大的变量。这个选择的值是在约束图中排除邻居变量的可选值最少的。Idea:保持记录未赋值变量的剩余合法值当任一变量没有合法值时结束搜索。前向检验将信息从已赋值变量传播到未赋值变量，但是并不能提前检测出所有矛盾:。约束图中的连通域是可辨认的。假设每个子问题有总共n个变量中的c个变量。一个重要的例子：语法约束与推理复杂度之间的关系。1.任选一个节点作为树的根节点，从跟节点到叶节点按顺序排列，每个节点的父节点都在它的前面。选择会造成与其它变量的冲突最小的值。5.6，5.8，5.9培训专用