对于A*算法的一些疑问

链接:http://godorz.info/2009/11/some-questions-about-a-star-algorithm/

Article 13518 of comp.games.development.programming.algorithms:
Path: nntp.stanford.edu!newsfeed.stanford.edu!logbridge.uoregon.edu
!cyclone-west.rr.com!news.rr.com|news-west.rr.com
!newsfeed2.earthlink.net!newsfeed.earthlink.net
!newsmaster1.prod.itd.earthlink.net
!newsread2.prod.itd.earthlink.net.POSTED!not-for-mail
From: “Tom Hatfield” <[e-mail]>
Newsgroups: comp.games.development.programming.algorithms
References: <8bvf90$rto$[e-mail]>
Subject: Re: Path-finding algorithm
Lines: 97
Message-ID: <mXDF4.13013$[e-mail]>
Date: Sun, 02 Apr 2000 08:56:50 GMT
NNTP-Posting-Host: 63.27.26.87
Organization: EarthLink Inc. — http://www.EarthLink.net

> Hi,
>   我在寻找着一种路径-查找算法(我觉得是这么叫的).我正在写着基于瓷砖的游戏,我需要一种可以找到
>   绕过障碍物(无法被穿越的瓷砖)到达目的瓷砖的算法.

因为你并没有要求特定的编程语言,因此我仅仅是给出了算法的一个框架.下面是一个对于A*算法的半编码的描述,A*算法对于你所要求的找到穿越障碍物的路径的问题是快速而且高效的.你可以用它来处理很多其他的问题.

基本上,A*算法作用于以下3个部分:Opem表(存储需要被扫描的结点),Closed表(存储并不需要被扫描的结点)以及启发函数.在这里的问题中,一个”结点”包含一片瓷砖的简单信息.每片瓷砖有它自己的结点,但是扫描地图上的所有瓷砖的可能是很小的;事实上,一切顺利的话,你仅会扫描很少的一部分.

启发函数是A*算法效率的关键.它是从任意给定瓷砖到目标瓷砖的距离的估计.你的启发函数越接近真实距离,你寻找到的路径将越优.你能使用的最好的启发函数是连接起始结点到目标结点的直线:

d=|gx-sx|+|gy-sy|

为了让代码能够运行起来,你需要一个数组来保存Open表中的结点,另一个数组来保存Closed表中的结点.为了安全起见,Closed表的数组需要与你的地图大小(x*y)一样大,而Open表的数组大约是地图大小的一半.你的结点的结构大概就像下面的样子:

structure Node(n)

.XCoord

.YCoord

.Cost

.XParent

.YParent

现在让我们更深入地讨论该算法.我不能保证这一定是A*算法的最佳版本,因为这是我特别为Visual Bacis设计的(你步可能从因特网上找到一份VB语言编写的路径-查找算法,相信我).它的确含有一个我遇到过的不足,但是你可以稍作调整来满足你的需要.代码如下:

将起始结点压入Open表

Do:

找出Open表中拥有最佳的估计值的结点(耗散值+启发值)
把该结点压入Closed表中

If 该结点就是目标结点,结束程序,返回真值
Else,对该结点可达的所有邻居结点n:

计算结点n的估计值e(耗散值+启发值)

If 结点n已经在Open表中

If 结点n先前的估计值比当前的估计值e更优,那么仍保持结点n在Open表中
Else,把结点n移至Closed表中(它当前的估计值e更槽糕,因此我们可以无视n已经在Open表的事实)

If 结点n已经在Closed表中

If 结点n先前的估计值比当前的估计值e更优,把结点n移至Open表中
Else,那么仍保持结点n在Closed表中

If 结点n既不在Open表中,也不在Closed表中,那么把结点n移至Open表中

Loop while Open表中仍然有结点

当程序结束时,递归地查找结点的父亲位置得到最终的路径.

就是这样子.如果你在理解上有什么问题,我建议你可以在一张简单地图上,跟踪你是如何遍历结点的.这可以让你更好地理解算法如何运转.(我自己就这么做了)

就像我说的,这仅仅是A*算法众多实现中的一种.A*算法有很多变形,这决定于你的要求.也许你可以好好地检查这些实现:

我曾经问过一些人(A*算法的实现),但至今我没有得到任何回复.在下面描述中,你可以很快地做出一些修改,以得到更好的结果:

If 结点n已经在Closed表中

If 结点n先前的估计值比当前的估计值e更优,把结点n移至Open表中
Else,那么仍保持结点n在Closed表中

我不清楚在程序运行时,这会起到什么作用.但是在测试之后,我发现,将一个结点从Closed表中移出是没有什么道理的
不管怎么样,如果你有什么问题的话,尽量去尝试吧.这算法在很多情况下是可以工作的.祝你好运.