登录  
 加关注
查看详情
   显示下一条  |  关闭
温馨提示!由于新浪微博认证机制调整,您的新浪微博帐号绑定已过期,请重新绑定!立即重新绑定新浪微博》  |  关闭

银河里的星星

落在人间

 
 
 

日志

 
 

启发式搜索和A*  

2008-12-03 16:44:25|  分类: 算法与acm |  标签: |举报 |字号 订阅

  下载LOFTER 我的照片书  |

转载请注明作者:phylips@bmy

出处:http://duanple.blog.163.com/blog/static/70971767200811344425606/

引言:
现实中的很多问题都可以看成搜索问题
众里寻她千百度,蓦然回首那人却在灯火阑珊中。
就算是人类的思维,很多时刻也是在进行着搜索,搜索存储在脑中的记忆元素
就算身在社会中,我们也还是在不同的时间搜索着不同的东西。

这些只是普遍意义上的搜索,在算法中,很多问题时间上是在进行着状态空间搜索,希望找到一条从初始状态到目标状态的排序,比如排序,8数码,8皇后,最短路

而进行搜索的方法有很多,最简单的如盲目搜索,与之相反的一种就是启发式搜索,就是有效的利用当前的信息,根据一个评估函数,选择一个比较有前途的待扩展节点进行扩展。启发式搜索也叫做A算法,而A*算法则是一种特殊形式的A算法。这也算是人工智能的一个分支内容,网上的一些资料,比如lrj的那本黑书,还有一些介绍A*算法的文章,基本上都是A*算法的应用,所以很多概念,并不准确,而对于理解A*算法需要的一些关键性的证明也是没有提供的。

本文,就从人工智能的角度来介绍这个算法,主要内容参考自NJ 尼尔森的<<人工智能>>,这本书对启发式算法进行了比较深入的解释,关键是其中的一些关键性的证明都是存在的,比如证明A*算法的可接纳性,一致性条件及定理。

关键概念:

介绍一些关键的概念:
首先,对于状态空间搜索,是可以提出一个通用的搜索算法框架的,而这个框架中则主要使用了open,和closed两个表。open表,保存了当前待扩展节点,closed表则保存已扩展节点,而BFS DFS也可以纳入这个框架,比如DFS中使用的white black gray染色,实际于 open closed便是对应的。

对于启发式搜索一般具有如下评估函数f*(n) = g*(n)+h*(n),f*(n)表示从起始点经过n到达目标的估计函数
g*(n)表示从起始点到达节点n的花费函数,比如对于最短路问题,可能就是已经发现的从出发点,到当前节点的最小cost, h*(n)表示从当前状态n到目标状态的估计花费。

对于h*(n)施加如下约束,g*(n) >= g(n)  ,h*(n) <= h(n),即估计花费从是小于等于实际最小花费,则启发式搜索就是A*算法。而A*算法是可接纳的,也就是说如果存在一条到达目标的最优路径,A*算法可以保证找到这条路径。

继续对A*算法的h函数施加约束,可以保证满足一致性,或者叫单调性,约束是:对于任意的状态ni,nj
h*(ni) - h*(nj) <= c(ni,nj)
一致性可以保证,当 A*扩展节点n时,它已经找到了到达节点n的最优路径。

通用搜索框架:
1)生成一个包含初始点n0的搜索树Tr,并把n0放入open表
2)初始化一个为空的closed表
3)如果open表为空,则失败退出
4)取出open表第一个元素,将该元素放入closed表,设该元素为n
5)如果n为目标,则可以从n沿着Tr的弧进行回溯,找到解决方案,成功退出
6)扩展节点n,生成n的后继节点集M,可以利用一个parent指针,将这些节点指向n,从而维护Tr树,将这些节点放入open表
7)按任意模式或者启发式方式对open表进行排序
8)返回步骤3

该算法可以用来执行 DFS BFS 以及A*,如果是BFS则只需要把待扩展 节点放到open表的尾部即可
如果是DFS 则只需要把待扩展 节点放到open表的头部即可,均不需要执行7)
而对于启发式搜索来说,要根据启发函数进行步骤7)。


A*算法中可能需要解决的问题:
观察以上步骤,实际上在加入两个表的操作中,可能遇到一些特殊情况,就是原表中已经包含了当前要插入的这个点。这时候该如何处理。对应的在搜索树,或者搜索图中,行进的过程中又到达了原来曾经扩展或者已经在待扩展open表的那个点。

比如在8数码中,实际上每两个状态如果可达,则肯定上可以相互到达的,也就是说对于节点n的每个后继都可以吧节点n作为它的后继。这样我们就需要解决这类问题,对于这种情况只要,保证在扩展节点的后继M中不要包含它的双亲就行了,考虑到更长的循环,我们还要把双亲修改成祖先,即后继M中不要包含它的祖先。这样我们可能就需要一个数据结构用来保存节点的祖先。

但是仍有可能通过不同的路径到达相同的节点,解决这个问题的一个简单方法就是忽略它,不去检查。也就是说不去检查是否一个节点已经存在于open 或者closed中。这样实际上就允许通过不同的路径到达相同的节点,这个相同节点在Tr中重复多次出现,而这个重复的次数就是算法发现到达该点的不同路径的数目。

当然,如果对A*算法,加入一致性约束,这样就可以保证当A*首次扩展节点n时,它已经找到了到达该节点的最佳路径。

为了防止不满足一致性约束的A*算法进行重复搜索,需要对A*算法进行修改,由于可以沿着不同路径到达同一点,导致A*算法实际上产生的是一个搜索图G,而不是树,而树Tr刚好包含在这个图里。之所以要保留这个图,是因为可能后面的那个路径要比现在这个更优,在发现这样的路径时我们要更新那个搜索树。

A*算法框架:
1)生成一个包含初始点n0的搜索树Tr,并把n0放入open表
2)初始化一个为空的closed表
3)如果open表为空,则失败退出
4)取出open表第一个元素,将该元素放入closed表,设该元素为n
5)如果n为目标,则可以从n沿着Tr的弧进行回溯,找到解决方案,成功退出
6)扩展节点n,生成n的后继节点集M,在G中n的祖先不能出现在m中,在G中放置M,使他成为n的后继
7)
从M中每一个不在G中的节点放置一个指向n的指针,并且加入open中(即不在open也不在closed中的节点)
对于在open的那些,则判断是否需要更新,如果更小则更新
对于在closed中的那些,则判断是否需要更新,如果更小则更新
8)按照启发式方式对open表进行递增排序
9)返回步骤3

A*算法的一些证明和性质:

对图和h函数施加一些条件,可以保证A*算法得到最优解:
1)图中每个节点的后继是有限的
2)图中所有弧的代价都大于某个正数
3)对于图中所有节点,h函数<= 实际代价

证明略。
主要依赖于如下引理:
启发式搜索和A* - 星星 - 银河里的星星

h函数取值越小,所具有的启发性越小,而查看的节点就越多,dikstra算法实际上就是h函数=0,的特殊的A*算法。

一致性约束。。。

IDA*算法。
迭代加深的A*算法,初始设置截断值为h*(n0),以后逐步增大





 

  评论这张
 
阅读(6472)| 评论(3)

历史上的今天

评论

<#--最新日志,群博日志--> <#--推荐日志--> <#--引用记录--> <#--博主推荐--> <#--随机阅读--> <#--首页推荐--> <#--历史上的今天--> <#--被推荐日志--> <#--上一篇,下一篇--> <#-- 热度 --> <#-- 网易新闻广告 --> <#--右边模块结构--> <#--评论模块结构--> <#--引用模块结构--> <#--博主发起的投票-->
 
 
 
 
 
 
 
 
 
 
 
 
 
 

页脚

网易公司版权所有 ©1997-2018