A-star寻路记 • 果果日记

前段时间研究小游戏的同学用过A*算法寻路，当时我只是有个印象，恰巧最近有同学做数模问我，我也只能硬着头皮看一看了。先声明，太low或者有差错也不管哈。

题目要求

给定一个n*n的地图，其中有障碍物和跨越难度各不相同的地形，现要求找到总代价最小的路径。

如果光溜溜地摆出地图，要凭空想出一个方法挺难的，而且最重要的是复杂度也许很高。但我们有a-star。

这个名词大家一定不陌生，但对它的含义可能一知半解。常见的启发式算法如模拟退火算法、神经网络、蚁群算法等，它们在面对最优化问题时，并不从某个精妙的逻辑出发（像数学证明那样），而是以直观的感受构建算法，消耗有限的时间和空间尽量得到接近最优的可行解（但通常无法证明）。

直观地讲，你要找最小路径，那只能从出发点开始，一步步地试出来，不过呢，复杂度不仅达到了n次方，还有可能存在回路。A-star算法提供的解决方案是，用两张表分别存储被考虑用来寻找最短路径的区块（open）与不再考虑用来寻找最短路径的区块（closed），同时启发式算法能保证尽量选择较优的路径。

最基础的，从起始点出发，每次从open表中选总代价最小的项（F最小），向周围8个方向前进（将这些区块加入open表），这是A-star的主循环。

新遇到的区块可以加入open列表，但扫描后的点会加入closed列表。

搜索的路径需要被记录，可以用一个栈结构，从open列表进入时入栈，如果一个区块周围不再有符合要求的区块则回退。

不能在closed表中，不能超出边界，不能是建筑，如果已在open列表，当前G值大于open表中记录的G值也不符合要求。

F=G+H

F即总代价，包括G实际经过的路程和H估算的该点离终点的距离。

可以直接用笛卡尔距离，也可以直线+拐弯etc，总之提供一个大概的参考值。

写在毕设里了，下回搬运。