博客地址：httpblogcsd
etlm
xjfarticledetails8917679里面有详细的介绍和代码下载
这段时间学习了A（ASTAR）算法寻找最优路径算法。其实现从A点寻找到达B点的最优路径。其中用的知识有，上期介绍的链表，链表的插入与排序。首先是先用字符在命令窗口来绘制地图显示路径的，在测试算法成功后，将算法应用到基于文档的程序窗口中，更直观的显示。下面是详细介绍。
一A算法介绍A算法是一种静态路网中求解最短路最有效的方法。公式表示为：f
g
h
f
是从初始点经由节点
到目标点的估价函数，g
是在状态空间中从初始节点到
节点的实际代价，h
是从
到目标节点最佳路径的估计代价。其实A算法是一种最好优先的算法只不过要加上一些约束条件罢了。由于在一些问题求解时，我们希望能够求解出状态空间搜索的最短路径，也就是用最快的方法求解问题，A就可以很好的完成这个任务。我们先下个定义，如果一个估价函数可以找出最短的路径，我们称之为可采纳性。A算法是一个可采纳的最好优先算法。A算法的估价函数可表示为：f
g
h
这里，f
是估价函数，g
是起点到节点
的最短路径值，h
是
到目标的最短路经的启发值。由于这个f
其实是无法预先知道的，所以我们用前面的估价函数f
做近似。g
代替g
，但g
g
才可（大多数情况下都是满足的，可以不用考虑），h
代替h
，但h
h
才可（这一点特别的重要）。可以证明应用这样的估价函数是可以找到最短路径的，也就是可采纳的。我们说应用这种估价函数的最好优先算法就是A算法。我们假设某人要从A点移动到B点，但是这两点之间被一堵墙隔开。如图1，绿色是A，红色是B，中间蓝色是墙。
1
图1初试状态
图2第一步
f为完成A算法我们事先建立好一个ope
list链表和closelist链表，初始化时将第一个方块也即图1中的绿色方块位置放到ope
list中。我们第一步计算的结果如图2所示。每个方格都标上了F，G，H的值，就像起点右边的方格那样，左上角是F，左下角是G，右下角是H。1从起点A开始，并把它就加入到一个由方格组成的ope
list开放列表中。这个ope
list有点像是一个购物单。当然现在ope
list里只有一项，它就是起点A，后面会慢慢加入更多的项。Ope
list里的格子是路径可能会是沿途经过的，也有可能不经过。基本上ope
list是一个待检查的方格列表。2查看与起点A相邻的方格忽略其中墙壁所占领的方格，及在closelist中的方格，把其中可走的walkable或可到r