资源描述：
《启发式搜索策略课件.ppt》由会员上传分享，免费在线阅读，更多相关内容在教育资源-天天文库。
1、P943.3设计要求与提示:设计要求给出搜索图,包括局部择优与全局择优,并在图中标示出搜索顺序标号,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)3.4启发式搜索策略启发信息和估价函数局部择优搜索全局择优搜索A*算法宽度优先、深度优先搜索属于盲目搜索（按规定的路线搜索）。盲目搜索效率低，耗费过多
2、的计算空间与时间。Background&Questions:e.g.-1e.g.1Astofig.,whichone,thechildrenA,BandCofS,wouldbehopefultogetgoalorgetgoalwithlittlecost?MakechoiceForeachstepsearching.2.若选择最有希望的节点加以扩展(NOT按规定的路线盲目搜索)，则搜索效率将会大为提高。3.4.1启发信息和估价函数启发信息：与具体问题求解相关的控制性知识。CanmakechoiceUsefulforsearchingsolution.e.g.-2
3、busdebitcardsforstudentsorregularpeopleBlindsearchingisstillusefulinsomecases.估价函数：Expressionoftheusefulinformation启发信息的量化表示,据此可估计OPEN表中各扩展节点的重要程度，给它们排定扩展次序。5定义评价函数/估计函数f:f（n）＝g（n）＋h（n）其中n是被评价的节点。g(n)：表示从初始节点S到节点n的路径的代价；h(n)：表示从节点n到目标节点G的路径的代价；f(n表示从初始节点S经过节点n到目标节点G的路径的代价。g(n)：costpa
4、yingalreadyforsearchingh(n)：costevaluationinfurthersearchingf(n)：costevaluationinsearchingalongtheroute.g.-3partofsearchinggraph33…n11定义一个评价函数f11isstart,33isgoalniscurrentnodeorsearchingn,nowAroutFrom11to33Whichisg?Whichish?…gnhnfn3.4.2局部择优搜索基本思想：当一个节点扩展后,在它的所有子节点中，选估价函数f(n)最优者作为下一个考
5、察的节点。e.g.illustratethebasicideabyshoppingmakethebestchoiceamongacertainarea例1：用局部择优搜索策略求解八数码问题。Understandwhatf(n),g(n)andh(n)mean估价函数定义为f(n)=g(n)+h(n)其中，g（n）=d(n)表示搜索depth,or等代价时,g（n）对局部择优搜索没有影响.g(n)issamewhensearchingamongthechildren.h(n)=w(n)表示结点n的格局与目标结点D格局相比位置不符的数码个数。So,估价函数定义为f(
6、n)=h(n)=w(n)例1局部择优搜索树-1CompareNo.cardsnotintheproperposition-h(n)=w(n)在它的所有子节点中，选估价函数f(n)最优者等代价时,g（n）对局部择优搜索没有影响.3casesfromstartnode-3childrennodesSearchingdepth=1,searchingcostI,2,3,theng=1,2,3Otherwisesearchingcost1,theng==1EXE-1局部择优搜索树EXE-2局部择优搜索树局部择优搜索随机性如果将搜索No.3格局改为搜索其具有相同估值的兄弟
7、格局，如图所示。请补充搜索树的其余部分。231847651234562318476524102局部择优搜索随机性Bestsolution局部择优搜索小结主要在单因素、单极值情况下使用；在多因素，多极值情况下，找不到最佳解。AsforNo.3anditsbrother,twotopvalues局部择优搜索亦称“瞎子爬山法”。可能找不到最佳解。Think找不到最佳解?Maybemaketheleftoneasthefirstchoice:asforfig.differentsearchingroutscasuallyReturntoComparewithglobal
8、ThinkingAlgo
