A* 算法证明

此文章目标人群为还未理解A*算法的或想更进一步了解它的人士。

给定有向图的两个结点求他们之间长度最短的路径，可以用到A*算法，算法在下面列出。

对图中某一结点N以及起始结点src、终止结点dst：
整个算法在执行过程中，会从src结点开始对图中的结点进行遍历（可能某些并不会被遍历到），算法在遍历到某个结点时，会记录下src到该结点经过的路径，该路径的长度就记为g(N)。在算法初始化时，很自然的，src结点的g值为0，其它的结点g值为∞，表示还未被遍历到。另外，某个结点可能被遍历多次，例如：
           A 

      ↗        ↘


src                D → ….
      ↘      ↗

          B    


算法（可能）通过src->A->D这条路径遍历D之后，又折回去访问B，接着再访问D。
要谨记，结点的g值是动态生成的——在第一次遍历到它的时候生成（并且可能在以后遍历的时候更新，这是后话），不要被它吓到，如果你愿意，你可以就当它是从起始点到这一点的某条路径的长度。

h(N)表示结点N到目标点dst的“预估”长度。算法开始前，每个结点的h值都是预先确定好的。（怎么确定暂且不论）A*算法的一个思想是：路径是慢慢发现的，你发现了中途某个结点后，并不知道它离你的目标点准确有多远，只能知道个大概。不要急，这个东西在后面会慢慢解释。

g(N)和h(N)的和记为f(N)。f(n)表示了算法的遍历趋势，请铭记于心，g(N)代表这个节点离起始点的（本次遍历时经过）距离，h(N)代表这个节点离终点的（预估）距离。




有了上述概念，我们先来看看算法的形式化的步骤：
1. 建立两个容器，分别名为open和closed；
2. 将src结点添加到open中，置src结点的g值为0，置src结点的parent为null；
3. 只要open容器非空，执行以下步骤：
记open容器中f值最大的结点为cur，将cur移入closed中并将其从open中删除
如果cur就是dst结点，那么算法结束，从cur开始追朔parent生成的路径就是最短的路径；接下来，对cur结点的每一个相邻结点n：
如果n在close中
略过它，遍历下一个相邻结点
如果n在open中
如果cur的g值加上cur到n这条边的距离小于已存在的n的g值，那么更新已存在的n的g值为前者，更新其parent为cur；否则什么也不做。
否则
将它添加到open中去，其g值设为cur的g值加上cur到n这条边的距离，其parent设为cur

在证明算法前，我们必须对h函数的选择条件加以限制。
h*(N)表示结点N到dst的实际距离

根据h函数选取条件h(N)<=h*(N)：
d(i,j) = h*(i)-h*(j)
h*(i) > h(i)
h*(j) > h(j)
因此：
d(i,j) < h(i) - h(j)

记最短路径（path）上的点为(v0, v1, v2, ..., vk, ..., vt)，其中k=0...t，v0为起始点，vt位目标点。


结论0：
i通过i->...->k->...->j这条最短路径p到达j，k是这条路径上的一个中间点，那么i->...k也是i到k的最短路径。
证明：
如果i->...k不是i到k的最短路径，而i->k的最短路径记为p1，那么p1+(k->...->j)才是i到j的最短路径，与p是最短路径相悖。

结论1：
对于最短路径上的结点N，当它前面的结点进入close时，它的g值就是它距起始点的最短距离，因为当N-1进入close时就会对N的值进行指定或更新，而这个值就是最小的。

结论2：
对于最短路径上一点vj前面的所有点，但凡vj进入open，这些点要么都已经进入closed，要么至少有一个就在open中，下面是证明：
因为v0是起始点，因此v0一定会最先进入close，并展开v1到open，此时的g(v1)为起始点到v1的最短路径；
此后，设N=1，2...j-1，对于在open中的vj和它前面的最短路径上的点
因为 h(N)-h(j)<d(N,j) // h函数选取条件
g(j)-g(N)>d(N,j) // 因为此时g(N)是起始点到N的最短路径长度（见结论0）
// g(j)是起始点到j的当前路径长度
// 但是此时(g(N)对应的路径)+(N,j)才是最短的路径
// 因此g(j)>g(N)+d(N,j)
所以 (g(j)-g(N))-(h(N)-h(j))>0
即 f(j)-f(N)>0
即 f(N)<f(j)
可见f(v1)<f(vj)，因此如果v1、vj同时在open中（vj可能通过其它路径被访问过），那么v1一定会先于vj进入close，并展开v2到open（如果它不在）或更新它的g(v1)，此时的g(v1)为起始点到v1的最短路径
可见f(v2)<f(vj)，因此如果v2、vj同时在open中（vj可能通过其它路径被访问过），那么v2一定会先于vj进入close，并展开v3到open（如果它不在）或更新它的g(v2)，此时的g(v1)为起始点到v1的最短路径
...
可见f(vj-1)<f(vj)，因此如果vj-1、vj同时在open中，那么vj-1一定会先于vj进入close，并展开vj到open（如果它不在）或更新它的g(vj)，此时的g(vj)为起始点到vj的最短路径


换句话说，结论2表明：最短路径上的点会按先后顺序进入close。


注意，结论3只是说明最短路径上的点会按先后顺序进入close，并未说明在这些点会按先后顺序进入open，也并未说明它们之间是否穿插着其它点进入close。
例如：
   10   B   20
    ↗      ↘
A             D
    ↘  C  ↗
    14       6
   
   
起点为A，终点为D，现用A*算法求最短路径

为了求出最短路径，令
h(A)=10（小于A到D实际最短距离）
h(B)=5（小于B到D实际最短距离）
h(C)=4（小于C到D最短距离）
h(D)=0


起始时：
open = {A（g=0 h=10）}
close = {}

1. open中A最小，加入A到close中，对A的后代B和C，把他们都加入到open中，于是
open = {B（g=10 h=5）, C（g=14 h=4）}
close = {A}

2. open中B最小，加入B到close中，对于B的后代D，把它加入到open中，于是
open = {C（g=14 h=4）, D（g=30 h=0）}
close = {A, B}

3. open中C最小，加入C到close中，对于B的后代D，它已经存在于open中，但是因为c->d的g值更小，于是更新D的g值为C的g值加C到D的边，于是
open = {D(g=20 h=0)}
close = {A B C}

4. 从open中取出D，算法结束

可以看到，虽然终点D在步骤2进入了open，但由于f值比它小的C一直存在——直到C进入close，它才得以进入close。
另外，就算终点提前进入了open，提前得到了g值，那条最短路径出open时也会把g值更新为最短的。