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

2019-03-11 本文已影响19人 AiFany

maze.jpg

一、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值。