启发式搜索策略ppt课件.ppt

《启发式搜索策略ppt课件.ppt》由会员上传分享，免费在线阅读，更多相关内容在教育资源-天天文库。

1、3.4启发式搜索策略启发信息和估价函数局部择优搜索全局择优搜索A*算法宽度优先、深度优先搜索属于盲目搜索（按规定的路线搜索）。盲目搜索效率低，耗费过多的计算空间与时间。2.若选择最有希望的节点加以扩展(NOT按规定的路线盲目搜索)，则搜索效率将会大为提高。BackgroundandQuestions:e.g.1Astofig.,whichone,thechildrenA,BandCofS,wouldbehopefultogetgoalorgetgoalwithlittlecost?Makechoic

2、eForeachstepsearching.3.4.1启发信息和估价函数启发信息：与具体问题求解相关的控制性知识。CanmakechoiceUsefulforsearchingsolution.e.g.2busdebitcardsforstudentsorregularpeopleBlindsearchingisstillusefulinsomecases.估价函数：Expressionoftheusefulinformation估计OPEN表中各扩展节点的重要程度，给它们排定扩展次序。4定义评价函数

3、/估计函数f:f（n）＝g（n）＋h（n）其中n是被评价的节点。g(n)：表示从初始节点S到节点n的路径的代价；h(n)：表示从节点n到目标节点G的路径的代价；f(n表示从初始节点S经过节点n到目标节点G的路径的代价。33…n11定义一个评价函数f…gnhnfn33…xn11定义一个评价函数f…gnhnfn3.4.2局部择优搜索基本思想：当一个节点扩展后,在它的所有子节点中，选估价函数f(n)最优者作为下一个考察的节点。例1：用局部择优搜索策略求解八数码问题。估价函数定义为f(n)=g（n）+h(n)

4、。其中，g（n）=d(n)表示搜索depth,等代价时,g（n）对局部择优搜索没有影响.g(n)issamewhensearchingamongthechildren.h(n)=w(n)表示结点n的格局与目标结点D格局相比位置不符的数码个数。So,估价函数定义为f(n)=w(n)。例1局部择优搜索树-1：CompareNo.cardsnotintheposition在它的所有子节点中，选估价函数f(n)最优者等代价时,g（n）对局部择优搜索没有影响.例1局部择优搜索树-2：例1局部择优搜索树-3：局部

5、择优搜索随机性如果改搜索No.3格局为其具有相同估值的兄弟格局，如图所示。请补充搜索树的其余部分。231847651234562318476524102局部择优搜索随机性Bestsolution局部择优搜索小结主要在单因素、单极值情况下使用；在多因素，多极值情况下，找不到最佳解。AsforNo.3anditsbrother,twotopvalues局部择优搜索亦称“瞎子爬山法”。asforfig.找不到最佳解。Think找不到最佳解?Maybemaketheleftoneasthefirstchoic

6、e:differentsearchingroutscasuallyReturntoComparewithglobalAlgorithm?3.4.3全局择优搜索特点：对所有已生成而未扩展的节点，从中选出估价函数f(n)最优的节点进行扩展。例1：八数码问题如果将估计函数定义为：f(n)=g(n)+h(n)其中，nforglobalnodesgeneratedalreadyandnotdevelopedg(n)=d(n)代表结点n的扩展深度,eachstepcostsameh(n)=w(n)表示结点n的格局

7、与目标结点D格局相比位置不符数码个数。全局择优搜索例1全局择优搜索树：Clickherefornextstep例2局部择优搜索树-1：例1全局择优搜索树八数码问题，如果用局部择优搜索策略求解，搜索No.2格局后，必将沿箭头所示方向搜索。请补充搜索树的其余部分。全局择优搜索可避免局部择优搜索随机性例2局部择优搜索树-2：Compareglobalandlocale.g.1globle择优搜索树h(n)＝W(n)AvoidTrapbranchOtherwiselocal择优搜索树：f(n)＝W(n)Gl

8、obalFirstGlobalchange全局择优搜索小结think?algorithm&OPENDS：在OPEN表中保留所有已生成而未扩展的节点，并用估价函数f(n)对它们全部进行估计，andsort!得到的不一定是实际上的最佳解。Answer:Designproperf(n).otherwisejustlikepointdirection.从所有已生成而未扩展的节点中，选出最优的节点进行扩展。avoidtrappinginthelocalbestQu