最短路径算法之AStar算法(三) 《A* Pathfinding for Beginners》一文中的两个问题

现在，看看网上流传的很广的一篇文章《A* Pathfinding for Beginners》，经典的A STar算法的入门文章，也是我前面推荐的阅读文章。

个人认为，这篇入门文章的算法不能找出最短路径，只能找出较短路径。因为算法有两个问题：

1，这篇入门文章的算法的H函数采用曼哈顿距离，该距离不是节点到终点的最短距离。根据前篇文章的注意点5，算法找出来的不一定是最短路径。看下图

绿色的点代表起点，红色的点代表终点。灰色的点代表不可通过的路径。
根据文章的算法，从起点开始依次扩展最左边的列的点，左下角的点的F值是180。而左上角的点的F值200.那么，根据文章中的算法，图下半面的点的F值统一是180，直至终点都是180，而左上角的点直至算法结束都不会被扩展。
因此，根据文章中的算法选择的路径就是下半面的唯一的一条通向终点的路径。如下图所示，紫色的格代表了选择的路径。

可是实际上的最短路径是下图所示的路径：

2，将AStar算法入门文章中的算法和本文前面列出的算法进行比较，可以发现一个区别，就是当某个节点已经在close链表中时。AStar算法入门文章中的算法是当某个节点已经在close链表中时就不会被重新放到open链表再次进行扩展，但是本文前面列出的的算法是当某个节点在close链表中时可以被重新放到open链表中并且重新被扩展。根据注意点2，AStar算法入门文章中的算法是不对的。看下图

起点左方的节点(里面标有1)的F值是180，而右面的节点(里面标有2)的F值是160。因此从起点右面的节点开始扩展。根据文章中的算法，会按照下图所示的路径进行扩展，一直扩展到标有3的紫色节点，该节点的F值是180，因此它的下一个后继节点就是它上面的标有4节点，F值是200，该F值已经大于起点左边的标有1的F值是180的节点

于是开始从标有1的节点开始继续扩展。扩展到标有6的节点，如下图：

从标有6的节点开始扩展时，遇到后继节点5，但是节点5已经在close链表中了,不会进行处理。因此，按照文章中的算法找到的最短路径如下图

实际上，最短路径应该是如下图所示的:

现在来解决这两个问题。首先解决的就是H函数的问题。H函数不应该选取曼哈顿距离，应该是最短路径。我们根据坐标来看距离问题，假设起点的坐标是(X_^start，Y_^start)，终点的坐标是(X_^end，Y_^end)。每个格子的长度是1。图形中任意一点N的坐标是(X_^N，Y_^N)。令x= X_^N-X_^end，y=Y_^N-Y_^end。
如果x>y，则H(N)= y*14+(x-y)*10。如果x>y，则H(N)= x*14+(y-x)*10。

解决了第一个问题，现在看看第二个问题。其实，解决了第一个问题以后，第二个问题就捎带着解决了。

道理很简单，点N的F值是G(N)+H(N)。按照修改过的H函数计算方法，扩展点N时，它的后继节点M的F值只可能大于或者等于F(N)，而不可能小于F(N)。假设F(M)<F(N)。F(M)=G(M)+H(M)=G(N)+w(N，M)+H(M)。w(N，M)代表了从N到M的路径值或者是10或者是14。F(N)=G(N)+H(N)。也就是所，G(N)+H(N)> G(N)+w(N，M)+H(M)。两边去掉G(N)，可以得到，H(N)> w(N，M)+H(M)。那么就是说从N到M再到终点的最短距离比从N到终点的最短距离要短，这本身就是一个矛盾的结论，因为N到M再到终点的路径本身就属于从N到终点的路径！

有了这个结论，来看第二个问题。
随着第一个问题的解决，AStar算法入门文章中的算法和本文中的算法的唯一区别就在于当一个节点已经在close链表中时是否会被再次扩展。AStar算法入门文章中的算法不会再次扩展，而按照本文中的算法，如果新计算的节点的F值小于被放入close链表时的F值，那么该节点会被放进open链表中重新等待扩展。
现在我们假设某个节点C已经被放到了close链表中，并且此时的F值为M，并且在以后的某个时候重新计算节点C的F值时得到了一个更小的F值N，N<M，此时对应的路径是l。那么根据上面的结论，属于路径l的在节点C的前面的节点的F值都小于N，因此都小于M。
我们现在看看路径l。设在路径l上起点到C的节点依次为start-l_¹-l_²-…-l_^k-C，此时它们的F值（除了start和C）依次为为F_¹、F_²、…F_^k。
如果沿着这条路径进行扩展，那么从start到C的所有节点的F值都小于M。当从start开始扩展时，l_¹被放到了open链表中。此时l_¹的F值只可能是F_¹（证明很简单，和起点直接相连的节点的F值一开始就是最小值并且不会改变。因为从起点到这些节点的最短距离就是和他们到起点的直接距离，根据F=G+H。H函数不变，当G达到最小值时F就达到了最小值）。因为l1的节点的F值小于M，因此在l_¹没有被扩展时C节点是不可能以M做为F值而被扩展的。
当l_¹被扩展时，l_²作为它的后继节点计算其F值为F_²。根据AStar算法，如果l_²节点在open链表中，则它的F值肯定小于或者等于F_²，此时如果l_²没有被扩展，则C节点是不可能以M做为F值而被扩展的。如果l_²节点在close链表中，则它肯定是已经被以小于或者等于F_²的值被扩展了。因此，当l_²节点没有被以小于或者等于F_²的F值被扩展时，C节点是不可能以M做为F值而被扩展的。
我们现在假设，l_^k-1(k>=3)被以小于或者等于F_^k-1的F值F’_^k-1。F’_^k-1=G’(l_^k-1)+H(l_^k-1)，F_^k-1=G(l_^k-1)+H(l_^k-1)，因此，G’(l_^k-1)<= G(l_^k-1)。
现在来看lk。F’_^k=G’(l_^k)+H(l_^k)=G’(l_^k-1)+w(l_^k-1，l_^k)+H(l_^k)。而F_^k=G(l_^k)+H(l_^k)= G(l_^k-1)+w(l_^k-1，l_^k)+H(l_^k)。因为G’(l_^k-1)<= G(l_^k-1)，因此，F’_^k<=F_^k。根据AStar算法，如果l_^k节点在open链表中，则它的F值肯定小于或者等于F_^k，此时如果l_^k没有被扩展，则C节点是不可能以M做为F值而被扩展的。如果l_^k节点在close链表中，则它肯定是已经被以小于或者等于F_^k的值被扩展了。因此，如果l_^k-1(k>=3)以小于或者等于F_^k-1的F值被扩展，那么当l_^k节点没有被以小于或者等于F_^k的F值被扩展时，C节点是不可能以M做为F值而被扩展的。
当l_^k节点被以小于或者等于F_^k的F值被扩展时，根据和上面相同的过程可以推出C节点必须以小于或者等于N的F值被扩展后才可能以M值被扩展。但是这本身是矛盾的，因为N<M，根据AStar算法，对于某个节点而言，不可能以较大的F值去替换较小的F值。
因此，我们可以推出，对于修改过的算法，每个节点都只可能以最小的F值被扩展一次，并且以后不会被再次扩展。因此，在这个情况下，AStar入门文章的算法和本文的算法是相同的。