A*算法寻求最短路

A*算法关键在在于评估函数。评估函数分为两个部分，f(n) = g(n) + h(n):

如果g(n) = 0的话，那么我们只关心从当前点到目标的距离，类似贪心扩展
如果h(n) 不大于实际距离的话，那么一定可以得到最优解。h(n)越准确那么效率越高。
如果h(n) = 0的话，那么退化成为单源最短路静问题，dijkstra算法。

对于迷宫函数使用曼哈顿距离是最简单也是安全的，但是相比BFS可以少访问不少节点。

def astar(maze, src, dst):
    def get_est_dist(p, to_src_dst):
        to_dst_dist = abs(p[0] - dst[0]) + abs(p[1] - dst[1])
        return to_dst_dist + to_src_dst

    nexts = []
    item = (get_est_dist(src, 0), src, 0)
    heapq.heappush(nexts, item)
    visited = set()
    visited.add(src)

    dist = -1

    while nexts:
        (est_dist, p, d) = heapq.heappop(nexts)
        if p == dst:
            dist = d
            break

        for u in nns(maze, p):
            if maze[u[0]][u[1]] == 1 and u not in visited:
                visited.add(u)
                item = (get_est_dist(u, d + 1), u, d + 1)
                heapq.heappush(nexts, item)

    print('astar: visited {} nodes, dist: {}'.format(len(visited), dist))
    return dist

突然发现python里面允许比较tuple是一件非常有意义的事情：将tuple[0]设置成为比较value的话，那么就可以直接将tuple作为数据放在最小堆里面，而不用单独定义类型和编写比较函数。

我的测试用例里面生成了一个200x200的迷宫图，可以看到astar访问的节点数量是BFS的一半。

find shortest path: (0, 0) -> (199, 199)
bfs: visited 31023 nodes, dist: 398
astar: visited 16973 nodes, dist: 398