第二部分:深入A*算法———浅析A*算法在搜索最短路径中的应用
一、前言
在这里我将对A*算法的实际应用进行一定的探讨,并且举一个有关A*算法在最短路径搜索 的例子。值得注意的是这里并不对A*的基本的概念作介绍,如果你还对A*算法不清楚的话, 请看姊妹篇《初识A*算法》。
这里所举的例子是参考AMIT主页中的一个源程序,你可以在AMIT的站点上下载也可以在我 的站点上下载。你使用这个源程序时,应该遵守一定的公约。
二、A*算法的程序编写原理
我在《初识A*算法》中说过,A*算法是最好优先算法的一种。只是有一些约束条件而已。 我们先来看看最好优先算法是如何编写的吧。
如图有如下的状态空间:(起始位置是A,目标位置是P,字母后的数字表示节点的估价值)
搜索过程中设置两个表:OPEN和CLOSED。OPEN表保存了所有已生成而未考察的节点,CLOSED 表中记录已访问过的节点。算法中有一步是根据估价函数重排OPEN表。这样循环中的每一 步只考虑OPEN表中状态最好的节点。具体搜索过程如下:
1)初始状态: OPEN=[A5];CLOSED=[]; 2)估算A5,取得搜有子节点,并放入OPEN表中; OPEN=[B4,C4,D6];CLOSED=[A5] 3)估算B4,取得搜有子节点,并放入OPEN表中; OPEN=[C4,E5,F5,D6];CLOSED=[B4,A5] 4)估算C4;取得搜有子节点,并放入OPEN表中; OPEN=[H3,G4,E5,F5,D6];CLOSED=[C4,B4,A5] 5)估算H3,取得搜有子节点,并放入OPEN表中; OPEN=[O2,P3,G4,E5,F5,D6];CLOSED=H3C4,B4,A5] 6)估算O2,取得搜有子节点,并放入OPEN表中; OPEN=[P3,G4,E5,F5,D6];CLOSED=[O2,H3,C4,B4,A5] 7)估算P3,已得到解; 看了具体的过程,再看看伪程序吧。算法的伪程序如下:
Best_First_Search() { Open = [起始节点]; Closed = []; while ( Open表非空 ) { 从Open中取得一个节点X,并从OPEN表中删除。 if (X是目标节点) { 求得路径PATH;返回路径PATH; } for (每一个X的子节点Y) { if( Y不在OPEN表和CLOSE表中 ) { 求Y的估价值;并将Y插入OPEN表中;//还没有排序 } else if( Y在OPEN表中 ) { if( Y的估价值小于OPEN表的估价值 ) 更新OPEN表中的估价值; } else //Y在CLOSE表中 { if( Y的估价值小于CLOSE表的估价值 ) { 更新CLOSE表中的估价值; 从CLOSE表中移出节点,并放入OPEN表中; } } 将X节点插入CLOSE表中; 按照估价值将OPEN表中的节点排序; }//end for }//end while }//end func
啊!伪程序出来了,写一个源程序应该不是问题了,依葫芦画瓢就可以。A*算法的程序与此 是一样的,只要注意估价函数中的g(n)的h(n)约束条件就可以了。不清楚的可以看看《初识A*算法》。好了,我们可以进入另一个重要的话题,用A*算法实现最短路径的搜索。在此之 前你最好认真的理解前面的算法。
|