A* 搜索算法是什么？

一致性

如果从一个节点移动到相邻节点时，启发式估计满足单调关系，且不会出现前后矛盾的跳变，通常就认为它是一致的。对于 A* 来说，这能让搜索过程更稳定，也更容易保证最优性。

Python 实现示例

下面这个例子演示了如何用 A* 在一个加权图里寻找从 A 到 G 的最短路径。这里边上的数字表示实际移动代价，节点上的启发式值则用于估算到终点的距离。

先看思路：从 A 出发后，算法会比较几个候选方向的 f(n) 值。它并不会'看谁顺眼'，而是始终选择当前最有希望的那条路。这个例子里，最终找到的路径是 A -> E -> D -> G。

def aStarAlgo(start_node, stop_node):
    open_set = set([start_node])
    closed_set = set()
    g = {}
    parents = {}

    g[start_node] = 0
    parents[start_node] = start_node

    while len(open_set) > 0:
        n = None

        for v in open_set:
            if n is None or g[v] + heuristic(v) < g[n] + heuristic(n):
                n = v

        if n is None:
            print('Path does not exist!')
            return None

        if n == stop_node:
            path = []
            while parents[n] != n:
                path.append(n)
                n = parents[n]
            path.append(start_node)
            path.reverse()
            print('Path found: {}'.format(path))
            return path

        for (m, weight) in get_neighbors(n):
            if m not in open_set and m not in closed_set:
                open_set.add(m)
                parents[m] = n
                g[m] = g[n] + weight
            else:
                if g[m] > g[n] + weight:
                    g[m] = g[n] + weight
                    parents[m] = n
                    if m in closed_set:
                        closed_set.remove(m)
                        open_set.add(m)

        open_set.remove(n)
        closed_set.add(n)

    print('Path does not exist!')
    return None


def get_neighbors(v):
    if v in Graph_nodes:
        return Graph_nodes[v]
    return None


def heuristic(n):
    H_dist = {
        'A': 11,
        'B': 6,
        'C': 99,
        'D': 1,
        'E': 7,
        'G': 0,
    }
    return H_dist[n]


Graph_nodes = {
    'A': [('B', 2), ('E', 3)],
    'B': [('C', 1), ('G', 9)],
    'C': None,
    'E': [('D', 6)],
    'D': [('G', 1)],
}

aStarAlgo('A', 'G')

运行结果：

Path found: ['A', 'E', 'D', 'G']

这个例子里，A* 的行为很清晰：它不会只看眼前那条边的代价，也会把'走到终点还要花多少'算进去。正因为如此，它往往能避开一些表面上便宜、实际却更绕的路线。

A* 和 Dijkstra 的区别

很多人会把 A* 和 Dijkstra 放在一起比较。两者都能做最短路径搜索，但思路不一样。

• Dijkstra：更像是均匀地向外扩展，适合没有明确目标引导的最短路问题。
• A*：在 Dijkstra 的基础上引入启发式估计，因此能更有针对性地朝目标前进。

如果启发式函数设计得合理，A* 通常会比 Dijkstra 更省搜索范围；但如果启发式函数质量差，A* 的优势就会缩水。

小结

A* 搜索算法是图搜索里非常经典的一种方法。它把真实路径代价 g(n) 和启发式估计 h(n) 结合起来，在保证较强实用性的同时，也尽量兼顾最优性。对于游戏寻路、机器人导航、地图路径规划这类任务，它几乎是绕不开的基础算法之一。

真正决定 A* 表现的，不只是算法本身，还有启发式函数的质量。把这部分设计好，A* 才能真正发挥出'既聪明又稳妥'的优势。