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

Question

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

Answer 1

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