A*算法大牛进，高分。

Question

1.如果h(n)经常都比从n移动到目标的实际代价小（或者相等），则A*保证能找到一条最短路径。h(n)越小，A*扩展的结点越多，运行就得越慢。
2.如果h(n)有时比从n移动到目标的实际代价高，则A*不能保证找到一条最短路径，但它运行得更快。
为什么？？？？？？？？？？？？？？？？？？？

Answer 1

设open中有x,y两个点，全局最优路径中有x->y，等效证明x在y点前被取出：g(x)+h(x)<=g(x)+h*(x)<=g*(y)<=g(y)<=g(y)+h(y)