1. 首页
  2. IT资讯

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值更新为最短的。

谢谢观看2 记得点赞 · 加油学习 0 · 有问题私信我 564

原文始发于:

主题测试文章,只做测试使用。发布者:夏枳★,转转请注明出处:http://www.cxybcw.com/109175.html

联系我们

13687733322

在线咨询:点击这里给我发消息

邮件:1877088071@qq.com

工作时间:周一至周五,9:30-18:30,节假日休息

QR code