Python3 趣味系列题7(续) ------ A

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；

1. 获得这个网格经过一步移动可以去的网格列表；
2. 遍历这个列表中的网格D；
3. 如果网格D不在open list中，把它加入open list，并且把当前方格C设置为它的父辈网格，并存储网格D的F值；
4. 如果D已经在 open list 中，说明之前已经到达过网格D。那就需要比较以前的路径和当前的路径哪条路径是最优的，也就是F值最小的。也就是得到当前的F值和之前的F值中较小的。如果是以前的小，则不需要任何操作。如果是当前的F值较小，则就把网格D的父辈网格变为当前的网格C，并且存储网格D的F值。

B. 当终点在open list中，表明路径已经找到了，或者open list是空的，此时没有路径，退出循环。

C. 保存路径。从终点网格开始，沿着父辈网格移动直至起点网格，得到最终的路径。

二、路径展示

• 遍历墙的迷宫

image image

• 遍历网格的迷宫

image image

点击获得更多趣味谜题。欢迎Follow，感谢Star!!! 扫描关注微信公众号pythonfan，获取更多。

image image