A算法ppt课件.ppt
- 【下载声明】
1. 本站全部试题类文档,若标题没写含答案,则无答案;标题注明含答案的文档,主观题也可能无答案。请谨慎下单,一旦售出,不予退换。
2. 本站全部PPT文档均不含视频和音频,PPT中出现的音频或视频标识(或文字)仅表示流程,实际无音频或视频文件。请谨慎下单,一旦售出,不予退换。
3. 本页资料《A算法ppt课件.ppt》由用户(三亚风情)主动上传,其收益全归该用户。163文库仅提供信息存储空间,仅对该用户上传内容的表现方式做保护处理,对上传内容本身不做任何修改或编辑。 若此文所含内容侵犯了您的版权或隐私,请立即通知163文库(点击联系客服),我们立即给予删除!
4. 请根据预览情况,自愿下载本文。本站不保证下载资源的准确性、安全性和完整性, 同时也不承担用户因使用这些下载资源对自己和他人造成任何形式的伤害或损失。
5. 本站所有资源如无特殊说明,都需要本地电脑安装OFFICE2007及以上版本和PDF阅读器,压缩文件请下载最新的WinRAR软件解压。
- 配套讲稿:
如PPT文件的首页显示word图标,表示该PPT已包含配套word讲稿。双击word图标可打开word文档。
- 特殊限制:
部分文档作品中含有的国旗、国徽等图片,仅作为作品整体效果示例展示,禁止商用。设计者仅对作品中独创性部分享有著作权。
- 关 键 词:
- 算法 ppt 课件
- 资源描述:
-
1、A*算法尚福华1A算法 n在图搜索算法中,如果能在搜索的每一步都利用估价函数f(n)=g(n)+h(n)对Open表中的节点进行排序,则该搜索算法为A算法。由于估价函数中带有问题自身的启发性信息,因此,A算法又称为启发式搜索算法。n对启发式搜索算法,又可根据搜索过程中选择扩展节点的范围,将其分为全局择优搜索算法和局部择优搜索算法。21. 全局择优搜索全局择优搜索n在全局择优搜索中,每当需要扩展节点时,总是从Open表的所有节点中选择一个估价函数值最小的节点进行扩展。其搜索过程可能描述如下:n(1)把初始节点S0放入Open表中,f(S0)=g(S0)+h(S0);n(2)如果Open表为空,则
2、问题无解,失败退出;n(3)把Open表的第一个节点取出放入Closed表,并记该节点为n;n(4)考察节点n是否为目标节点。若是,则找到了问题的解,成功退出;n(5)若节点n不可扩展,则转到第(2)步;n(6)扩展节点n,生成子节点ni(i=1,2,),计算每一个子节点的估价值f(ni) (i=1,2,),并为每一个子节点设置指向父节点的指针,然后将这些子节点放入Open表中;n(7)根据各节点的估价函数值,对Open表中的全部节点按从小到大的顺序重新进行排序;n(8)转第(2)步。3n由于上述算法的第(7)步要对Open表中的全部节点按其估价函数值从小到大重新进行排序,这样在算法第(3)步
3、取出的节点就一定是Open表的所有节点中估价函数值最小的一个节点。因此,它是一种全局择优的搜索方式。n对上述算法进一步分析还可以发现:如果取估价函数f(n)=g(n),则它将退化为代价树的广度优先搜索;如果取估价函数f(n)=d(n),则它将退化为广度优先搜索。可见,广度优先搜索和代价树的广度优先搜索是全局择优搜索的两个特例。4例例 1: 八数码难题。n设问题的初始状态S0和目标状态Sg如图5-12所示,估价函数与请用全局择优搜索解决该题。n解:解:这个问题的全局择优搜索树如图1所示。在图1中,每个节点旁边的数字是该节点的估价函数值。例如,对节点S2,其估价函数的计算为nf(S2)=d(S2)
4、+W(S2)=2+2=4n从图1还可以看出,该问题的解为nS0 S1 S2 S3 Sg5图1 八数码难题的全局择优搜索树672局部择优搜索局部择优搜索n在局部择优搜索中,每当需要扩展节点时,总是从刚生成的子节点中选择一个估价函数值最小的节点进行扩展。其搜索过程可描述如下:n(1)把初始节点S0放入Open表中,f(S0)=g(S0)+h(S0);n(2)如果Open表为空,则问题无解,失败退出;n(3)把Open表的第一个节点取出放入Closed表,并记该节点为n;n(4)考察节点n是否为目标节点。若是,则找到了问题的解,成功退出;n(5)若节点n不可扩展,则转到第(2)步;n(6)扩展节点n
5、,生成子节点ni(i=1,2,),计算每一个子节点的估价值f(ni) (i=1,2,),并按估价值从小到大的顺序依次放入Open表的首部,并为每一个子节点设置指向父节点的指针,然后转第(2)步。8n由于这一算法的第六步仅仅是把刚生成的子节点按其估价函数值从小到大放入Open表中,这样在算法第(3)步取出的节点仅是刚生成的子节点中估价函数值最小的一个节点。因此,它是一种局部择优的搜索方式。n对这一算法进一步分析也可以发现:如果取估价函数f(n)=g(n),则它将退化为代价树的深度优先搜索;如果取估价函数f(n)=d(n),则它将退化为深度优先搜索。可见,深度优先搜索和代价树的深度优先搜索是局部择
6、优搜索的两个特例。9A*算法算法n上一节讨论的启发式搜索算法,都没有对估价函数f(n)做任何限制。实际上,估价函数对搜索过程是十分重要的,如果选择不当,则有可能找不到问题的解,或者找到的不是问题的最优解。为此,需要对估价函数进行某些限制。A*算法就是对估价函数加上一些限制后得到的一种启发式搜索算法。10n假设f*(n)为从初始节点S0出发,约束经过节点n到达目标节点的最小代价值。估价函数f(n)则是f*(n)的估计值。显然,f*(n)应由以下两部分所组成:一部分是从初始节点S0到节点n的最小代价,记为g*(n);另一部分是从节点n到目标节点的最小代价,记为h*(n),当问题有多个目标节点时,应
7、选取其中代价最小的一个。因此有nf*(n)=g*(n) +h*(n)n把估价函数f(n)与 f*(n)相比,g(n)是对g*(n)的一个估计,h(n)是对h*(n)的一个估计。在这两个估计中,尽管g(n)的值容易计算,但它不一定就是从初始节点S0到节点n的真正最小代价,很有可能从初始节点S0到节点n的真正最小代价还没有找到,故有)()(g*ngn 11n有了g*(n) 和h*(n)的定义,如果我们对A算法(全局择优的启发式搜索算法)中的g(n)和h(n)分别提出如下限制:ng(n)是对g*(n)的估计,且g(n)0;nh(n)是对h*(n)的下界,即对任意节点n均有n则称得到的算法为A*算法。
8、)()(h*nhn 121A*算法的可纳性 n一般来说,对任意一个状态空间图,当从初始节点到目标节点有路径存在时,如果搜索算法能在有限步内找到一条从初始节点到目标节点的最佳路径,并在此路径上结束,则称该搜索算法是可纳的。A*算法是可采纳的。下面我们分三步来证明这一结论。13定理定理1n对有限图,如果从初始节点S0到目标节点Sg有路径存在,则算法A*一定成功结束。14定理定理1证明:n首先证明算法必定会结束。由于搜索图为有限图,如果算法能找到解,则会成功结束;如果算法找不到解,则必然会由于Open表变空而结束。因此,A*算法必然会结束。n然后证明算法一定会成功结束。由于至少存在一条由初始节点到目
9、标节点的路径,设此路径n S0= n0,n1 ,nk =Sgn算法开始时,节点n0在Open表中,而且路径中任一节点ni离开Open表后,其后继节点ni+1必然进入Open表,这样,在Open表变为空之前,目标节点必然出现在Open表中。因此,算法必定会成功结束。15引理引理1n对无限图,如果从初始节点S0到目标节点Sg有路径存在,且A*算法不终止的话,则从Open表中选出的节点必将具有任意大的f值。16引理引理1证明:证明: n设d*(n)是A*生成的从初始节点S0到节点n的最短路径长度,由于搜索图中每条边的代价都是一个正数,令这些正数中最小的一个数是e,则有n因为是最佳路径的代价,故有n又
10、因为 ,故有n如果A*算法不终止的话,从Open表中选出的节点必将具有任意大的d*(n)值,因此,也将具有任意大的f值。endng)()(*endng)()(g(n) *0)(nhendngnhngnf)()()()()(*17引理引理2n在A*算法终止前的任何时刻,Open表中总存在节点n,它是从初始节点S0到目标节点的最佳路径上的一个节点,且满足。)()(0*Sfnf18引理引理2证明:n设从初始节点S0到目标节点t的最佳路径序列为 S0= n0,n1 ,nk =Sgn算法开始时,节点S0在Open表中,当节点S0离开Open进入Closed表时,节点n1进入Open表。因此,A*没有结束
展开阅读全文