在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 *