1. 先搞懂“搜索”在人工智能导论课里的位置这是人工智能导论课里“搜索”模块的第二节。如果你刚上完无信息搜索那节课头脑里对广度优先、深度优先还有一点印象但又被八数码、迷宫寻路这一类问题搞得有点乱那这次要讲的“启发式搜索”就是给你之前那套盲目探索的算法装上“方向感”。一句话定义启发式搜索 在状态空间里找目标时用一个“估计函数”给每个待探索的节点打一个分然后优先展开分数更好的节点。这个“估计函数”就是启发式heuristic通常写作 h(n)表示“从当前节点 n 到目标状态还需要的最小代价的估算值”。这节内容能帮你解决什么问题最典型的就是网格迷宫找最短路径、八数码/十五数码还原、游戏里角色从 A 点到 B 点绕开障碍物这类场景。和广度优先、深度优先这些无差别遍历不同启发式搜索可以在每个节点上做“优先级排序”用更少的展开节点数找到目标。这门课适合谁说实话如果你只是跟着课程进度走这部分不需要额外准备什么数学基础。会写基本的树/图遍历能理解“代价”这个概念就能跟得上。如果你是自学或者补基础我建议先把广度优先和深度优先的代码敲一遍再来看这一节不然“优先级队列”“闭集”这些词容易飘。先说一个我自己当初踩过的坑上这门课时我花了很长时间在纠结“启发式到底是不是绝对正确的预测”。后来才明白启发式从来不需要准确它只需要“别低估太多”。它就像一个经验丰富的向导——不会确切告诉你到终点还有几步但至少不会把你带到明显离谱的方向。2. 搜索建模是地基状态、动作、代价、目标判定很多初学者一上来就写 A* 搜索然后在某个循环里转不出来最后发现是“状态表示”从一开始就有问题。这一小节必须讲因为它决定了后面所有代码怎么组织。在启发式搜索里你面对的本质是一个状态空间图。四个基本元素状态state描述当前“局面”的最小信息集合。八数码里的一个状态就是 3x3 棋盘上所有数字的排列迷宫问题里就是机器人所在坐标。动作action从一个状态到另一个状态的合法转移方式。迷宫是上下左右移动八数码是空格向四周某个位置移动。转移代价cost执行该动作的开销。迷宫通常四个方向都是 1但如果你在带权地形图里走路穿过草地的代价可能是 2走平路的代价是 1。目标判定goal test判断某个状态是否达到终点。我辅导过不少同学处理一个模拟项目大致是“外卖机器人在网格中从起点走到取餐柜”。如果状态只存坐标 (x, y)动作就是四个方向那一切都清晰但如果有人试图在状态里塞进完整路径历史代码立刻变得冗余又难查。还有一点容易忽略状态的“唯一键”问题。写代码时通常用元组或字符串当字典键。八数码把 3x3 棋盘压成 9 个字符的长字符串迷宫直接用 (x, y) 元组。如果数据结构混用有的地方用 list 有的地方用 tuplePython 里 list 不能做字典键一执行就报错或者更严重——不报错但逻辑错误。实操建议正式写搜索算法之前先单独写一个“状态转换函数”的单元测试。给你一个起始状态调用一次动作生成器把下一步状态打印出来人眼核对一遍是否符合物理规则。这一步做扎实后面所有 debug 时间都能省回来。3. 两种经典启发式曼哈顿距离与欧氏距离启发式函数是这节内容的灵魂。导论课里最常出现在作业和考试中的是两个网格类启发式曼哈顿距离和欧氏距离。解释概念时直接看公式曼哈顿距离Manhattan Distance / 城市街区距离h(n) |x1 - x2| |y1 - y2|它表达的是在只能横平竖直移动的世界里你必然至少要走这么多步。举例起点 (0, 0)终点 (2, 2)曼哈顿距离 4。在四方向网格里哪怕障碍物再多实际怎么绕也不可能少于 4因为横向至少需要 2 步纵向至少需要 2 步。这个性质就是可采纳性。欧氏距离Euclidean Distanceh(n) sqrt((x1 - x2)^2 (y1 - y2)^2)在允许斜向移动的网格中欧氏距离更贴合真实最短距离但在只能上下左右移动的网格中欧氏距离往往小于曼哈顿距离因此它提供的信息量更弱——搜出来的节点数通常更多。为什么说“信息量”是衡量启发式质量的关键因为对同一个可采纳的 h 来说估值越接近真实剩余代价 h*搜索的剪枝效率就越高。曼哈顿距离在四方向网格里就是信息性很强的启发式错误位置计数数一数有几个数字不在目标位虽然也可采纳但信息量明显不如曼哈顿距离所以它做出来的 A* 展开节点数往往多个数量级。这里顺便说下我在作业中发现的一个经验单纯比较两个启发式哪个好直接对比“展开节点数”是直观且有效的。统计方法在后面的章节里会详细展开但先记住结论曼哈顿距离总和 错误位置个数 的信息强度在八数码这种棋盘类问题上基本总是赢。注意启发式的计算成本也要算在总运行时间里。如果 h(n) 本身要启动一个小搜索去求精确解那每展开一个节点都等于做了一次子搜索开销会非常恐怖。课程作业里比较启发式标准口径应该统计“展开节点数量”而不是只看墙钟时间。4. 贪心最佳优先搜索先感受方向感但别急着用它贪心最佳优先搜索Greedy Best-First Search的思路说实话特别像人类找路时的本能每次从开放表里挑离目标“看起来最近”的节点展开。这里的“看起来最近”完全由 h(n) 决定不参考已走路径的实际花费。它的优点是结构简单、速度快、内存占用也不大在单纯“找个可行路径”的任务中可能比后面要说的 A* 快一个数量级。对实时性要求高但允许非最优解的场合它仍然有价值。但它存在一个深刻的缺陷不保证最优。原因是它没有累计代价 g(n) 的约束。一个经典的欺骗场景我给学生演示过很多次一条路上有个很长的死胡同死胡同里的某些位置距离目标点的曼哈顿距离甚至比正确岔路口更小。贪心搜索会被这个虚假的“靠近目标”骗进死胡同里直到走到尽头才发现没路再折返回来。这个绕弯过程会让路径明显变长。再精确一点说贪心优先甚至不能保证终止时一定能给出较优路径它只保证能找到一条如果存在可行路。当 h(n) 本身较差时它可能深陷局部区域。这段的结论就是一个过渡既然贪心只看 h 容易短路那我们把 g(n) 也加入打分模型就形成了搜索的升级版——A*。这一步在逻辑上非常自然也是课程安排里后面的必然衔接。5. A* 搜索的核心原理g h精确账本加乐观估计A* 是启发式搜索里最重要的算法没有之一。它把节点排序的优先级定义成一个简单的相加f(n) g(n) h(n)g(n)从起点到当前节点 n 的已经花掉的真实代价。这一步是可追踪的、精确的因为它来自每条走过边的代价值相加。h(n)从当前节点到目标剩余代价的估计这是启发式的角色。f(n)决定了这个节点在开放表里的紧急程度。把两个数字放在同一个天平上意义很大g 是“你为了到这一步已经付出了多少”h 是“你觉得还要再付出多少”。两个分支如果剩余估计相同已经花得更少的那个胜出如果一条路线已经把代价耗高哪怕 h 再小f 也未必占优。用一句话总结贪心负责指方向账本负责纠弯路。A* 的完整运行逻辑可以用伪代码表达这里给一份贴近课程实现、可以直接改写成作业代码的版本import heapq def astar_search(start, goal_test, successors, heuristic): # open 表优先队列元素为 (f值, 计数器, 状态) open_heap [] counter 0 heapq.heappush(open_heap, (heuristic(start), counter, start)) came_from {} # 记录最短路径中每个节点的前驱 cost_so_far {} # 记录每个状态目前已知最小 g 值 came_from[start] None cost_so_far[start] 0 while open_heap: f_current, _, current heapq.heappop(open_heap) if goal_test(current): return reconstruct_path(came_from, current) for next_state, step_cost in successors(current): new_cost cost_so_far[current] step_cost if next_state not in cost_so_far or new_cost cost_so_far[next_state]: cost_so_far[next_state] new_cost priority new_cost heuristic(next_state) counter 1 heapq.heappush(open_heap, (priority, counter, next_state)) came_from[next_state] current return None # 没找到路径 def reconstruct_path(came_from, current): path [current] while came_from[current] is not None: current came_from[current] path.append(current) path.reverse() return path这份伪代码有几个关键设计必须说清楚第一open 表里除了状态还放了一个计数器。这是因为两个不同状态的 f 值可能完全相同Python 的 heapq 比较元组时会进一步比较第二个元素。如果不加计数器它可能会去比较状态本身那可能引发类型错误或错误排序。第二cost_so_far 字典存储“当前已发现的最优 g(n)”。每次生成后继状态时如果发现了更短路径new_cost cost_so_far[next]就更新记录并重新入堆。这种操作称为“节点松弛”允许同一个状态被多次压入堆中但只有在它真的拿到更优 g 值时才会发生。第三也是我当年自己踩过的大坑目标判定必须发生在“从堆中弹出该节点”时而不是在“生成该节点”时。很多人图省事在某个后继状态是目标时立刻返回路径结果可能在第一步就把起点当目标返回了或者返回一条非最优路径。正确做法是当从堆中弹出该节点且它满足目标判定条件时才终止程序。再说说为什么 A* 在可采纳启发式下能找到最优解。核心论证是如果存在一条到目标的最优路径 P*它的真实总代价是 C*。在搜索过程中任何位于这条最优路径上的未展开节点 n都满足 f(n) ≤ C*。因为 g(n) 是沿最优路径到达 n 的真实代价它不会超过最优代价的前缀部分而 h(n) 可采纳意味着 h(n) ≤ 剩余真实代价。既然 open 表每次弹出的都是全局 f 最小的节点且目标节点只有当它的 f 值等于 C* 时才会被弹出那么最优路径上的节点必然先于所有非最优目标被展开。这里有个容易绕晕的点h(n) 可采纳只要求它“不低于真实代价”。如果你不小心设计了一个高估的启发式A* 就可能在非最优路径上“自作聪明”地跳过一些更优分支最终返回一条绕路的路径。这一点在后面的注意事项目录里要反复强调。6. 可采纳性、一致性与信息性启发式品质的三层评价标准课程作业里通常还会涉及一个话题怎么判断一个启发式是“合格”的、以及合格里面哪个更“强”。有三个标准需要分开记忆。6.1 可采纳性Admissibilityh(n) ≤ h*(n) 对所有非目标状态成立其中 h*(n) 是从 n 到目标的真实最小代价。这个条件保证了 A* 的最优性。简单理解就是启发式永远不要“过于乐观”——且听清楚这里及物动词的方向是“不能对剩余代价高估”即不能低估了完成任务的困难程度。如果 h(n) 总是很小、甚至恒为 0它依然可采纳但信息性极差搜索退化成了 Dijkstra 算法。如果你设计一个“剩余步数乘以 3”的启发式那它可能高估了真实代价于是不满足可采纳性最优性直接崩塌。6.2 一致性Consistency / Monotonicity一致性是更强的条件。对任意状态 n 和它的后继状态 n都必须满足h(n) ≤ cost(n, n) h(n)同时 h(goal) 0。直观含义是从 n 移动到 n 所花的代价加上 n 的启发式估计不会比 n 原来的启发式估计更少。也就是说启发值沿搜索路径“不会突然反弹上涨”。一致性成立时对任意扩展后的节点f(n) 单调不减。为什么一致性重要因为一旦 f 值单调不减每个状态在 closed 表里的 g 值一旦确定就不再需要被更新不必反复把旧节点重新压回堆中实现更简单、效率更稳定。曼哈顿距离在普通四方向网格图中天然满足一致性因为 h 值变化最大就等于移动一步的代价 1。6.3 信息性Informativeness信息性讨论的是两个可采纳启发式的相对强弱。如果对任意状态 n 都有 h1(n) ≤ h2(n) ≤ h*(n)就说 h2 比 h1 信息性强h2 dominates h1。信息性强意味着 f 值的区分度更大优先队列里被展开的“偏路”节点更少。代价是计算 h2 可能需要更多时间。所以真正工程上选哪种启发式是在“剪枝效率”和“单节点计算开支”之间做的权衡没有绝对正确只有具体地图具体分析。实操心得做作业里启发式对比实验时建议把 h 设为 0 跑一遍作为一个 reference——那本质上就是 Dijkstra。然后分别统计“曼哈顿”和“错误位置计数”两个版本展开的节点数量。如果某个启发式展开的节点数反而比 Dijkstra 更多那通常是实现出的 h 值写错了把“估计值”算成了“实际距离”以外的什么东西。7. 封闭表与重复态处理最容易出 bug 的逻辑区A* 实现中有个地方特别容易“想当然”closed 表到底存什么已经弹出过的节点还要不要再看最简单可靠的实现其实不用单独维护封闭集合。用法是靠 cost_so_far 字典实现“自动拦截”。具体逻辑可以这样分析如果某个状态从未出现new_cost 一定小于初始无穷大入堆。如果某个状态已经出现过但当前路径更短则它会被更新入堆。如果某个状态出现过且已有 g 值比新路径更短或相等则忽略这个后继。这种方式天然处理了“重复态”状态未必只入堆一次但每次重复入堆都意味着发现了一条更优到达路径。只要启发式满足一致性这种重复量可控不会造成指数级爆炸。但如果你真的单独写一个 closed_set种下了一个经典的 bug 隐患当节点重新以更优 g 值被发现时你却因为它已经在 closed_set 里而跳过更新最终路径可能与最优解相差巨大。不少作业平台里报错“路径长度比最小长度多 2”十有八九是这个原因。所以我的建议很直接初学阶段别维护 closed_set只维护 cost_so_far 加上“如果新代价不小于已有代价就跳过”的判断。这段逻辑逻辑简单且不易错。后续进阶时可以再讨论通过闭集合配合一致性优化性能的方案。8. 加权 A*、IDA* 与双向 A*真实项目中更常见的变体A* 虽然很漂亮但面临大图时仍然可能崩溃——内存占满、时间过长。课程不一定深入讲但面试和真实项目里会频繁遇到下面的变形。加权 A*Weighted A*把优先级改成 f g w·h其中 w 1。当 w 增大搜索更偏向“快速逼近目标”节点数往往明显下降但代价是牺牲最优性。实测下来 w 1.5 在游戏寻路里是一个常用起点——路径质量损失小搜索速度常常能提升到原来的好几倍。如果业务只要求“差不多就行”从 1.5 试起是稳妥的选择。IDA*Iterative Deepening A*用深度优先搜索的栈结构替代优先队列每轮递归深度限制不是树深而是 f 值上限。每轮结束如果没找到目标就把 f 上限提升为这一轮中出现过的最小超限值重头再来。这样内存可以控制在 O(深度) 级别适合 15 数码这类 A* 内存爆炸的场景。缺点是同一个状态会被反复扩展多次地图较大时总计算量可能更大。双向 A*同时在起点和目标两边发起搜索两棵前沿树逐步靠拢接上即成功。它惯常能把搜索范围缩小两个数量级但实现起来要注意两边各自的启发式计算方向不同、终止条件复杂教学阶段如果时间紧不建议作为首选挑战。如果你只是想交作业或应付考试先精通标准 A* 就够了这些变体属于加深印象、开阔视野的选学内容。9. 实战操作从地图文件到一次可跑通的完整实验这一节给一个“照着做就能跑通”的实验脉络。假设你已经有一张字符地图例如用 . 表示空地、# 表示墙、S 表示起点、G 表示终点。目标是最短路径。第一步解析地图。把文本读入二维数组遍历每个格子记录起始坐标 (sx, sy) 和目标坐标 (gx, gy)同时把墙的位置存入一个 set供后继生成函数直接判断。def parse_map(text): grid [] start goal None for row, line in enumerate(text.strip().splitlines()): line_clean list(line.strip()) grid.append(line_clean) for col, ch in enumerate(line_clean): if ch S: start (row, col) elif ch G: goal (row, col) return grid, start, goal第二步写后继生成器。标准四方向移动返回 (新坐标, 步代价)。步代价默认 1若你的地图有特殊地形可在这里根据格子内容做加权。def successors(pos, grid): rows, cols len(grid), len(grid[0]) r, c pos 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] ! #: yield (nr, nc), 1第三步写两个启发式函数方便后面比节点数。def manhattan(pos, goal): return abs(pos[0] - goal[0]) abs(pos[1] - goal[1]) def euclidean(pos, goal): return ((pos[0] - goal[0])**2 (pos[1] - goal[1])**2) ** 0.5第四步把第 5 节的通用 A* 接上。跑通后最有效的验证方式是打印一条路径——比如把路径上的格子改为 然后在控制台把地图整个 print 出来。盯着路径看一遍确认避免绕路、没有穿墙、起终点正确。第五步比较统计量。在 A* 主循环里加两个计数器expanded_count每从堆中弹出并准备处理的节点加 1。generated_count每生成一个后继并可能压入堆中时加 1。在固定地图上跑曼哈顿与欧氏距离两个版本统计这两个指标。通常曼哈顿的 expanded_count 明显更小因为它在四方向网格里信息性更强。这一整套流程跑下来你其实已经把“用启发式搜索解决一个实际搜索问题”所需的全部环节都过了一遍。之后的挑战项比如加权 A*、双向 A*只需要改 priority 计算或在主循环里加上另一棵树都可以在此框架上直接迭代。10. 常见错误与排查技巧从“死循环”到“路径不对”的完整速查这一节是我面对学生作业和实际项目总结出来的排查清单按症状分类直接背下来能省不少时间。症状可能原因排查思路程序运行极慢或死循环状态 key 设计混乱list 当字典键或启发式不满足一致性导致节点反复入堆用元组或字符串先把 h 换成 0 跑 Dijkstra若能迅速结束说明问题在启发式返回路径明显绕路h 被高估了不可采纳打印每个节点的 f、g、h检查 h 是否可能大于真实剩余代价找不到目标目标判定写错或者 start 已满足目标但你在入堆时就把 start 判定为目标在主循环里加一个 print确认弹出的节点坐标是否符合预期路径比预期的 BFS 还长终止过早在“生成后继”时直接返回修正为“从堆中弹出并判定通过”才返回节点数量指数爆炸h 信息性太差或者 g 的更新逻辑写错导致反复压入先对比 h0 版本再检查 cost_so_far 更新条件权重 A* 路径差到不可接受w 过大尝试 w1.1 或 1.2逐档调优再说几条经验上很有价值的建议调试时不要只打印最终结果。每次从堆里弹出节点时输出 (f, g, h, 坐标)小地图上人眼扫一遍基本能定位问题。它直观、可靠比写一堆测试断言还快。对比启发式实验时保持两台算法的终止条件一致。这是很容易被忽略的口径问题。如果 A* 版本一入队目标就返回而另一个版本弹出目标时才返回节点数必然差得离谱但这不能说明启发式的优劣。大图测试前先做小图跑通。50x50 的地图对于 Python 调试已经足够确认逻辑没问题后再放大到 500x500否则中途出现 bug 时连打印输出都看不清 —— 这句话不知道少浪费我多少时间。11. 优先队列的口径问题为什么 heapq 里要加计数器再深度挖掘一个看起来很微小但实际影响很大的细节优先队列中的“同级元素排序”。Python 的 heapq 比较元组时从左到右逐项比较。如果你直接 push 一个 (priority, state) 元组而两个不同状态恰好 priority 相同heapq 会继续比较 state。如果 state 是两个整数组成的元组那么比较不会报错程序能跑但结果取决于坐标大小而不是“先入先出”或某种稳定顺序。更麻烦的是如果 state 是不可比较的对象比如自定义 Node 类没实现lt直接抛 TypeError。解决办法就是在优先级元组里插入一个单调递增的计数器heapq.heappush(heap, (priority, counter, state))。这样即使 priority 完全相等也能保证稳定弹出“先压入”的节点。不要小看这个细节我在不少同学的代码里看到过因为缺这个计数器而出现诡异的不稳定路径。这种稳定耗时很长但对结果毫无影响的细节恰恰是让一个搜索实验“可复现”的前提。如果你要在作业里统计节点数并且对同一个地图跑多次没有计数器时可能每次的路径长度一致但展开的节点顺序不同统计结果便带有随机偏差。加上计数器输出完全可复现实验结果更可信。12. 一个关键心法启发式设计是一门“领域知识编码课”最后想聊聊超出算法本身的东西。学完启发式搜索之后我最大的体会是它锻炼的其实是一种能力——把你对某个领域已有的理解转化成一张有代价的“质量函数”。迷宫里的曼哈顿距离是领域知识八数码中的曼哈顿距离总和也是领域知识物流调度里的行驶时间预测同样是领域知识。启发式算法的通用框架本身很简单难的是你面对的每一种新问题得找到那条“不会高估、又足够紧”的边界。这种能力会在课程后续的其他地方反复出现。比如学对抗搜索时一个局面打分函数本质上就是一种“从当前状态到胜负的启发式估计”学强化学习时价值函数估计的也是“从当前状态到最终回报的期望”学约束满足问题时MRV 启发式本质上也是在为下一步选择提供排序依据。所以我对这门课后半段的建议是别停留在看懂和交作业。给自己留一周随便找一个新环境——单词接龙、仓库拣货、甚至拼图 APP——自己设计状态、动作、代价和启发式跑一遍两个对比实验。这样做完后你对“搜索”的理解会从“背了一段伪代码”变成“真正会用”。这门课打完基础之后后面很大一部分内容都是在同一套思想上继续叠加把更大的未知空间砍小再砍小直到能在这砍出来的小空间里做精确决策。能过了启发式搜索这关后面的路会顺很多。