上篇文章中证明了A Star算法,下面,我们来看看该算法中需要注意的几个问题。
1,在扩展节点M时,计算了其后继节点N的F值,发现N节点已经在open链表中,并且新的F值小于老的F值,但是此时不进行F值的更新,那么修改过的算法正确吗?很简单不正确的,看下面这个图
图1
各个边的权值都已经标注在各边的旁边。H(A)=-100,H(B)=20,H(C)=30。经过start的扩展,F(A)=0,F(C)=40。因此,继续扩展点A,计算得到F(B)=140,把点B放进open链表中。然后扩展点C,计算得到的新的B的F值是40,如果此时不更新,然后扩展点B,最后得到的路径是start-A-B-end,显然是错误的。
2,在扩展节点M时,计算了其后继节点N的F值,发现N节点已经在close链表中,并且新的F值小于老的F值,但是此时不进行更新,那么修改过的算法正确吗?很简单,也是不正确的,看下面这个图:
图2
各个边的权值都已经标注在各边的旁边。H(A)=-100,H(C)=40。经过start的扩展,F(A)=0,F(C)=50。因此,继续扩展点A,计算得到F(end)=120。然后扩展点C,计算得到的新的A的F值是-70,如果此时A节点已经在close链表中,不进行更新,然后扩展点end,最后得到的路径是start-A-end,显然是错误的。
3,如果扩展完毕一个节点以后不放入close链表,会如何呢
程序可能会陷入死循环。还是看图2。扩展了A点以后如果不放入close链表中,那么A点的F值始终是最小,因此始终会扩展该点。当然后面的对点A的扩展不会有任何效果,程序陷入死循环。
4,如果end节点一进入open链表程序就结束,算法正确吗
算法是不正确的,看还是看图2。扩展了点A以后end节点就进了open链表,如果此时算法结束,那么得到的路径start-A-end是错误的。
5,如果H函数的估计值大于节点到终点的最短路径,算法一定会找出最短路径吗
当然不会了。看下面这个图:
图3
H(A)=20,H(B)=200。则扩展了start节点后,F(A)=120,F(B)=210。然后扩展点A,得到end节点,F(end)=120,然后扩展end节点,算法结束,得到的路径是start-A-end,显然是错误的。
我们现在看看前一篇文章讲过的该算法的两个隐含前提
6,如果F(end)不等于0,并且F(end)<0,算法正确吗
算法不是正确的。还是看图3,重新设计H函数,令H(A)=20,H(B)=10,H(end)=-500。扩展了start节点,然后是扩展A节点,结果获得的end节点的F值是-380,然后扩展end节点,算法结束,得到的路径是start-A-end,显然是错误的。但是,如果H(end)>0,算法还是正确的,因为end节点不会有后继节点,尽管H(end)大于0,但是当end节点处于最短路径时,它的F值F(end)肯定是最小的。但是这可能会增加算法的时间,因为这增大了end节点的F值,使得end节点被选择出来的几率降低,计算其它不必要的节点。
7,如果H函数随着算法的进行发生了变化,算法正确吗
算法不是正确的,还是看图2。现在设置开始的H值为:H(A)=-100,H(C)=40。扩展start节点,得到F(A)=0,F(C)=50。然后扩展A节点,将end节点扩展进来,F(end)=120。然后,H函数发生了变化,H(A)=20,H(C)=40。现在扩展C节点,得到F(A)=50,现在A节点在close链表中,但是原先的A节点的F值是0,根据AStar算法不会将A节点重新放进open链表中。最后得到的路径start-A-end是错误路径。
8,如果图中存在着负权环,那么程序会如何?
算法有可能会结束,但是得不到正确结果,或者算法会陷入死循环,无法正确结束。
先看看图4:
图4
令H(A)=60,H(B)=10,H(C)=15。此时,可以计算得出最短路径是start-B-end,但是显然是不正确的。
现在重新设计节点A的H函数值,令H(A)=20,则程序会循环的在B、C、A之间运行,这三个节点不停的在open和close链表中切换。
本文内容由网友自发贡献,版权归原作者所有,本站不承担相应法律责任。如您发现有涉嫌抄袭侵权的内容,请联系:hwhale#tublm.com(使用前将#替换为@)