最短路径算法之AStar算法(一) AStar算法的证明

本文并不试图对A Star算法进行一个入门式的讲解，因为光是那个讲解就有可能会占据很长的篇幅，而且网上已经有讲解的文章，讲的肯定比我好。所以，本文是面向已经对A Star算法有了一定了解的人。如果各位对A Star算法还不睡很了解，那么请参考我下面列出的几篇文章：

1，http://apps.hi.baidu.com/share/detail/16593767

     这篇文章详细讲解了A Star算法，是一片很好的入门文章。读者如果有兴趣还可以参看它的英文原文。

2，http://blog.csdn.net/sworder_001/archive/2006/09/27/1297501.aspx

    这篇文章有A Star算法的伪代码，和上面文章的伪代码有所不同，细心的读者一定可以看出来。本文稍后会讨论这个不同。

好了，到了这里，我假设读者已经对S Star算法有了较好的理解。

在讲解A Star算法前，先定义一下文章中使用的符号和术语。

图G代表了某个要在其上寻找最短路径的图，start为起点，end为终点。
有某条路径path，其上的某两点为M和N，则令符号Ppath(M-N)为在路径path上从点到点N的路径值。那么，Ppath(start-end)就是路径path的值。
α(N)为在图G中从start到N的最短路径值。 
β(N)为G图中从N到end的最短距离。
w(x,y)为边(x，y)的权值。
对于某条有向边(M，N)，M是N的前驱节点，N是M的后继节点。 

AStar算法是从起点开始一步步的往终点探索。他有两个链表open链表和close链表。每探索（本文称之为“扩展”）一个点N时，就获取了N的所有的后继节并且把他们放到open链表中，并且把点N放到close链表中。AStar算法每从open链表中选取一个点进行扩展，选取的原则就是每个节点的评估函数。
评估函数F(N)=G(N)+H(N)。通过评估函数，每个节点都有一个评估值。G(N)代表了在一步步扩展的过程中，从start到点N的距离，H(N)代表了从点N到end的最短距离的估计值，注意，这里说的是估计值，当然是因为最短距离无法得知，所以只能估计了。通过这个评估函数我们可以看出来，节点的评估值代表了通过该节点从起点到终点的最短路径的一个估计值。
H函数随着图的不同而不同。

AStar算法的伪代码如下：
假设对于某个节点N而言，H函数值为H(N)。
建立一个数据结构Node：
struct Node{
    int g;   //该节点的g值
    int h;   //该节点的h值
    int f;   //该节点的f值
    Node* pre;  //该节点的前驱节点
};

AStar_Search(){
    struct  Node  start_node;
    start_node.g = 0;
    start_node.h = H(start);
    start_node.f = start_node.h;
    start_node.pre = NULL;

    OPEN链表 = [start_node]; CLOSE链表 = [];

    while ( OPEN链表非空 ) {
        从OPEN链表中取得F值最小的Node,称之为x_node，对应的节点称之为为x；
        从OPEN链表中删除x_node；

        if (x是end节点){
            根据每个节点对应的node结构的pre指针，返回路径；
        }

        for (x的每一个后继节点y){
            struct  Node  y_node;
            y_node.g = x_node.g+w(x,y);
            y_node.h = H(y);
            y_node.f = y_node.g+y_node.h;
            y.pre = x_node;

            if( y不在OPEN表 and 不在CLOSE表中){
                把y_node放到OPEN表中；
            }else  if( y在OPEN表中){
                取出OPEN表中的y节点对应的Node结构，称之为y_open；

                if( y_node.f小于y_open.f) {               //程序注意点1
                    y_open.g=y_node.g;
                    y_open.h=y_node.h;
                    y_open.f =y_node.f;
                    y_open.pre = y_node.pre;
                }
            }else{              //y在CLOSE表中
                取出CLOSE表中的y节点对应的Node结构，称之为y_close；

                if(y_node.f小于y_close.f){              //程序注意点2
                    将y_close从CLOSE链表中删除
                    把y_node放到OPEN表中；
                }
            }
        }  //end  for

        将x_node放入到CLOSE表中；
    }    //end  while
}    // end  AStar_Search

设点N为图中的一个点，如果H(N)<= β(N)，那么用A Star算法找出来的路径就是最短路径。否则，只能是近似的最短路径，而并非最短路径。

个人认为，算法中有两个隐含的前提：
1. H(end)=0，也就是说，终点的H函数的估计值为0，这是显而易见的。
2. H函数不会随着算法的进行而发生变化，也就是说，对于某个节点N而言，H(N)的值是不变的。

我们来证明这个算法，就是说当H(N)<= β(N)时，算法找出来的是最短路径。

引理1：令某条路径stp是图G中的最短路径，点N是这条路上的任意一点，则Pstp(start-N)= α(N)。
证明很简单，假设从start到点N存在一条更短的路径，其路径值为P(start-N)，就是说P(start-N)< Pstp(start-N)。Pstp(start-end)= Pstp(start-N)+ Pstp(N-end)。那么用这条更短的路径替换掉路径stp中从起点start到点N的路径，得到一个新的路径，令其为stp’。那么Pstp' (start-end)= P(start-N)+ Pstp(N-end)< Pstp(start-N)+ Pstp(N-end)= Pstp(start-end)。因此，这个新的路径的值肯定更短，这与stp是最短路径矛盾，因此，Pstp(start-N)= α(N)。

引理2：令某条路径stp是最短路径，N是这条路上的任意一点，则Pstp(N-end)=β(N)
证明方式和引理1相同。

引理3：令某条路径stp是最短路径，N是这条路上的任意一点，每个节点的H函数值不变，令G(N)= Pstp(start-N)，则此时得到的F(N)为最小值，并且，如果H(N)<=β(N)，则F(N)<= Pstp (start-end)。
证明很简单，F=G+H。在H函数值不变的前提下，F函数值的大小就看就看G函数值的大小。根据引理1，Pstp(start-N)为从start到点N的最短值。因此，F(N)= Pstp(start-N)+H(N)为最小值。Pstp (start-end)= Pstp (N-S1)+ Pstp (N-end)= Pstp (N-S1)+ β(N)(根据引理2)>= Pstp (N-S1)+ H(N)=F(N)。

现在，简单的证明一下这个算法，就是说对于图中的任意一个节点node而言，令H(node)<= β(node)，则找出的路径是最短路径。以下的证明建立在前面所说的两个前提之下。

用反证法。假设该算法不正确，通过该算法找出了一条路径，设其为astar，实际的最短路径为stp。 那么令Pastar (start-end)> Pstp (start-end)。因为如果Pastar (start-end)=Pstp(start-end)，那么该算法没有错误，只不过是找到了另外一条最短路径。令Pastar (start-end)=M，Pstp (start-end)=N，M>N。
因为找出的路径是astarh并且其路径值是M，所以当扩展end节点时其F值是M并且是open链表中F值最小的节点。

令stp路径为start-S1-S2-……-Sk-end。从S1到Sk的各个节点的最小的F值依次是F1、F2、……、Fk。根据引理3，这些F值都小于M。

好的，我们现在看一下S1节点。AStar算法从start开始，扩展start节点，start后继的节点中包括S1，因此S1被放置到了open链表中。G(S1)= Pstp (start-S1)。根据引理1，这也是从start到S1的最短距离，因此G(S1)已经达到最小值，不会被再次改变。根据引理3，此时，S1节点的F值F(S1)= F1<=N<M。因此，根据AStar算法，我们可以得出下面这个结论，我们称之为结论1：
在以F1为F值扩展S1节点以前，不可能以M为F值扩展end节点。

现在我们假设节点Sm以Fm为F值进行了扩展，1<=m<=k。下面看看节点Sm+1。如果m=k，那么Sm+1就是end节点。
扩展Sm节点时，因为Sm+1节点是其后继节点，则计算Sm+1节点的F值为F(Sm+1)=G(Sm+1)+H(Sm+1)=G(Sm)+w(Sm，Sm+1)+ H(Sm+1)。根据引理3，G(Sm)= Pstp(start-Sm) ，因此，F(Sm+1)= Pstp(start-Sm)+w(Sm，Sm+1)+ H(Sm+1)。因为Sm节点以及Sm+1节点都是最短路径stp上的节点，很显然，Pstp(Sm)+w(Sm，Sm+1)= Pstp(start-Sm+1)。因此，F(Sm+1)= Pstp(start-Sm+1)+ H(Sm+1)。再次根据引理3，F(Sm+1)是Sm+1节点中所有可能的F值中的最小值，并且该值不会在以后的计算中被再次改变，因此F(Sm+1)= Fm+1。
扩展完毕Sm节点以后，Sm+1节点的位置只可能是两种：open链表或者是close链表。如果Sm+1节点在open链表中，则它的F值只可能是最小的F值Fm+1。在以Fm+1为F值扩展Sm+1节点以前，不可能以M为F值扩展end节点。如果Sm+1节点在close链表中，那么根据AStar算法，在close链表中的Sm+1节点的老的F值F'(Sm+1)<= Fm+1。因为，对于Sm+1节点而言Fm+1已经是最小的F值了，因此F'(Sm+1)= Fm+1。也就是说，该Sm+1节点已经被以Fm+1为F值进行扩展过了，并且扩展时F值为最小的F值Fm+1。
至此，我们可以得出一个结论，称之为结论2：
如果在最短路径stp上的某个节点Sm以最小的F值Fm被扩展，那么在其后继节点Sm+1被以Fm+1为F值进行扩展以前，不可能以M为F值扩展end节点。

当Sk节点以Fk为F值进行扩展时，end节点作为其后继节点，根据和上面相同的推理过程，可以得到其F值为Pstp(start-Sk)+w(Sk，end)+ H(end)= Pstp(start-end)+ H(end)= Pstp(start-end)=N<M（H(end)等于0），并且N也是end节点最小的F值。end节点不可能在close链表中否则算法早就结束了，则end节点在open链表中并且其F值只可能是N。因为N小于M，根据AStar算法end节点的F值不可能变成M，因此，找出的AStarPath路径是不存在的。至此证明完毕。

AStar算法的H函数是AStar算法的核心，H函数估计的准确与否直接关系到了算法的效率和执行时间。我们假想一下，如果H函数的估计完全准确，那么每个最短路径上的节点的F值都是最小的，那么遵循着最小的F值一直找下去很快就可以得到最短路径了。如果H函数的估计误差很大，使得某个F值很小的节点实际上到终点的路程很远，那么算法就可能在错误的了路径上探索较长时间，然后再回到正确的路径上探索。因此，如果使用了AStar算法，H函数的设计一定要谨慎，否则该算法很可能达不到你当初设想的性能要求。

结合结论1和结论2，在以M为F值扩展end节点以前，S1节点必须以F1为F值进行扩展，因而，S2节点必须以F2为F值进行扩展，因而S3节点必须以Fe为F值进行扩展，一直到Sk节点必须以Fk为F值进行扩展。