3-4启发式搜索策略课件

3.4启发式搜索策略启发信息和估价函数A*算法

宽度优先、深度优先搜索属于盲目搜索（按规定的路线搜索）。盲目搜索效率低，耗费过多的计算空间与时间。2.若选择最有希望的节点加以扩展(NOT按规定的路线盲目搜索)，则搜索效率将会大为提高。Background

andQuestions:e.g.1Astofig.,whichone,thechildrenA,BandCofS,wouldbehopefultogetgoalorgetgoalwithlittlecost?MakechoiceForeachstepsearching.3.4.1启发信息和估价函数启发信息：

与具体问题求解相关的控制性知识。CanmakechoiceUsefulforsearchingsolution.e.g.2busdebitcardsforstudentsorregularpeopleBlindsearchingisstillusefulinsomecases.估价函数：Expressionoftheusefulinformation

估计OPEN表中各扩展节点的重要程度，给它们排定扩展次序。4定义评价函数/估计函数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)。其中，

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：局部择优搜索随机性如果改搜索No.3格局为其具有相同估值的兄弟格局，如图所示。请补充搜索树的其余部分。2 318 47 6 51234562 318 47 6 524102局部择优搜索随机性Bestsolution局部择优搜索小结主要在单因素、单极值情况下使用；在多因素，多极值情况下，找不到最佳解。

AsforNo.3anditsbrother,twotopvalues局部择优搜索亦称“瞎子爬山法”。asforfig.找不到最佳解。

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

h(n)=w(n)表示结点n的格局与目标结点D格局相比位置不符数码个数。

全局择优搜索例1全局择优搜索树：Clickherefornextstep例2局部择优搜索树-1：例1全局择优搜索树八数码问题，如果用局部择优搜索策略求解，搜索No.2格局后，必将沿箭头所示方向搜索。请补充搜索树的其余部分。

全局择优搜索可避免局部择优搜索随机性例2局部择优搜索树-2：Compare

globalandlocale.g.1globle择优搜索树h(n)＝W(n)AvoidTrapbranchOtherwiselocal择优搜索树：f(n)＝W(n)GlobalFirstGlobalchange全局择优搜索小结think?

algorithm&OPENDS：在OPEN表中保留所有已生成而未扩展的节点，并用估价函数f(n)对它们全部进行估计，andsort!得到的不一定是实际上的最佳解。Answer:Designproperf(n).otherwisejustlikepointdirection.

从所有已生成而未扩展的节点中，选出最优的节点进行扩展。avoidtrappinginthelocalbestQuestionS：①howmanyh(w)ofthestatesare？②whichonewouldbemorehopefullyforbestsolution?③whichonecostlittlefromtheinitialtothecurrent?1 2 38 47 6 5 2 318 47 6 51 2 378 4 6 5a)b)c)w=0w=2w=2g=xg=10g=20

S0Analyze：

c)meanscostmuchtofindaROUThopefullytothegoal.1 2 38 47 6 5 2 318 47 6 51 2 378 4 6 5a)b)c)P=0P=2P=2g=xg=10g=203.4.4A*算法特点：对状态空间搜索算法中的扩展节点选择原则进行了限制。选用了一个比较特殊的估价函数。性质:采纳性单调性信息性271)基本思想：定义一个评价函数f:

f（n）＝g（n）＋h（n）

其中n是被评价的节点。

g*(n)：表示从初始节点S到节点n的最短路径的代价；

h*(n)：表示从节点n到目标节点G的最短路径的代价；

f*(n)=g*(n)+h*(n)：表示从初始节点S经过节点n到目标节点G的最短路径的代价。

f（n）、g（n）和h（n）则分别表示是对f*（n）、g*（n）和h*（n）三个函数值的的估计值。Requirement1:g（n）>0meansS0=!SgNotification:whilesearching①Generally,g（n）>=g*(n)②Trendis,g（n）descend.e.g.ifnwillbesearchedsecondtime,g（n2）<=g（n1）,otherwise,g（n2）routwillbeabandonedinsolution,keepg（n1）.最佳图搜索算法A﹡

（OptimalSearch）29

Requirement2:算法给h(n)加上如下的限制条件，h(n)≤h*(n)则算法转换为A*算法。2）A*算法性质：A*算法，具有可采纳性。可采纳（Admissibility）：一般地说，对任意一个图，当s到目标节点有路径存在时，如果搜索算法总是在找到一条从s到目标节点的最佳路径上结束，则称该搜索算法是可采纳的。30e.g.1八数码问题

31启发函数根据任意节点与目标之间的差异来定义，“不在位”将牌个数估计，取h(n)＝W(n)。thinking?W(n)≤h*(n)尽管对具体的h*(n)是多少很难确切知道，但能确定得出：至少要移动W(n)步才能达到目标。八数码问题启发函数-11 2 38 47 6 51 2 3 8 47 6 5a)W(n)=1steps=12 318 47 6 5b)W(n)=3steps=328316 47 5c)W(n)=4steps=5h*meansleaststepsTothegoal32

启发函数根据任意节点与目标之间的距离的信息P(n)来定义P(n)定义为每一个将牌与其目标位置之间距离的总和，取h(n)＝P(n)。

thinking?P(n)≤h*(n)八数码问题启发函数-21 2 38 47 6 51 2 3 8 47 6 5a)P(n)=1steps=12 318 47 6 5b)P(n)=3steps=328316 47 5c)P(n)=5steps=5c)P(8)=2P(6)=1P(2)=1P(1)=1h(n)=P(n)

搜索树331 2 38 47 6 534取不同启发函数，应用A*算法求得最佳解时所扩展和生成的节点数

35h(n)=w(n)

搜索树DevelopNo.6GenerateNo.8-1(excepts0)local择优搜索树-1：f(n)＝W(n)DevelopNo.10GenerateNo.20Blind搜索树?More!37①OPEN:＝（s），f（s）:＝g（s）+h（s）;

②LOOP：IFOPEN＝（）THENEXIT（FAIL）；

③n:＝FIRST（OPEN）；

④REMOVE（n，OPEN），ADD（n，CLOSED）；

⑤IFGOAL（n）THENEXIT（SUCCESS）；⑥EXPAND（n）→{mi}，计算f（mi

）＝g（mi）+h（mi）；

g（mi）是从s通过n到mi的代价(g（mi）=0forlocalbest)h(mi

)：表示从节点n到目标节点的代价的估计；

f（mi）是从s通过n、mi到目标节点代价的估计。⑦OPEN中的节点按f值从小到大排序(childrensortingforlocalbest)；pointerfrommiton⑧GOLOOP；g(mi)：根据已经搜索的结果，按照从初始节点s到节点mi的路径，计算这条路径的代价就可以了。h(mi)：是与问题有关的，需要根据具体的问题来定义。Algorithm38①OPEN:＝（s），f（s）:＝g（s）+h（s）;

②LOOP：IFOPEN＝（）THENEXIT（FAIL）；

③n:＝FIRST（OPEN）；

④IFGOAL（n）THENEXIT（SUCCESS）；

⑤REMOVE（n，OPEN），ADD（n，CLOSED）；

⑥EXPAND（n）→{mi}，计算f（n，mi

）＝g（n，mi）+h（mi）；

g（n，mi）是从s通过n到mi的代价h(mi

)：表示从节点n到目标节点的代价的估计；

f（n，mi）是从s