AI 版 (精华区)
发信人: yale (武松在世), 信区: AI
标 题: 深入A*算法
发信站: 哈工大紫丁香 (2003年12月15日15:35:14 星期一), 站内信件
发信人: sugy (不再灌水), 信区: AI
标 题: 深入A*算法
发信站: 饮水思源站 (Tue Jul 10 15:27:46 2001), 转信
一、前言
在这里我将对A*算法的实际应用进行一定的探讨，并且举一个有关A*
算法在最短路径搜索 的例子。值得注意的是这里并不对A*的基本的概
念作介绍，如果你还对A*算法不清楚的话， 请看姊妹篇《初识A*算法》。
二、A*算法的程序编写原理
我在《初识A*算法》中说过，A*算法是最好优先算法的一种。只是有一
些约束条件而已。 我们先来看看最好优先算法是如何编写的吧。
如图有如下的状态空间：（起始位置是A，目标位置是P，字母后的数字表示节点的
估价
值）
A － 5
／ │ ＼
／ │ ＼
↓ ↓ ＼
B-4 C-4 D-6
／｜ ／ ＼ ／＼
／ ｜ ／ ＼ ／ ＼
／ ｜ ｜ ↓ ｜ ＼
E-5 F-5 G-4 H-3 I J
／\ ／＼ ｜ ／ ＼ /＼ ＼
／ \ ／ ｜｜ ／ ＼ / ＼ ＼
／ v ｜｜ ↓ ↓／ ＼ ＼
K L M N O-2 P-3 Q R
｜ ｜
｜ ｜
｜ ｜
S T
搜索过程中设置两个表：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*算法实现最短路径的搜索。在此之 前你
最好认真的理解前面的算法。
三、用A*算法实现最短路径的搜索
在游戏设计中，经常要涉及到最短路径的搜索，现在一个比较好的方法
就是用A*算法进行设 计。他的好处我们就不用管了，反正就是好！^_*
注意下面所说的都是以 ClassAstar 这个程序为蓝本，你可以在这里
下载这个程序。这个程 序是一个完整的工程。里面带了一个EXE文件。
可以先看看。
先复习一下，A*算法的核心是估价函数f(n)，它包括g(n)和h(n)两部分.
g(n) 是已经走过的 代价，h(n)是n到目标的估计代价。在这个例子
中g(n)表示在状态空间从起始节点到 n节点的 深度，h(n)表示n节点
所在地图的位置到目标位置的直线距离。啊！一个是状态空间，一个
是 实际的地图，不要搞错了。再详细点说，有一个物体A，在地图上
的坐标是(xa,ya)，A所要到 达的目标b的坐标是(xb,yb)。则开始搜索
时，设置一个起始节点1，生成八个子节点2 - 9 因 为有八个方向。
如图： 节 点 1 g(1)=0
／| | ＼ h(1)=(Xb*Xb-Xa*Xa)+(Yb*Yb-Ya*Ya)
／ ／ | ＼
／ ／ | ＼
节点2 节点3 节点4...节点9 g(9)=1
／|＼
h(9)=(Xb*Xb-X9*X9)+(Yb*Yb-Y9*Y9)
／ | ＼
／ | ＼
节点10 节点11...节点17 g(17)=2
h(17)=(Xb*Xb-X17*X17)+(Yb*Yb-Y17*Y17)
仔细看看节点1、9、17的g(n)和h(n)是怎么计算的。现在应该知道了
下面程序中的f(n)是如何 计算的吧。开始讲解源程序了。其实这个
序是一个很典型的教科书似的程序，也就是说只要 你看懂了上面的
伪程序，这个程序是十分容易理解的。不过他和上面的伪程序有一些
的不同， 我在后面会提出来。
先看搜索主函数：
void AstarPathfinder::FindPath(int sx, int sy, int dx, int dy)
{
NODE *Node, *BestNode;
int TileNumDest;
//得到目标位置，作判断用
TileNumDest = TileNum(sx, sy);
//生成Open和Closed表
OPEN=( NODE* )calloc(1,sizeof( NODE ));
CLOSED=( NODE* )calloc(1,sizeof( NODE ));
//生成起始节点，并放入Open表中
Node=( NODE* )calloc(1,sizeof( NODE ));
Node->g = 0;
//这是计算h值
Node->h = (dx-sx)*(dx-sx) + (dy-sy)*(dy-sy); //此处按道理应用
开方
//这是计算f值，即估价值
Node->f = Node->g+Node->h;
Node->NodeNum = TileNum(dx, dy);
Node->x = dx;
Node->y = dy;
OPEN->NextNode=Node; // make Open List point to first
node
for (;;)
{ //从Open表中取得一个估价值最好的节点
BestNode=ReturnBestNode();
//如果该节点是目标节点就退出
if (BestNode->NodeNum == TileNumDest) // if we've found the
//end, break and
finish
break;
//否则生成子节点
GenerateSuccessors(BestNode,sx,sy);
}
PATH = BestNode;
}
再看看生成子节点函数 GenerateSuccessors：
void AstarPathfinder::GenerateSuccessors(NODE *BestNode,int dx, int dy)
{
int x, y;
//哦！依次生成八个方向的子节点，简单！
// Upper-Left
if ( FreeTile(x=BestNode->x-TILESIZE, y=BestNode->y-TILESIZE)
)
GenerateSucc(BestNode,x,y,dx,dy);
// Upper
if ( FreeTile(x=BestNode->x, y=BestNode->y-TILESIZE) )
GenerateSucc(BestNode,x,y,dx,dy);
// Upper-Right
if ( FreeTile(x=BestNode->x+TILESIZE, y=BestNode->y-TILESIZE)
)
GenerateSucc(BestNode,x,y,dx,dy);
// Right
if ( FreeTile(x=BestNode->x+TILESIZE, y=BestNode->y) )
GenerateSucc(BestNode,x,y,dx,dy);
// Lower-Right
if ( FreeTile(x=BestNode->x+TILESIZE, y=BestNode->y+TILESIZE)
)
GenerateSucc(BestNode,x,y,dx,dy);
// Lower
if ( FreeTile(x=BestNode->x, y=BestNode->y+TILESIZE) )
GenerateSucc(BestNode,x,y,dx,dy);
// Lower-Left
if ( FreeTile(x=BestNode->x-TILESIZE, y=BestNode->y+TILESIZE)
)
GenerateSucc(BestNode,x,y,dx,dy);
// Left
if ( FreeTile(x=BestNode->x-TILESIZE, y=BestNode->y) )
GenerateSucc(BestNode,x,y,dx,dy);
}
看看最重要的函数GenerateSucc：
void AstarPathfinder::GenerateSucc(NODE *BestNode,int x,int y,int
dx,int dy)
{
int g, TileNumS, c = 0;
NODE *Old, *Successor;
//计算子节点的 g 值
g = BestNode->g+1; //g(Successor)=g(BestNode)+cost of
getting
//from BestNode to Successor
TileNumS = TileNum(x,y); // identification purposes
//子节点再Open表中吗？
if ( (Old=CheckOPEN(TileNumS)) != NULL ) // if equal to
NULL then
//not in OPEN list, else it returns the Node in Old
{
//若在
for( c = 0; c < 8; c++)
if( BestNode->Child[c] == NULL ) // Add Old to the
list of
// BestNode's Children (or
Successors).
break;
BestNode->Child[c] = Old;
//比较Open表中的估价值和当前的估价值（只要比较g值就可以
了）
if ( g < Old->g ) // if our new g value is < Old's then
//reset Old's parent to point to
BestNode
{
//当前的估价值小就更新Open表中的估价值
Old->Parent = BestNode;
Old->g = g;
Old->f = g + Old->h;
}
}
else //在Closed表中吗？
if ( (Old=CheckCLOSED(TileNumS)) != NULL ) // if equal to
NULL then
// not in OPEN list, else it returns the
Node in Old
{
//若在
for( c = 0; c< 8; c++)
if ( BestNode->Child[c] == NULL ) // Add Old to the list of
//BestNode's Children (or
Successors).
break;
BestNode->Child[c] = Old;
//比较Closed表中的估价值和当前的估价值（只要比较g值就可
以了）
if ( g < Old->g ) // if our new g value is < Old's
then
// reset Old's parent to point to
BestNode
{
//当前的估价值小就更新Closed表中的估价值
Old->Parent = BestNode;
Old->g = g;
Old->f = g + Old->h;
//再依次更新Old的所有子节点的估价值
PropagateDown(Old); // Since we changed the g value of
//Old,we need to propagate this new
//value downwards, i.e.
// do a Depth-First traversal of
the tree!
}
}
else//不在Open表中也不在Close表中
{
//生成新的节点
Successor = ( NODE* )calloc(1,sizeof( NODE ));
Successor->Parent = BestNode;
Successor->g = g;
Successor->h = (x-dx)*(x-dx) + (y-dy)*(y-dy); // should do
// sqrt(), but since we
don't really
Successor->f = g+Successor->h; // care about the
distance but
//just which branch looks
Successor->x = x; // better this should
suffice.
// Anyayz it's faster.
Successor->y = y;
Successor->NodeNum = TileNumS;
//再插入Open表中，同时排序。
Insert(Successor); // Insert Successor on OPEN
list wrt f
for( c =0; c < 8; c++)
if ( BestNode->Child[c] == NULL ) // Add Old
to the
// list of BestNode's Children (or
Successors).
break;
BestNode->Child[c] = Successor;
}
}
哈哈！A*算法我懂了！当然，我希望你有这样的感觉！不过我还要
再说几句。仔细看看这个程序，你会发现，这个程序和我前面说的伪
程序有一些不同，在GenerateSucc函数中，当子节点 在Closed表中时，
没有将子节点从Closed表中删除并放入Open表中。而是直接的重新
计算该 节点的所有子节点的估价值（用PropagateDown函数）。这
样可以快一些！另当子节点在 Open 表和Closed表中时，重新的计算
估价值后，没有重新的对Open表中的节点排序，我有些想不通， 为什
么不排呢？:-(，会不会是一个小小的BUG。你知道告诉我好吗？
好了！主要的内容都讲完了，还是完整仔细的看看源程序吧！希望我
所的对你有一点帮助，一 点点也可以。如果你对文章中的观点有异议
或有更好的解释都告诉我。
--
**************************************************************************
归去来兮！田园将芜胡不归？既自以心为形役，奚惆怅而独悲？悟已往之不谏，知来
者之可追；实迷途其未远，觉今是而昨非。
归去来兮，请息交以绝游。世与我而相遗，复驾言兮焉求？悦亲戚之情话，乐琴书以
消忧。农人告余以春兮，将有事乎西畴。或命巾车，或槕孤舟。既窈窕以寻壑，亦崎
岖而经丘。木欣欣以向荣，泉涓涓而始流。羡万物之得时，感吾生之行休。
※ 来源:·饮水思源站 bbs.sjtu.edu.cn·[FROM: 211.80.39.110]
--
※ 转寄:·饮水思源 bbs.sjtu.edu.cn·[FROM: 202.118.239.104]
--
As we know,there are known knowns.There are things we know we know.
We also know there are known unknowns. That is to say
We know there are somethings we do not know.
But there are also unknown unknowns, the ones we don't know we don't know
-Rumsfeld
※ 来源:·哈工大紫丁香 bbs.hit.edu.cn·[FROM: 202.118.239.104]
Powered by KBS BBS 2.0 (http://dev.kcn.cn)
页面执行时间：209.671毫秒