2 cnv xyr cnv_xyr 于 2015.06.06 00:12 提问

A*算法大牛进,高分!!

A*算法中为什么当h>=h*时,不能保证找到最优解,求大神解答。

2个回答

fcxxxer
fcxxxer   2015.06.07 14:10
已采纳

搜索算法的区别是如何重排open表,关键是如何编码状态和定义状态的值。对搜索过程中任意状态s,A*算法以g(s)+h(s)重排open表,也就是说g(s)+h(s)是排列open中状态的依据,其中g(s)是初始状态到s的消耗,h(s)是s到目标状态的估计。我重排open用的是c++的优先队列,扩展状态s得到新的状态ns,如果ns没访问过则直接将ns及其节点加入open。如果ns已经访问过(在open或close中),则更新ns的g(s)和h(s),由于无法直接在优先队列中进行更新,所以需要在外部用全局数组记录各个状态的g值,当某个状态的g值要改变时重新加入包含这个状态的节点,这样有冗余但不影响正确性,也是优先队列优化dijkstra算法的方法。关于启发函数h(s),h(s)越大则占g(s)+h(s)的比重越大,程序的速度也越快,当h(s)总小于实际到最终状态的消耗时,算法是能确定找到最优解的,否则能找到解但不一定能找到最优解(总消耗最少)。http://blog.csdn.net/b2b160/article/details/4057781

jiuqiyuliang
jiuqiyuliang   2015.06.06 08:27

假设最优路径是a->b->c,非最优路径a->c,当a被从open表中取出,他先将c,b放入open表,只需要证明b能在c之前被从open中取出(这样经过b的最优路径就不会被跳过了),这是显而易见的,因为最优路径经过b,而且hb->c。

先看A*算法的定义(这个应该是公认的):
1、估值函数:f(n)=g(n)+h(n)
g(n)是已经发生的耗费,h(n)是将要发生的耗费的估值
2、f(n)单调非减
3、h(x)≤h*(x),对于任意的节点x都成立
4、从优先队列的队头取出节点
(a)检测该节点是否为目标节点,是,则求得解,返回该节点。
(b)不是目标节点,则根据f(n)的大小展开子节点到优先队列中(还有一些细节,省了)
5、重复第4步,至队列为空

陆是这么说的:由于H*算法是可采用的(即求出的第一个可行解就是最优解),而A*算法只不过是将与H*算法的限制(即h(x)≤h*(x))用于A算法而得到的,所以A*算法也是可采用的,即A*算法保证得到最优解。

蔡、傅是这么说的:算法要是可采用的,需要满足4个充分条件,除了前面提到的3个条件,还有一个:在目标节点处,需要f(n)≡f*(n),而A*算法并没有这一限制,所以不能保证得到最优解。

f(n)是由g(n)和h(n)两部分构成,而g(n)一般是取的实际发生的耗费,这个值显然有:g(n)≥g*(n),所以通常都不必考虑它。
不过在目标节点处,是不是能保证g(x)≡g*(x)呢?如果等式恒成立,则在目标节点处必有f(n)≡f*(n),那么条件4就是多余的。反之就有f(n)〉f*(n),蔡的考虑就是对的。

写到这里,终于明白了:A*算法并不要求g(x)≡g*(x),这也是作者们的分歧所在。但我现在认为也许这一条件已经隐含在其它条件中,我再想一想,也欢迎各位继续讨论。

推荐:http://bbs.csdn.net/topics/70416815

希望可以帮助到你。

Csdn user default icon
上传中...
上传图片
插入图片