《人工智能05约束满足问题（PPT53页)精编版》由会员分享，可在线阅读，更多相关《人工智能05约束满足问题（PPT53页)精编版（54页珍藏版）》请在金锄头文库上搜索。
1、第五章 约束满足问题,Review: Last Chapter,Best-first searchHeuristic functions estimate costs of shortest paths Good heuristics can dramatically reduce search cost Greedy best-first search expands lowest h incomplete and not always optimalA* search expands lowest g+ h complete and optimal also optimally effic
2、ient (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 solution keep a single current state, try to improve it Hill-climbing
3、 searchdepending 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 CS
4、Ps Problem structure and problem decomposition Local 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
5、domain（值域）Digoal 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 al
6、gorithms,Example: 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-Coloring,Solutions are assignments satisfying all co
7、nstraints, e.g., WA=red, NT =green, 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 有限
8、值域: n 个变量, 值域大小d O(dn) 完全赋值e.g., Boolean CSPs/布尔CSP问题(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 tim
9、e by linear programming(LP) methods,约束的种类,Unary（一元） 约束只限制单个变量的取值,e.g., SA green Binary（二元）约束 与两个变量有关,e.g., SA WA Higher-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 eac
10、h variable assignment（个体变量赋值的耗散）约束优化问题,Example: 密码算数,变量: 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,约束超图,Real-world CSPs,Assignment problems（分配问题）e.g., who teaches what class who reviews which
11、papers Timetabling problems（时间表安排问题）e.g., which class is offered when and where? Hardware configuration（硬件配置问题） Transportation scheduling（交通调度） Factory scheduling（工厂调度） Floorplanning（平面布置） Notice that many real-world problems involve real-valued variables,列举分配,指数时间 dnBut complete can we be clever ab
12、out exponential time algorithms?,形式化描述标准搜索(incremental增量形式化),从简单直白的方法开始，状态被定义为已被赋值的变量 初始状态: 空的赋值, 后继函数: 给一个未赋值变量赋值使之不与当前状态冲突 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
13、use complete-state formulation（完全状态形式化）4. b = (n - l )d at depth l, hence n! dn leaves !,Backtracking search回溯搜索,变量赋值具有可交换性 , 也就是说 WA = red then NT = green same as NT = green then WA = red 在搜索树的每个节点上只考虑单个变量的可能赋值b = d and there are dn leaves Depth-first search for CSPs with single-variable assignment
14、s is calledbacktracking search 回溯搜索是处理CSP问题最基础的无信息搜索算法 Can solve n-queens for n 25,回溯搜索,Backtracking example,Backtracking example,Backtracking example,Backtracking example,提高回溯效率,General-purpose methods can give huge gains in speed: 1. 哪一个变量应该被下一个赋值? 2. 赋值应该以什么样的顺序被尝试? 3. 能更早察觉到不可避免的失败吗? 4. Can we t
15、ake advantage of problem structure?,Minimum remaining values,Minimum remaining values 最少剩余值(MRV):选择“合法”取值最少的变量,Why min rather than max? 被称为“最受约束变量” 或“失败优先”启发式,Degree heuristic（度启发式）,在MRV无法抉择时启动度启发式 度启发式:通过选择涉及对其它未赋值变量的约束数最大的变量,提高回溯效率,General-purpose methods can give huge gains in speed: 1. 哪一个变量应该被下
16、一个赋值? 2. 赋值应该以什么样的顺序被尝试? 3. 能更早察觉到不可避免的失败吗? 4. Can we take advantage of problem structure?,最少约束值,一个变量被选定, choose the least constraining 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: 保持记录未赋值变量的剩余合法值当任一变量没有合法值时结束搜索,前向检验,Idea: 保持记录未赋值变量的剩余合法值
