maze.jpg
前文: Python3 趣味系列题 7 ------ Prim 算法生成完美迷宫
一, A * 算法
寻找路径的算法有很多, 例如 BFS 算法, Dijkstra 算法等. BFS 算法可以在较短时间内寻找到从起点到结束点的路径, 但不一定是最优的. 而 Dijkstra 算法从起点开始向外围逐渐扩展, 直到达到结束点, 因此得到的路径一定是最优的, 但是耗时较长. A * 算法可以看作这 2 个算法的结合, 这主要依赖于 A * 算法的启发式搜寻策略, 下一步去往的网格是下面式子中具有最小值的网格:
F = G + H
G: 代表从起始点网格到当前这个网格距离的代价;
H: 从当前这个网格到结束点网格距离的代价;
下面举例说明: 前一个到达的网格假设为 A, 从这个网格可以去的网格有 C1, C2,C3. 然后计算这 3 个网格中 F 的值最小的网格作为下一个要去的网格. 当不考虑 G 时, 算法就变为 BFS; 当不考虑 H 时, 算法就变为 Dijkstra 算法. 注意上面的 H 只是理论上的代价值, 因为实际中可能存在障碍点, 这一点并不妨碍算法的进行.
网格之间的距离可以根据网格的移动方式定义, 例如只可以上下左右的移动, 一般就考虑曼哈顿距离, 例如本文. 可以 8 个方向移动的, 可以在斜的方向上考虑欧式距离等.
下面给出 A * 算法具体的步骤:
A. 把起始点网格加入 open list ; 循环如下过程:
遍历 open list , 查找其中 F 值最小的网格, 把它作为当前要处理的网格 C;
把网格 C 移到 close list;
获得这个网格经过一步移动可以去的网格列表;
遍历这个列表中的网格 D;
如果网格 D 不在 open list 中, 把它加入 open list, 并且把当前方格 C 设置为它的父辈网格, 并存储网格 D 的 F 值;
如果 D 已经在 open list 中, 说明之前已经到达过网格 D. 那就需要比较以前的路径和当前的路径哪条路径是最优的, 也就是 F 值最小的. 也就是得到当前的 F 值和之前的 F 值中较小的. 如果是以前的小, 则不需要任何操作. 如果是当前的 F 值较小, 则就把网格 D 的父辈网格变为当前的网格 C, 并且存储网格 D 的 F 值.
B. 当终点在 open list 中, 表明路径已经找到了, 或者 open list 是空的, 此时没有路径, 退出循环.
C. 保存路径. 从终点网格开始, 沿着父辈网格移动直至起点网格, 得到最终的路径.
二, 路径展示
遍历墙的迷宫
image
image
遍历网格的迷宫
image
image
来源: http://www.jianshu.com/p/db60229e599b