启发式搜索策略课件.ppt

:设计要求给出搜索图,包括局部择优与全局择优,并在图中标示出搜索顺序标号,f(n),g(n),h(n)取值设计相应算法实现所需要的数据结构、函数(在数据结构中已有的标准算法中选择)给出局部择优与全局择优的流程图2中的设计应对应局部择优与全局择优的流程图提示启发式函数为W左边B的个数,h(n)=m×W左边B的个数,m=1,2,3…,m为h(n)在本f(n)中的权重耗散值为代价数值,即g(n)*算法宽度优先、深度优先搜索属于盲目搜索(按规定的路线搜索)。盲目搜索效率低,耗费过多的计算空间与时间。Background&Questions:.-.,whichone,thechildrenA,BandCofS,etgoalwithlittlecost?(NOT按规定的路线盲目搜索),则搜索效率将会大为提高。: 与具体问题求解相关的控制性知识。.-:Expressionoftheusefulinformation 启发信息的量化表示,据此可估计OPEN表中各扩展节点的重要程度,给它们排定扩展次序。*定义评价函数/估计函数f:f(n)=g(n)+h(n)其中n是被评价的节点。g(n):表示从初始节点S到节点n的路径的代价;h(n):表示从节点n到目标节点G的路径的代价;f(n表示从初始节点S经过节点n到目标节点G的路径的代价。g(n):costpayingalreadyforsearchingh(n):costevaluationinfurthersearchingf(n):.-3partofsearchinggraph33…n11定义一个评价函数f11isstart,33isgoalniscurrentnodeorsearchingn,nowAroutFrom11to33Whichisg?Whichish?…: 当一个节点扩展后,在它的所有子节点中,选估价函数f(n)最优者作为下一个考察的节点。:用局部择优搜索策略求解八数码问题。Understandwhatf(n),g(n)andh(n)mean估价函数定义为f(n)=g(n)+h(n)其中,g(n)=d(n)表示搜索depth,or等代价时,g(n)(n)issamewhensearchingamongthechildren. h(n)=w(n)表示结点n的格局与目标结点D格局相比位置不符的数码个数。So,估价函数定义为f(n)=h(n)=w(n)例1局部择优搜索树--h(n)=w(n)在它的所有子节点中,选估价函数f(n)最优者等代价时,g(n)-3childrennodesSearchingdepth=1,searchingcostI,2,3,theng=1,2,3Otherwisesearchingcost1,theng==1EXE-1局部择优搜索树