A*搜索算法启发式估价函数

可视化演示

A*算法是结合Dijkstra和贪心最优搜索的启发式搜索算法，通过估价函数f(n)=g(n)+h(n)实现最优... 切换模式查看不同维度。

核心原理：导航仪的总账本

小林打开导航的瞬间，系统就把整张城市地图拆成了无数个路口节点。每个路口都有一本“小账本”：左边一栏记“已经走过的里程”，右边一栏记“向导预估的剩余里程”，中间画一条粗线标出两者之和。A* 的决策逻辑就这么朴素——每到一个分岔路口，它从不冲动，而是把脚下所有候选路口的总账翻一遍，挑最小的一笔继续前进。

这本账本的名字叫估价函数。其中，g(n) 是从起点到当前路口 n 已经实际花掉的距离，它真实可靠，像你车上的里程表；h(n) 则是从 n 到终点还需要的估计距离，它是向导凭经验给出的预测，像地图上的直线距离。A* 把两者相加，得到总估价 f(n)，然后每轮从“候选路口清单”（开放表）中挑 f 值最小的路口去“实地考察”，考察完的路口放进“已考察清单”（关闭表），避免反复绕圈。

当小林跟着导航绕过第一个堵点，他发现导航并没有盲目扩张“所有方向的候选路口”，而是优先往餐厅方向倾斜。这正是 f 值排序的魔法：它让搜索既记住过去的教训，又盯住未来的目标。一个会记旧账又敢预测未来的司机，永远比只看后视镜或只盯挡风玻璃的人更快到目的地。

启发函数设计：向导的目测距离

小林的向导是个本地通，他站在路口报距离时，嘴里念叨着几种“目测法”：第一种，只数东西向和南北向的街道格数，加起来就是“出租车理论路程”，这叫曼哈顿距离；第二种，直接透视楼群，报两点间直线距离，这是欧氏距离；第三种，允许沿 45 度斜穿广场，报的是对角线距离。选哪种目测法，直接决定了导航“抢不抢时间、绕不绕远路”。

在网格地图中，曼哈顿距离是最常用的启发函数，因为每一步的代价如果是水平或垂直移动 1，那么最理想情况下从 (x₁,y₁) 到 (x₂,y₂) 至少要走这两个方向差的绝对值之和：

向导的目测能力越接近真实路况，导航的搜索就越“有向性”：预估太高，它会漏掉真正的最优捷径；预估太低，它又会在太多无谓方向磨蹭。选启发函数，就像选导游——不求神机妙算，但求“报低不报高”，永远给一个乐观但不离谱的下限。小林的向导最终选用了曼哈顿距离，因为城市是棋盘式布局，直线距离反而失真，这个细节让导航系统在每秒几十次的路径重算中省下了大量计算。

可采纳性：不说大话的向导

小林问向导：“到餐厅到底还有多远？”向导微微一笑：“放心，我报的数字只会少报，绝不虚报。”这句朴素的承诺，在算法世界里有个严谨的名字——可采纳性（admissibility）。如果一个启发函数对所有路口 n 都满足“估计值不超过真实值”，那么 A* 第一次走到终点时，记录下的路径必然是最优的。

为什么“只说少话”能保住最优解？因为如果向导某次虚报了一个过高的距离，系统就可能被误导：它以为某条死路很近而另一条活路很远，于是提前砍掉了真正的最优分支。反过来，只要 h 永远不大于 h*（真实最小代价），那么任何一条比当前路径更好的路，它的 f 值一定不会比当前扩展节点大，搜索就永远不会被“假的好消息”骗走。可采纳性的数学表达简洁得令人惊讶：

有了这不撒谎的向导，A* 才敢拍胸脯说“找到的就是最好的”。小林的导航在屏幕上弹出“最优路线已规划”时，这条路线也许不是直觉上最直的那条，但它一定经得起数学证明的推敲。可采纳性就是搜索界的诚信体系——信任一旦建立，系统就不需要反复怀疑自己走过的每一步。

一致性：一步一校对的默契

小林发现，导航每隔一个路口就会自动刷新预估：“咦，刚才那个路口说还剩 8 公里，走完这条街变成 7 公里了，少得还挺匀。”这种“每走一步，估计值正好减少一步实际消耗”的默契，就是一致性（consistency），也叫单调性。

一致性要求满足三角不等式：从 n 出发，先走到邻居 m 再继续到终点，这个分两步的估计，不应该比直接从 n 预估到终点更小。换句话说，h 值沿路径不得“跳涨”，只能像下楼梯一样逐级走低。这个性质带来一个巨大的工程红利：一旦某个路口被放入关闭表（已考察），它的 f 值就定格了，永远不会被更优路径“翻案”，所以关闭表不需要重开，A* 的运行效率大幅提升。

一致性是可采纳性在“动态过程中的升级版”：可采纳性保证向导从不说大话，一致性保证向导每走一步都言行一致。小林感慨，靠谱的导航不仅开头靠谱，全程都靠谱。对他这种路痴来说，系统的每一步都保持前后连贯，比单纯的“最终正确”更让人安心——工程上也因此省掉了重新评估已关闭节点的开销。

性能对比：三种司机的赛跑

小林叫了三个朋友模拟三种寻路策略：老张开 Dijkstra，每到一个路口就把所有方向的候选路口都摊开，一视同仁地扩张，最后总能覆盖大片区域，像在纸上画一个以起点为圆心的巨大涟漪；小李开贪心最优先，完全不听里程表，只管向导指的方向猛冲，速度飞快但容易撞进死胡同还得折返；小林自己的 A* 则两只眼睛同时用——左手翻里程账本，右手听向导预言，每步挑总账最少的走。

Dijkstra 其实是 A* 在 h(n)=0 时的特例：完全放弃向导，自然每一步都“无方向感”，扩展节点数像扇形展开；而贪心算法则是让 h 主导一切、g 完全缺席，等于蒙眼信向导，路径正确性毫无保障。A* 的扩展节点数通常远小于 Dijkstra，尤其在开阔地图上，它几乎笔直地扑向目标，只探索一条“价值走廊”而非整片区域。但这不代表 A* 免费：它需要维护优先队列，开放表中可能有大量节点占用内存，空间代价不容小觑。

| 算法 | 使用 g | 使用 h | 最优性 | 扩展规模 |

|------|--------|--------|--------|----------|

| Dijkstra | ✅ | ❌ | 保证 | 全方向扩散 |

| 贪心最优先 | ❌ | ✅ | 不保证 | 奔向目标但易绕路 |

| A* | ✅ | ✅ | 可采纳时保证 | 介于两者之间 |

小林的导航最终选定了 A*，因为它像一位既讲原则（尊重走过的路）又懂变通（相信合理预估）的聪明司机。老张的稳重、小李的敏捷，都被 A* 的两分法融合成一种更高级的驾驶哲学：每一个路口，都同时向过去负责、向未来探路。

工程优化：老司机的省油技巧

导航地图铺满全城时，即使 A* 也不能对每个路口都精打细算。小林的老司机朋友传授了几个“省油绝招”：第一条，双向 A*——起点和终点各派一支搜索队，两队向中间包夹，直到两队在某个路口碰头。由于搜索从两端同时收敛，扩展的总体积从一个大圆变成两个小圆，节点数量往往能省下一半以上。第二条，加权 A*——给 h 乘上一个系数 ε>1，让向导的声音更响亮，搜索更激进地冲向目标，代价是路径质量轻微打折，适合对实时性要求极高、路径只需“够好”的场景：

第三条更狠：跳点搜索（JPS）。在网格地图中，直线走廊上的中间点其实完全不用逐个考察，A* 通过“跳点”规则直接跳过无分叉的直线路段，只在拐弯处驻足。小林看着导航屏幕，搜索点不是密密麻麻铺满街区，而是像跳房子一样精准落子在每个关键转角，原本几万次扩展被压到几百次。这些优化让 A* 不仅活在游戏 NPC 的寻路代码里，也活在扫地机器人绕过充电桩、快递机器人穿过仓库货架的每一次转身中——好算法从来不是纸上谈兵，而是把聪明的估价变成现实世界里的省时省油。

AI 应用场景

Python 演示

import heapq def a_star_search(grid, start, goal):    rows, cols = len(grid), len(grid[0])    open_heap = [(0, start)]    g_cost = {start: 0}    came_from = {}    closed = set()    while open_heap:        _, current = heapq.heappop(open_heap)        if current == goal:            path = []            while current in came_from:                path.append(current)                current = came_from[current]            path.append(start)            return path[::-1]        if current in closed:            continue        closed.add(current)        cx, cy = current        for dx, dy in ((1,0),(-1,0),(0,1),(0,-1)):            nx, ny = cx+dx, cy+dy            if not (0 <= nx < rows and 0 <= ny < cols):                continue            if grid[nx][ny] == 1:                continue            neighbor = (nx, ny)            tentative = g_cost[current] + 1            if tentative < g_cost.get(neighbor, float('inf')):                if neighbor in closed:                    continue                g_cost[neighbor] = tentative                came_from[neighbor] = current                h = abs(nx-goal[0]) + abs(ny-goal[1])                heapq.heappush(open_heap, (tentative+h, neighbor))    return [] if __name__ == "__main__":    grid = [        [0,0,0,0,0,0,0,0],        [0,1,1,0,1,0,0,0],        [0,0,0,0,1,0,1,0],        [0,1,0,0,0,0,1,0],        [0,1,0,1,0,0,0,0],        [0,0,0,1,0,1,1,0],        [0,1,0,0,0,0,0,0],        [0,0,0,1,1,0,0,0],    ]    start = (0, 0)    goal = (7, 7)    path = a_star_search(grid, start, goal)    if path:        print("路径长度:", len(path)-1)        for r in range(len(grid)):            line = ""            for c in range(len(grid[0])):                if (r, c) == start:                    line += "S"                elif (r, c) == goal:                    line += "G"                elif (r, c) in path:                    line += "*"                elif grid[r][c] == 1:                    line += "#"                else:                    line += "."            print(line)    else:        print("未找到路径")

1. open_heap = [(0, start)]使用堆维护开放表，保证每轮弹出的都是 f 值最小的路口，对应可视化中“挑总账最少的路口先考察”。
2. g_cost = {start: 0}起点已知代价为 0，与思维导图中“起点代价为零”节点呼应。
3. if current in closed: continue关闭表中的节点已考察完毕，直接跳过，体现一致性的工程红利。
4. tentative = g_cost[current] + 1每次移动代价为 1，向上累积 g 值，这是“记账本”的实时更新。
5. h = abs(nx-goal[0]) + abs(ny-goal[1])曼哈顿距离计算启发值，永不高估真实代价。
6. heapq.heappush(open_heap, (tentative+h, neighbor))以 f = g + h 作为优先级入堆，这正是 A* 的核心估价函数。

常见误区

面试题