1. 从暴力搜索到启发式搜索问题的本质在哪做AI编程的人绕不开搜索。推荐系统的路径规划、游戏里的寻路、大模型Agent的任务拆解、物流调度里的顺序编排底子上都是同一件事在一个巨大的状态空间里找一条通向目标的路径。区别只在于状态空间有多大、每一步的代价是什么、能不能提前预判哪条路更值得走。启发式搜索Heuristic Search就是用来回答哪条路更值得走这个问题的而贪婪最佳优先搜索和A*是这套方法里最经典的两个起点。我先讲清楚问题的难处。假设你在做一个网格寻路地图分成100×100的格子每个格子要么能走要么是墙。从这个起点到终点理论上的路径数量是个天文数字——每走一步有4个方向可选走50步的组合数量就已经超过10的30次方。你要是用广度优先搜索BFS或者深度优先搜索DFS这类盲目搜索本质上是在不看目标、均匀撒网BFS会一圈一圈地把所有能到的位置全部铺开直到某一圈刚好碰到终点。在地图小的时候没感觉地图一大、障碍物一复杂内存直接爆掉几十万个节点全部压进队列。启发式搜索的思路就一句话别傻走先看看哪个方向离目标更近。贪婪最佳优先搜索只认这个更近A*则是把更近和已经走了多远合起来算一笔账。这两者的差别决定了算法是跑得飞快但可能翻车还是稳扎稳打但一定最优。那什么人适合读这篇如果你已经在用Python写爬虫、写算法题、写工程脚本想在路径规划或者状态搜索上补齐一块知识这篇足够用。如果你完全是新手Python基础语法还不太熟问题也不大——我尽量把每个环节用生活化的例子讲开代码也写得能直接复制跑起来。2. 贪婪最佳优先搜索盯着目标跑得最快的那种2.1 核心思路与算法流程贪婪最佳优先搜索Greedy Best-First Search的逻辑特别朴素每一步都从待扩展的节点里挑一个离目标估计最近的节点把它展开。至于已经走了多少步、绕了多少弯它完全不关心。评价函数写出来就是f(n) h(n)这里的h(n)就是启发函数表示从节点n到目标的估计代价。在地图寻路里如果只能上下左右四个方向走最常用的就是曼哈顿距离横坐标差的绝对值加纵坐标差的绝对值。如果能走八个方向用切比雪夫距离取两个坐标差的较大值更合适如果能斜着走但斜走代价不是1欧氏距离更贴近真实代价。算法流程拆开看是这样几步把起点塞进一个优先队列优先级就是h(起点)。从队列里弹出h值最小的节点标记为已访问。如果这个节点就是目标回溯路径结束。否则把它所有没访问过的邻居加进队列邻居的优先级是h(邻居)。重复2到4直到队列为空说明无解或者找到目标。这里有个细节值得说队列里可能出现同一个位置的多个副本。因为贪婪算法不管g值某个邻居可能被不同路径重复加进去。工程上必须做个判重否则队列会越滚越大。最省事的办法是用一个closed集合记录已经展开过的节点弹出来发现是旧的就直接跳过。2.2 Python实现与优先队列的正确姿势Python标准库里的heapq是个小顶堆弹出来的永远是最小值。直接用它写贪婪最佳优先代码如下import heapq import itertools def manhattan(a, b): return abs(a[0] - b[0]) abs(a[1] - b[1]) def greedy_best_first(grid, start, goal): grid: 二维列表, 0表示可通行, 1表示障碍 start/goal: (行, 列) 元组 返回: (路径列表, 扩展节点数) 或 (None, 扩展节点数) rows, cols len(grid), len(grid[0]) counter itertools.count() # 用于打破优先级相同的比较僵局 open_heap [(manhattan(start, goal), next(counter), start)] came_from {start: None} closed set() expanded 0 while open_heap: _, _, current heapq.heappop(open_heap) if current in closed: continue closed.add(current) expanded 1 if current goal: path [] while current is not None: path.append(current) current came_from[current] return path[::-1], expanded r, c current for dr, dc in ((1, 0), (-1, 0), (0, 1), (0, -1)): nr, nc r dr, c dc if 0 nr rows and 0 nc cols and grid[nr][nc] 0: nxt (nr, nc) if nxt not in closed and nxt not in came_from: came_from[nxt] current heapq.heappush(open_heap, (manhattan(nxt, goal), next(counter), nxt)) return None, expanded注意heapq在比较元组时如果第一个元素相等就会去比第二个。如果第二个元素也是不可比的对象比如字典程序直接抛TypeError。所以我在堆里塞了个自增计数器counter作为第二元素第三位才放真正的节点。这是写A*和贪婪搜索时最常见的报错来源新手百分之八十会在这里卡住。2.3 贪婪为什么快又为什么靠不住贪婪最佳优先的优势很直观它每一步都朝着终点方向压扩展的节点数通常远少于BFS。在一张没有太多陷阱的地图上它跑出来的路径长度接近最优解速度快得让人舒服。我用一张40×40、随机撒了25%障碍的地图测过BFS平均要扩展七八百个节点贪婪通常百来个就收工了。但它的坑也很致命。假设地图上有一个大的凹形障碍终点正好在凹口里面。贪婪算法站在凹口左边看到右边的格子曼哈顿距离更小一头扎进去然后发现是死胡同退出来再扎进去——反复横跳。它没有走弯路是为了绕过障碍这个概念因为h(n)只看直线距离完全无视地形。我踩过一个更隐蔽的坑在某次做类Roguelike游戏寻路时贪婪算法在开阔区域表现极好但一旦地图里出现U形墙寻出来的路径会贴着墙绕一大圈长度是A的两倍多。玩家体验上就是NPC走路像智障。后来我把寻路换成了A问题直接消失。所以贪婪最佳优先适合什么场景一类是对实时性要求极高、路径质量可以妥协的场景比如游戏里远处的杂兵寻路或者博弈AI里快速评估某个分支是否有戏。另一类是把它当启发函数本身来用——A里的h就可以用一次贪婪搜索的代价来估计不过那就是另一套玩法了。工程上千万别拿它当唯一方案正确做法通常是把它当成快速试探的前置步骤用它剪枝再用A收尾。3. A*算法把代价和方向捏在一起的平衡术3.1 f g h 这个公式到底在说什么A*的评价函数是f(n) g(n) h(n)g(n)是从起点走到节点n已经花掉的真实代价h(n)是从n到目标的估计代价。把两者加起来得到的f(n)就可以理解为如果经过n走整条路大概要花多少。用个生活类比你在陌生的城市里找一家餐厅。g(n)是你从出发到现在已经走过的距离是实打实的h(n)是你抬头看一眼地图App估计现在的所在地离餐厅还有多远。A*做的事就是不停地问哪条候选路的已走预计剩余总和最小挑那条走。这一加性质完全变了。BFS只看g谁走得浅谁先出队贪婪只看h谁离目标近谁先出队A*两者兼顾所以它既能朝目标方向推进又不会为了抄近道而绕远。这是它能在保证最优解的同时大幅减少扩展节点的原因。3.2 可采纳性与一致性A*最优性的两块基石很多人用A*的时候只管跑不关心h到底该满足什么条件结果路径偶发不是最优排查半天。这里必须把两个概念说透。可采纳性admissible对所有节点nh(n) ≤ h*(n)其中h*(n)是n到目标的真实最小代价。人话就是你的估计永远不能高估。曼哈顿距离在四向网格里就满足这个条件因为再怎么绕直线距离永远是下界。一旦你高估了A*可能会提前觉得这条路不行把真正的最优解砍掉最后给出一个次优解。一致性consistent也叫单调性对任意边n→n满足h(n) ≤ cost(n, n) h(n)。直观理解是从n出发的估计不能比先走一步再估计还离谱。一致性比可采纳性更强满足一致性的h一定可采纳。它的工程价值在于如果h是一致的那么一个节点第一次被弹出时它的g值就是最优的可以直接丢进closed集合再也不管。否则你必须在发现更优路径时把节点从closed里捞出来重新入队代码会复杂一大截。我个人的经验是写A*优先选一致的启发函数。四向网格用曼哈顿八向用切比雪夫或对角距离这两个在单位代价下都是一致的省心。如果你自定义了一个h先手算几组数据验证一下一致性能省掉后续大量调试时间。3.3 完整的A*实现下面这份代码是网格寻路的A*加了g_score字典记录每个节点的最优代价堆里第二元素放g再加计数器的做法我做了简化直接用(f, counter, node)import heapq import itertools def astar(grid, start, goal): rows, cols len(grid), len(grid[0]) counter itertools.count() open_heap [(manhattan(start, goal), next(counter), start)] came_from {start: None} g_score {start: 0} closed set() expanded 0 while open_heap: f, _, current heapq.heappop(open_heap) if current in closed: continue closed.add(current) expanded 1 if current goal: path [] while current is not None: path.append(current) current came_from[current] return path[::-1], expanded r, c current for dr, dc in ((1, 0), (-1, 0), (0, 1), (0, -1)): nr, nc r dr, c dc if not (0 nr rows and 0 nc cols): continue if grid[nr][nc] 1: continue nxt (nr, nc) if nxt in closed: continue tentative_g g_score[current] 1 if tentative_g g_score.get(nxt, float(inf)): g_score[nxt] tentative_g came_from[nxt] current heapq.heappush(open_heap, (tentative_g manhattan(nxt, goal), next(counter), nxt)) return None, expanded跟贪婪那份代码对比一下差别就三处多维护了一个g_score入堆的优先级是g h而不是h允许同一个节点以更小的g再次入堆因为用了tentative_g g_score[nxt]这个判断。第三点很关键如果你写成if nxt not in came_from就等于强制每个节点只入队一次A*的最优性就丢了。3.4 权重A*用一点点最优性换速度实际项目里时间比最优更值钱这时候可以给h乘一个权重f(n) g(n) w * h(n), w 1w取1.2到2之间扩展节点数往往能降一大截路径只比最优长一点点。代价是你失去了可采纳性保证跑出来的路径不再保证最优。这种做法叫权重A*Weighted A*在游戏和机器人实时规划里用得很广。我的经验是地图越开阔、障碍越稀疏w可以给得越大地图越复杂、绕路越多w就别超过1.5否则路径会难看得明显。注意w不是拍脑袋定的建议在具体地图上跑一组对照画出扩展节点数-路径长度的曲线挑一个拐点位置。我做过一个仓储机器人的项目w1.3时扩展节点数掉了约40%路径只长了6%性价比很高。4. 实操两个完整案例跑通A*4.1 网格寻路从建模到可视化先搭一张测试地图。我用的是随机生成加固定种子保证每次实验可复现import random def build_grid(rows, cols, obstacle_ratio0.25, seed42): random.seed(seed) grid [[0] * cols for _ in range(rows)] for r in range(rows): for c in range(cols): if random.random() obstacle_ratio: grid[r][c] 1 return grid grid build_grid(40, 40, obstacle_ratio0.25) start, goal (0, 0), (39, 39) grid[start[0]][start[1]] 0 grid[goal[0]][goal[1]] 0 path, expanded astar(grid, start, goal) print(f路径长度: {len(path)}, 扩展节点数: {expanded})可视化用matplotlib十几行就能搞定把障碍画成黑格、路径画成红线import matplotlib.pyplot as plt import numpy as np def draw(grid, path, start, goal): arr np.array(grid, dtypefloat) fig, ax plt.subplots(figsize(7, 7)) ax.imshow(arr, cmapGreys, originupper) if path: ys [p[0] for p in path] xs [p[1] for p in path] ax.plot(xs, ys, r-, linewidth2) ax.plot(start[1], start[0], go, markersize8) # 起点绿点 ax.plot(goal[1], goal[0], bo, markersize8) # 终点蓝点 ax.set_xticks([]); ax.set_yticks([]) plt.tight_layout() plt.show() draw(grid, path, start, goal)跑完之后你会发现A*的路径明显贴着障碍边缘走看起来聪明而贪婪的路径往往是几条折线的拼接转弯多、不自然。这就是g值在起作用——它惩罚了绕远的动作。4.2 八数码问题换一个状态空间试试网格寻路是图搜索里最直观的一种但启发式搜索的威力在组合状态空间里才更明显。经典的八数码问题就是好例子3×3的格子里放1到8和一个空格每次把空格和相邻数字交换求从初始状态到目标状态的最少步数。状态空间大小是9! 362880BFS硬搜也能过但代价不小。启发函数怎么设计是关键这里给两个错位数Hamming统计有多少个数字不在目标位置上。这个h计算极快但估计偏松A*扩展的节点多。曼哈顿距离和每个数字从当前位置挪到目标位置需要的曼哈顿距离之和。这个h更紧扩展节点少得多代价是每个节点要多算几次坐标差。import heapq import itertools GOAL (1, 2, 3, 4, 5, 6, 7, 8, 0) def manhattan_h(state): total 0 for idx, v in enumerate(state): if v 0: continue tr, tc divmod(v - 1, 3) r, c divmod(idx, 3) total abs(r - tr) abs(c - tc) return total def hamming_h(state): return sum(1 for i, v in enumerate(state) if v ! 0 and v ! GOAL[i]) def neighbors(state): i state.index(0) r, c divmod(i, 3) for dr, dc in ((1, 0), (-1, 0), (0, 1), (0, -1)): nr, nc r dr, c dc if 0 nr 3 and 0 nc 3: j nr * 3 nc lst list(state) lst[i], lst[j] lst[j], lst[i] yield tuple(lst) def solve_8puzzle(start, h_func): counter itertools.count() open_heap [(h_func(start), next(counter), start)] came_from {start: None} g_score {start: 0} closed set() expanded 0 while open_heap: _, _, current heapq.heappop(open_heap) if current in closed: continue closed.add(current) expanded 1 if current GOAL: path [] while current is not None: path.append(current) current came_from[current] return path[::-1], expanded for nxt in neighbors(current): if nxt in closed: continue tg g_score[current] 1 if tg g_score.get(nxt, float(inf)): g_score[nxt] tg came_from[nxt] current heapq.heappush(open_heap, (tg h_func(nxt), next(counter), nxt)) return None, expanded拿一个稍难的初始状态测一下start (2, 8, 3, 1, 6, 4, 7, 0, 5) path_m, exp_m solve_8puzzle(start, manhattan_h) path_h, exp_h solve_8puzzle(start, hamming_h) print(f曼哈顿: 步数{len(path_m)-1}, 扩展{exp_m}) print(f错位数: 步数{len(path_h)-1}, 扩展{exp_h})我在本地跑出来的结果大致是这样两者步数一样都是最优解但扩展节点数差了将近一个数量级。这组数据很能说明问题启发函数越贴近真实剩余代价A*越省力。启发函数解的长度扩展节点数单节点h计算耗时错位数Hamming最优约 4000极快曼哈顿距离和最优约 500 左右稍慢曼哈顿 线性冲突最优约 200 左右更慢不使用启发Dijkstra最优数万无提示所谓线性冲突是八数码里的进阶技巧——如果同一行有两个数字目标也在同一行但顺序反了那它们至少要多绕两步。把这种冲突数加上去h会紧很多。它依然是可采纳的因为冲突确实无法避免。4.3 三个算法在同一张地图上的横向对比为了方便你直观感受我用同一张40×40地图、同一对起终点把BFS相当于h0的A*、贪婪最佳优先、A*跑一遍算法评价函数路径长度扩展节点数是否保证最优广度优先f g层级最短约 800是贪婪最佳优先f h偏长可能绕路约 120否A*曼哈顿f g h最短约 200是权重A*w1.5f g 1.5h略长约 90否这张表基本把三者关系讲清楚了贪婪最快但不保证最优A在最优前提下比BFS省了75%的扩展量权重A是速度和质量的滑杆。选哪个看你的场景对最优的容忍度。5. 常见问题与排查技巧实录5.1 踩坑速查表写A*和贪婪搜索的时候问题往往不是算法写错而是细节没抠到位。我把这些年踩过的坑整理成一张表现象大概率原因解决办法程序报TypeError: not supported堆里元组第二元素不可比加itertools.count()计数器路径不是最短h高估了破坏可采纳性检查h确保不超过真实代价搜索极慢、内存暴涨没去重同一节点反复入堆加closed集合出堆先判重路径断成好几截回溯时came_from没兜底起点映射置为None循环判None找不到解但明明有路起点或终点落在障碍上建图后强制把起终点置为可通行节点被重复扩展h不满足一致性改用一致的h或在更新时重开节点斜向移动路径穿墙没做对角线穿墙检测检查斜向两侧格子是否都是通路注意第7条在地图寻路里特别常见。允许八方向移动时如果两个障碍呈对角摆放而中间那个格子被当作通路路径就会从缝里钻过去视觉上像是穿墙。标准做法是只有当斜向相邻的两个正交邻居都可通行时才允许走对角线。5.2 性能优化的几个实用招数第一招用数组代替字典。网格寻路里g_score、came_from用字典存元组键速度快但内存开销大。如果地图尺寸固定直接用一维数组、index r * cols c能省下不少内存查找还更快。我做过一个百万格级别的地图字典版跑起来内存吃紧换数组之后顺畅得多。第二招复用容器。高频调用寻路比如游戏里每帧都在算时每次新建字典和堆是笔不小的开销。可以把这些容器提到外面做对象池清空之后复用避免频繁的内存分配和GC。第三招按需选择启发函数。不是越紧越好。曼哈顿 线性冲突很紧但每个节点要跑一遍冲突检测如果路径本来就很短算h的时间可能比省下来的扩展时间还多。我的经验是平均路径长度小于50时就用最朴素的曼哈顿长了再上增强版。第四招分块预处理。超大地图上可以做跳点搜索JPS提前把地图里必定不会出现在最优路径上的节点剔掉让扩展量再降一个量级。它不是替代A*而是在A*的邻居生成环节加规则属于进阶优化。5.3 启发函数设计的三条心得写久了会发现启发函数的设计比算法本身更考验经验。我总结三条始终保持可采纳性优先。只要你还需要最优解这个保证h就绝对不能高估。我曾经为了提速给一个绕路频繁的地图硬是用了欧氏距离相当于高估了斜向代价结果路径偶尔比最优长一两步排查了两天才定位到。宁可慢一点也别丢掉正确性。启发函数要贴合移动代价模型。四向单位代价用曼哈顿八向用切比雪夫任意角度用欧氏非均匀地形就得用加权版的距离。你用的距离度量跟实际能走的动作对不上h就会要么高估要么过松两头不讨好。能用两段式就别一步到位。所谓两段式是先用一次快速的贪婪搜索或粗粒度网格得到一个大致代价把它乘个系数当h用。这样得到的h通常比几何距离紧得多还天然满足可采纳性只要系数小于1。我在一个大地图导航项目里用这招扩展节点数比纯曼哈顿方案少了约六成。补充一个小技巧调试A*的时候把open_heap和closed的状态打印成地图不同颜色表示不同状态一眼就能看出算法是往哪扩展的。很多时候问题不在代码而在你看不见扩展范围。把它画出来是树没长对还是h方向反了立刻分明。