A-Star算法的原理及应用

蔺敏达
2023-12-01

在ACM集训时看到小超同学在写一个A-Star的寻路算法,于是心痒痒,自己也想写一个,只是一直没有时间静下来好好动动脑筋,近日终于趁周末的时间,把A-Star实现了,可在地图上寻找较短路径,也可解任意迷宫。

在计算机中我们将地图表现为单元格,分可走单元格和不可走单元格。

如果用穷搜找最短路径当然是可以实现,但代价却很大。

于是我们必须要让计算机“有选择地走”。

若以当前单元格为起点(称为父单元格,它的周围有八个方向),下一步走哪呢?

这时就得给下一步的单元格(称为子单元格)进行“估价”。

“估价”可用估价函数来实现。

入门级的估价函数是这样的:

终点到目前点的估计代价=终点至当前点的直线距离

于是下一步的代价可以这样算

代价=起点到当前点的实际步数(通过一个变量累加可以直接得到)+ 终点到目前点的估计代价

然后把估价后的单元格放入“待考察表”

从待考察表中取代价最小的单元格作为起点,对它周围8个方向的单元格进行估价,然后把它放入“已考察表”。

若对一个单元格估价时,发现它已经在“待考察表”中则比较该单元格原先的估价和当前的估价,保留小的估价,并更新其父单元格属性。

不断重复以上过程,直到在“待考察表”中取出的单元格是终点单元格为止,若“待考察表为空”则表示找不到路径。

到达终点单元格后,通过其“父单元格”属性,一直找到起点,便构成一条路径。

原理已经讲完了。

根据这个原理,我用C++进行了模拟   (点这里下载演示程序

我把A-Star的算法封装成了一个类

使用极其方便



两个例子:

Enter the map's filename:
b.txt
Rows=7
Cols=13
. . . . . . . . . . . . .
. . . . . . x . . . . . .
. . . x x x x . . . . . .
. . . . . . x . . . . . .
. . . x x x x . . . . . .
. . . . . . x . . . . . .
. . . . . . . . . . . . .

Set the start point ( x , y ):
5 3
Set the end point ( x , y ):
12 3

Steps:
12,3
11,2
10,1
9,0
8,0
7,0
6,0
5,0
4,0
3,1
2,2
3,3
4,3
5,3

Rows=7
Cols=13
. . . . * * * * * * . . .
. . . * . . x . . . * . .
. . * x x x x . . . . * .
. . . * * * x . . . . . *
. . . x x x x . . . . . .
. . . . . . x . . . . . .
. . . . . . . . . . . . .

===========================

Enter the map's filename:
a.txt
Rows=7
Cols=7
. . . . . . .
. x x x . . .
. . . x . x .
. . . x . x .
. . . . . x .
. . . . . x .
. . . . . x .

Set the start point ( x , y ):
0 0
Set the end point ( x , y ):
6 6

Steps:
6,6
6,5
6,4
6,3
6,2
5,1
4,0
3,0
2,0
1,0
0,0

Rows=7
Cols=7
* * * * * . .
. x x x . * .
. . . x . x *
. . . x . x *
. . . . . x *
. . . . . x *
. . . . . x *
 
 类似资料: