湖南大学人工智能课件3-2.pptx

湖南大学人工智能课件3-2.pptx

《湖南大学人工智能课件3-2.pptx》由会员分享，可在线阅读，更多相关《湖南大学人工智能课件3-2.pptx（27页珍藏版）》请在冰点文库上搜索。

第三章PartII有信息的搜索策略,内容提要,最佳优先搜索贪婪最佳优先搜索A*搜索启发式函数松弛问题,回顾：

树搜索,一种搜索策略实际上就是根据树结点扩张的顺序来决定的,最佳优先搜索,基本思路：

通过对每一个结点设置一个评价函数f（n）,找到一个代价最低的未扩散的结点实现：

根据结点的评价函数值从低到高在队列中对结点进行排序大多数评价函数由启发函数h构成h（n）:

结点到目标结点的最小代价路径的代价估计值,最佳优先搜索,最佳优先搜索vs.一致代价搜索？

代价函数的定义不同算法实例贪婪最佳优先搜索A*树,Romania问题,贪婪最佳优先搜索,评价函数f（n）=h（n）从结点n到目标结点的代价估测值罗马尼亚问题：

贪婪最佳优先搜索首先扩展与目标结点估测距离最近的结点罗马尼亚问题中使用直线距离为估测距离,贪婪最佳优先搜索,贪婪最佳优先搜索,完备性？

最优性？

时间复杂度：

O（bm）空间复杂度:

O（bm）,A*搜索,评价函数f（n）=g（n）+h（n）g（n）=到达结点n已经花费的代价h（n）=结点n到目标节点的评估代价f（n）=通过结点n到达目标结点的总评估代价,A*搜索,A*搜索,可采纳的启发函数,启发函数h（n）是可采纳的条件：

如果对于每个结点n,h（n）h*（n），其中h*（n）是到达目标结点的真实代价可采纳启发函数绝不会高估到达目标结点的代价，因此它是最优的,A*算法的最优化证明,定理：

如果启发函数h（n）是可采纳的，那么A*使用树搜索是最优的证明：

假定存在一个局部最优目标G2和一个全局最优目标G,设n是一个未扩散的结点且n在到达G的最短路径上，n,G2都位于算法的fringe队列之中如下图所示,A*算法的最优化证明,一致性启发,一个启发函数是一致的条件：

对于任意一个结点n，以及n的行为a产生的后继结点n,满足如下公式：

h（n）c（n,a,n）+h（n）如果h（n）是一致的，我们得到,A*算法的最优化证明,定理：

如果h（n）是一致的，A*使用图搜索是最优的证明：

A*根据f值从小到大扩展结点;A*选择扩散结点n时，就已经找到了达到结点n的最优路径,A*算法的属性,Environment:

Patient,hospital,staffActuators:

Screendisplay（questions,tests,diagnoses,treatments,referrals）Sensors:

Keyboard（entryofsymptoms,findings,patientsanswers）,完备性每步的代价都大于某个常数e，并且分支数b是有限的最优性时间复杂度O（b）空间复杂度O（b）,启发式函数,19,例子：

八数码问题平均解的深度？

22平均分支因数？

3,启发式函数,20,例子：

八数码问题h1（n）:

不在位的棋子数h2（n）:

所有棋子到其目标位置的距离和h1（n）=8,h2（n）:

=3+1+2+2+2+3+3+2=18,启发式搜索性能分析,21,有效分支因子：

对于某一问题，如果A*算法生成的总结点数为N,解的深度为d,那么b*就是深度为d的标准搜索树为了能够包括N+1个结点所必需的分支因子N+1=1+b*+（b*）2+（b*）d有效分支因子越小，算法性能越好,启发式搜索性能分析,22,优势,23,对于所有的结点n,h1（n）=h2（n）（两个函数都是可采纳的），我们说h2（n）比h1（n）有优势。

典型的搜索代价（平均结点扩展数）：

d=12IDS=3,644,035nodesA*（h1）=227nodesA*（h2）=73nodesd=24IDS=toomanynodesA*（h1）=39,135nodesA*（h2）=1,641nodes,松弛问题,减少了行动限制的问题称为松弛问题。

松弛问题增加了状态空间的边原有问题的任一最优解同样也是松弛问题的最优解，但松弛问题可能存在更好的解。

松弛问题,八数码问题行动描述棋子可以从方格A移动到方格B如果A与B水平或者垂直相邻并且B是空的三个松弛问题：

去掉条件B的空的：

h2将给出最短解的确切步数去掉条件AB相邻上述两者都去掉：

h1将给出最短解的确切步数,总结,最佳优先搜索贪婪最佳优先搜索A*搜索启发式函数松弛问题,Qa？