问题描述

A*算法大牛进，高分！！

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

解决方案

搜索算法的区别是如何重排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

解决方案二：

假设最优路径是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

希望可以帮助到你。