简介人工智能搜索技术是AI问题求解过程的核心本PDF资源系统梳理了搜索技术的关键知识点适合正在学习人工智能算法、准备考研复试或进行项目开发的技术人员参考。内容从搜索技术概述切入明确问题求解即状态空间中的搜索过程随后详解状态图建模方法通过农夫过河等经典案例展示状态向量与合法操作变换在盲目搜索部分对比了宽度优先与深度优先策略的适用场景启发式搜索及A算法、A*算法则重点讲解估价函数f(n)g(n)h(n)的设计思路最后深入博弈搜索中的极小极大法与α-β剪枝法展示如何通过阈值剪枝大幅降低搜索空间。资源共1个PDF文件大小6.54MB篇幅紧凑但结构清晰图文与状态图示例相结合便于按章节自学或作为课程讲义补充。已有498人学习下载适合希望通过实例快速理解搜索策略、掌握状态空间表示与剪枝优化的读者。1. 人工智能搜索技术先分清“搜索”和“查找”很多人第一次接触人工智能搜索技术以为它是类似数据库里那种“输入关键字、返回结果”的查找。实际完全两回事搜索技术解决的是在状态空间里找到一条从初始状态到目标状态的动作序列核心不是“查”而是“试”和“比较”。学这块内容最快的路线是先会用状态空间把问题描述清楚再依次掌握盲目搜索、启发式搜索最后把 A* 算法作为主线跑通几个典型场景。这篇笔记就按这个顺序展开适合正在学人工智能导论课程、或者要做迷宫寻路类大作业的读者看完能直接照着实现也能知道参数调歪了到底哪里出错。2. 状态空间建模把问题变成一张“可搜索的图”2.1 状态、动作、代价在写任何搜索算法之前第一步不是打开编辑器写代码而是把问题抽象成三个要素状态state问题世界中的一个完整描述。迷宫里的一个格子坐标是状态八数码里的一个棋盘排列也是状态。动作action从一个状态到另一个状态的合法转移。迷宫里通常是上下左右四个方向。代价cost执行动作付出的开销。可以是步数、时间、油耗。这三个要素合起来就是状态空间图。搜索算法本质上是在这张图上游走盲目搜索完全不看方向启发式搜索则借助估价函数猜哪个方向更接近目标。我一般会先做一件看起来很笨的事把状态、动作、代价用结构体或类写出来即使用不上太多继承关系也会把动作函数抽象出来。原因很简单——后面换算法时只有状态转移接口固定住了BFS、DFS、A* 才能共用同一套图描述。2.2 以迷宫为例子四邻域建模的代码实现四邻域迷宫是搜索入门最常见的载体。假设迷宫是一个二维字符数组0表示可以走1表示墙壁入口在左上角出口在右下角移动代价固定为 1。from collections import deque class MazeState: def __init__(self, x, y): self.x x self.y y def __eq__(self, other): return self.x other.x and self.y other.y def __hash__(self): return hash((self.x, self.y)) def __repr__(self): return f({self.x}, {self.y}) def get_neighbors(state, maze): 返回当前状态的所有合法邻居状态按上下左右的顺序 rows, cols len(maze), len(maze[0]) neighbors [] for dx, dy in [(-1, 0), (1, 0), (0, -1), (0, 1)]: nx, ny state.x dx, state.y dy if 0 nx rows and 0 ny cols and maze[nx][ny] 0: neighbors.append(MazeState(nx, ny)) return neighbors这段代码里有两个细节值得注意。__hash__必须和__eq__一起定义否则把状态放进集合或者作为字典键时会出现“明明内容相同却当成两个对象”的情况get_neighbors的边界判断先做坐标越界检查再做墙壁检查顺序不能反过来因为maze[nx][ny]在下标越界时会直接抛异常。块的逻辑就这么简单。真正的坑在于后面的算法实现往往会改坏这个接口比如忘记把起点放在已访问集合里或者生成邻居时没有过滤掉父状态。接口保持稳定后面换算法时才不会越换越乱。2.3 为什么要先建图再谈算法很多人在学搜索技术时习惯直接背 A* 的代码最后写出来的程序其实是按照“地图上有一条直路”这个假设写的换个地图就翻车。先把状态空间拆清楚本质上就是逼自己想明白“搜索是在什么图上进行的”。状态空间图有几个关键属性直接决定算法选型有限还是无限。无限状态空间必须用能保证终止的算法。有向还是无向。迷宫里的移动无向拼图类问题的箭头可能不可逆。单步代价是否一致。全部为 1 时 BFS 就有最优性代价不同就该上 Dijkstra 或 A*。这些属性在一张图上同时存在比如寻路时单位步长一致但地形有沼泽时移动代价不同。这些后续需要计算性能都会回到状态空间的建模是否准确。3. 盲目搜索先会用“蛮力”再谈效率3.1 BFS 与 DFS 的代码对照盲目搜索里最常用的是宽度优先搜索BFS和深度优先搜索DFS两者只差一个“接下来先扩展谁”的策略。BFS 用队列先进先出DFS 用栈后进先出。对照代码最能看清差别def bfs_search(start, goal, maze): BFS用队列逐层扩张找最短路径 frontier deque([start]) came_from {start: None} while frontier: current frontier.popleft() if current goal: return reconstruct_path(came_from, start, goal) for next_state in get_neighbors(current, maze): if next_state not in came_from: frontier.append(next_state) came_from[next_state] current return None def dfs_search(start, goal, maze): DFS用栈一头扎到底不保证最短 frontier [start] came_from {start: None} while frontier: current frontier.pop() if current goal: return reconstruct_path(came_from, start, goal) for next_state in get_neighbors(current, maze): if next_state not in came_from: frontier.append(next_state) came_from[next_state] current return None两份代码的结构完全一样唯一的区别是popleft()和pop()。前者从队头取保证先扩展先入队的层后者从栈顶取一路往深走。关键都在came_from字典它记录了每个状态“从哪来”最后从终点倒着逆向还原路径。这里容易出现的认知偏差是以为 DFS 代码和 BFS 只是改一行跑起来没区别。实际上 DFS 在深迷宫里有栈溢出的风险而且第一次到达终点时的路径不保证最短。盲目搜索是这样一种思想除了“不要走回头路”之外不做任何方向判断。3.2 迭代加深与代价一致搜索BFS 最优但有空间问题DFS 省内存但不保证最优。两者的折中是迭代加深深度优先搜索限制搜索深度从 1 开始逐次增加每次都从头跑 DFS。深度限制以内的 DFS 会完整探索该深度层因此首次找到目标时一定是最短步数。迭代加深的代码并不复杂核心在循环里逐层增加深度上限。def id_dfs_search(start, goal, maze, max_depth100): for depth in range(max_depth): result dfs_with_limit(start, goal, maze, depth) if result is not None: return result return None def dfs_with_limit(state, goal, maze, limit, came_fromNone): if came_from is None: came_from {state: None} if state goal: return reconstruct_path(came_from, state) if limit 0: return None for next_state in get_neighbors(state, maze): if next_state not in came_from: came_from[next_state] state result dfs_with_limit(next_state, goal, maze, limit - 1, came_from) if result is not None: return result del came_from[next_state] # 关键回溯时删除记录防止污染其他分支 return Nonedel came_from[next_state]是这段代码的灵魂。没删的话一条分支探索过的节点会阻塞另一条分支的访问导致漏解。迭代加深看起来重复执行了大量冗余扩展但大多数地图上时间开销依然可以接受空间开销只有 O(深度) 的递归栈实用性很强。如果每一步代价不相同BFS 的最优性就失效了需要换成 Dijkstra 算法。Dijkstra 用优先队列按累计代价扩展首次到达终点的路径就是最小代价路径。盲目搜索到这里已经接近天花板剩下的事要靠启发信息来加速。3.3 盲目搜索的适用边界盲目搜索并不是一种“应该被淘汰”的方法。地图规模小、分支少、步数少时BFS 的实现简单、行为可预期错误率远低于启发式搜索。很多大作业场景里地图是固定的几十乘几十BFS 在几十毫秒内就能解决根本没必要上 A*。但搜索空间一旦变大就完全不行。一个 20x20 的开放网格四邻域状态下状态数是 400最长路径可能上百步分支因子按 4 算盲目搜索在最坏情况下会扩展接近全部状态。而 15 数码这类状态空间有万亿级别的排列数盲目搜索直接不可用。算法数据结构最优性空间复杂度适用场景BFS队列步数最短等代价图O(b^d)小地图、等代价DFS栈不保证O(d)大空间找任意解迭代加深递归栈步数最短等代价图O(d)折中方案Dijkstra优先队列总代价最小O(b^d)不等代价图盲目搜索的结论是不要指望一种搜索方法通吃所有场景。盲目搜索的价值是给启发式搜索提供对比基线只有当你能说出“BFS 在这里扩展了多少节点、A* 在这里扩展了多少节点”时才能真正体会启发函数的意义。4. 启发式搜索与 A* 算法从“会找到解”到“找到好解”4.1 启发函数为什么有用盲目搜索不知道目标在哪只能按固定顺序扩展。启发式搜索的思路是给当前节点打分优先扩展“看起来更接近目标”的节点。这个“看起来”就是用启发函数h(n)计算出来的估价值。迷宫里的曼哈顿距离是一个最直观的启发函数h(n) |x_n - x_goal| |y_n - y_goal|它计算当前格子到终点在网格上横向加纵向的格子数。注意曼哈顿距离不考虑墙壁阻挡因此它不会高估真实代价。启发函数不高估真实代价称为“可采纳的”这是启发式搜索保证最优性的前提。4.2 A 算法与 A* 算法的区别很多教材把 A 算法和 A* 算法放在相邻小节里讲初学者容易混为一谈。两者的关系很简单A 算法指“使用估价函数 f(n) g(n) h(n) 的通用搜索框架”其中 g(n) 是从起点到当前节点的实际代价A* 算法是 A 算法在 h(n) 可采纳且一致时的一个特例这时候能找到全局最优解。换句话说只要用了 f g h 的搜索方式都可以叫 A 算法。但只有当启发函数满足可采纳性不会高估真实代价时才有资格叫 A*。这个区别直接对应一个工程问题有人把启发函数写成了“非法高估”的形式比如迷宫里的欧氏距离乘以 1.2结果跑得很快但路径明显绕远。这时程序跑出来的东西严格说只是 A 算法的结果不是 A* 的。4.3 A* 算法的 Python 实现与参数说明给出一份可以抄作业的 A* 实现处理迷宫最短路径。import heapq def a_star_search(start, goal, maze, heuristicNone): A* 搜索返回从 start 到 goal 的最短路径状态列表 if heuristic is None: # 默认曼哈顿距离只适合四邻域移动代价为1的地图 heuristic lambda a, b: abs(a.x - b.x) abs(a.y - b.y) open_heap [] # 堆里存 (f, g, counter, state)counter 避免 f 相同时比较状态对象 counter 0 heapq.heappush(open_heap, (heuristic(start, goal), 0, counter, start)) came_from {start: None} g_score {start: 0} while open_heap: _, current_g, _, current heapq.heappop(open_heap) if current goal: return reconstruct_path(came_from, start, goal) for next_state in get_neighbors(current, maze): tentative_g current_g 1 # 迷宫单步代价固定为1 if tentative_g g_score.get(next_state, float(inf)): came_from[next_state] current g_score[next_state] tentative_g f tentative_g heuristic(next_state, goal) counter 1 heapq.heappush(open_heap, (f, tentative_g, counter, next_state)) return None代码里三个参数最要命逐个展开说。open_heap里存的是四元组(f, g, counter, state)。只存(f, g, state)的话堆比较时 f 相同比 gg 也相同就可能去比较 state 对象而MazeState没有定义__lt__直接报TypeError。加一个递增的counter就是为了打破平局保证比较永远能分出先后。第二个关键是tentative_g g_score.get(...)这个判断。它并不检查 next_state 是否已经在闭集合或堆里而是看“这条路径的 g 值是否比已知的更小”。更小就更新并重新入堆。这就是 A* 处理重复状态的方式简单且正确。第三个容易被忽略的点是堆里弹出的节点可能不是最新 g 值对应的节点。代码中弹出的current_g直接用于计算下一步的代价所以入堆时必须保证 g 值是当时计算出的准确值。上面代码里采用了“每次更新都重新评估所有邻居”的策略用current_g而不是g_score[current]正是为了处理这一情况。参数方面heuristic可以替换为任何满足条件的函数。换成欧氏距离也能跑但最优性要重新验证换成更大的值如h * 1.5跑得过快但路径不是最优。4.4 启发函数选择与一致性条件在工程里选启发函数时有两个层面的要求要区分开可采纳性保证最优但光可采纳还不够快一致性或称单调性让每个节点第一次被扩展时 g 值就已经最优避免不必要的重复扩展。一致性的定义是对任意状态 n 及其后继 n满足h(n) cost(n, n) h(n)这有点像三角不等式。满足一致性时A* 的行为更高效不需要维护复杂的重新打开逻辑。曼哈顿距离在四邻域等代价图上满足一致性所以上面实现对每个状态最多只会重新入堆有限次。如果地图带权重、对角线移动成本不同曼哈顿距离的一致性会被打破。这时常见的做法是改用“对角线距离”或“八方向切比雪夫距离”同时把移动代价设成对应的代价函数。启发函数必须和动作代价配套否则一致性失效A* 的路径可能悄悄变差。实战建议先用一个 10x10 的无障碍地图手动算一遍 A* 的 f、g、h 值确认代码输出的扩展顺序和自己的手算一致再换复杂地图。5. 避坑A* 搜索的经典常见问题与排查5.1 启发函数高估导致结果不是最优现象算法能很快跑完输出路径看起来也合理但手工数一下步数发现比实际最短路径多出几步。原因启发函数出现了高估破坏了 A* 的可采纳性。常见高估场景是用了欧氏距离却让移动代价为 1、横向纵向步进欧氏距离在纯网格里往往小于真实距离这不会高估但如果地图有对角线移动且对角线被简化成“先横再竖”的路径启发式估价就可能超过真实代价。解决逐条检查启发函数与代价函数是否匹配。最稳妥的做法是单步代价为 1、四邻域用曼哈顿距离允许斜走且斜走代价为 2、直走代价为 1可以用对角线距离公式。想快速验证写一个小脚本随机生成几十张地图把 A* 结果和 BFS 结果对比不一致就是启发函数出问题。5.2 重复入堆、g 值更新错误导致搜索“翻车”现象搜索明明已经找到终点但路径不是最短或者程序疯狂占用内存扩展节点数量离谱。原因常见写法是开一个closed_set把弹出的节点放进去当邻居已经在 closed_set 里就直接跳过。这种做法省内存但如果第一次弹出的路径不是最优的后面发现了更短的 g 值却因为“已关闭”而无法更新最优性就丢了。解决不用 closed_set改用 g 值比较如上节代码所示。核心逻辑只有一句“只有当新路径的 g 值更小时才更新。”这个模式同时适用于 Dijkstra 和 A*。注意代码里current_g的取值。如果从堆里弹出的 g 值已经过时有更新的更小 g 值没有被重新压入堆用它去推算邻居的 tentative_g 会出错。常见做法是弹出的current_g g_score[current]才继续处理不满足就跳过if current_g g_score.get(current, float(inf)): # 过期节点直接跳过 continue这行代码能拦截大量重复处理建议加上。这是 A* 性能调优中最立竿见影的几行之一。5.3 邻域与移动代价不匹配导致路径失真现象地图允许斜走输出路径看起来“能通行”却穿过了墙角或者明明斜走更短却选择了横竖折线。原因斜向移动时邻域从 4 个变成了 8 个但代码里get_neighbors更新了方向列表heuristic却仍然用曼哈顿距离。由于斜走一步的直线距离比横竖一步短但代价几何没配对启发函数低估了代价破坏了搜索的优先级判断。解决把斜向移动和代价绑定。常见做法是横竖移动代价为 1斜向移动代价为约 1.414启发函数用“切比雪夫距离或按八方向代价计算”也就是h(n) max(|dx|, |dy|) (sqrt(2) - 1) * min(|dx|, |dy|)用浮点代价时注意比较tentative_g 1.0不要直接做浮点相等比较用比较即可。更稳妥的是所有代价用整数表示比如横竖为 10、斜向为 14既能保持距离比例又避免浮点误差。5.4 启发函数设成 0A* 退化成 Dijkstra现象A* 代码跑得奇慢无比扩展节点数基本等于全图节点数但路径质量完全正确。原因启发函数直接return 0此时 f gA* 的扩展顺序和 Dijkstra 一模一样完全没有利用目标位置信息。很多人在调试时图省事把 h 设成 0再也没有改回来。解决在代码入口处加一个断言确保 h 不为全 0# 调试用如果 h 恒为 0立刻报警 assert any(heuristic(s, goal) 0 for s in [start]), 启发函数疑似恒为0这种断言平时不触发但能拦住调试后的“忘记恢复”失误。它也提醒一个道理A* 的性能完全系在启发函数上h 越接近真实代价扩展节点越少。5.5 堆里塞满路径导致内存爆炸现象大迷宫跑 A*内存占用飙升有时候是几 GB程序直接被杀掉。原因最典型的写法是把“完整路径”直接存进堆里的每个节点结果每个状态携带一份长度可能几百的列表内存从 O(n) 膨胀成了 O(n*d)。这是新手常见的玄学翻车点。解决堆里只存状态和代价值路径统一通过came_from字典在终点处回溯。上面的核心实现已经是这个模式。如果确实需要诊断路径最多只在找到终点后调用reconstruct_path构造一次。排查技巧在循环里每扩展 10000 个节点打印一次堆大小和 g_score 字典长度观察增长速度。正常情况下 g_score 增长接近线性如果堆大小持续数倍于状态数且不下降很可能出现了重复入堆过多的状况回到 5.2 的过期节点策略去排查。这些踩坑记录里5.1 和 5.2 专门针对最优性5.3 和 5.5 针对路径质量和资源开销5.4 是性能问题。实际调代码时按“先确认路径正确再确认内存合理最后确认速度”的顺序排查。6. 验证方法与进阶优化把 A* 调到一个工程能用的状态6.1 小图手算验证的正确姿势A* 实现完不验证就直接上大图是自找苦吃。先拿一张 5x5 无障碍地图起点在左下、终点在右上手工列出每次从堆里弹出的节点、对应的 f/g/h 三个值再和代码输出逐行对比。如果第一行就不一致优先检查堆的排序规则和方向遍历顺序。如果弹出顺序一致但路径不一致检查 g 值更新逻辑和came_from记录的时间点。这类验证题在搜索引擎里搜“A* 算法原理图”能找到大量手算例子挑一个节点数不超过 10 的图按上面的方式走一遍10 分钟内能把 A* 的编码错误排掉大半。6.2 进阶权重 A* 与双向搜索A* 跑通之后还有两个简单的工程级优化值得尝试。权重 A* 的核心是把估价函数改成 f g w * h其中 w 大于 1。它强烈偏向启发方向扩展搜索速度大幅提升代价是路径不再是严格最优但很多游戏寻路场景里“接近最优且速度快”远比“绝对最优但慢”更有价值。调整时观察不同 w 值下的路径长度与扩展节点数的关系就能找到可以接受的折中。双向搜索的思路是同时从起点和终点做 A*两个方向交替扩展相遇时拼接路径。在起终点距离远的大地图上双向搜索通常比单向 A* 减少大量扩展节点。要注意两边的启发函数需要改成“到对方起点的距离”才能保持一致性。这些优化都属于“把 A* 调到一个工程能用的状态”的具体手段每一类都值得单独拿一张地图做实验对比数据。说回到整体心得。搜索技术这条学习链上最容易辜负人的就是“以为自己懂 A* 了”会背公式容易能说清楚为什么h必须不高估、为什么closed_set不能单纯关闭、为什么堆比较要加 counter 才算入门。我自己的习惯是每写一个搜索算法都配一个 5x5 的手算测试和一张随机地图回归测试前者保证逻辑对后者保证实现稳。这套方法踩过无数坑之后依然可靠希望能帮到正卡在某一步的你。本文还有配套的精品资源点击获取