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