第三章的下册我连着啃了两遍。上篇讲完盲目搜索之后我一直觉得哪里没通广度优先和深度优先确实能解决问题但一旦状态空间变大那种一层一层往外扩的做法就非常吃力。直到周末把启发式搜索、博弈搜索、约束满足这三块学完才意识到第三章真正的核心不是“教会机器找到答案”而是“教会机器用知识去逼近答案”。很多人问我现在入行人工智能应该先学什么我的回答一直很统一先把搜索这一章吃透别急着上大模型和深度学习框架。搜索是很多决策问题的底层骨架后面学的路径规划、自动规划、智能体决策全都能在第三章找到影子。这篇笔记把第三章下的内容重新梳理一遍包括我手动推演过的算例、跑过的Python实现以及几个踩完坑才想明白的细节。适合正在上人工智能导论课的学生也适合自学入门、想补搜索基础的朋友对照参考。1. 下册整体布局从“会找”到“会挑”1.1 上篇回顾与下篇定位先花几十秒回顾上篇。第三章上册主要讲了状态空间表示和图搜索的基本思路把问题抽象成“状态节点转移边”然后在图中找一条从初始状态到目标状态的路径。盲目搜索方法比如宽度优先搜索BFS和深度优先搜索DFS能保证找到解但代价很大。BFS一层一层地扩展能保证最短路径却要记住大量待扩展节点DFS虽然省内存但很容易钻进死胡同还可能因为深度限制找不到解。上篇学完我最大的感受是“能做题但很不优雅”。下册的出现就是来解决这个问题的给搜索加上方向感让它优先往“看起来有希望”的方向走这就是启发式搜索的出发点。如果你正在自学我的建议是别跳过上册否则很难理解为什么A*算法里偏要绕那么多弯。盲目搜索虽然看上去笨却是理解搜索框架最好的跳板。1.2 三个核心主题的串联逻辑第三章下围绕三块内容展开启发式搜索、博弈搜索、约束满足问题求解。表面上是三个独立主题实际上它们的逻辑链条非常清晰。搜索归根结底是在一个大空间里找解但不同场景下“怎么找”的策略完全不同。单智能体静态环境追求效率和最优性用启发式搜索代表是A*。多智能体对抗环境你走一步、对手走一步要在博弈树里找最有利局面这就是博弈搜索代表是极大极小算法和α-β剪枝。问题被描述成“变量取值范围约束”的形式需要在满足约束的前提下给每个变量赋值这是约束满足问题CSP代表是回溯搜索和约束传播。我的理解是启发式搜索解决的是“代价和方向”博弈搜索解决的是“对手和不确定性”CSP解决的是“约束和组合爆炸”。这三者互相配合才算把搜索真正用起来。2. 启发式搜索用知识给搜索指路2.1 传统盲目搜索的痛点盲目搜索最大的问题在于“一视同仁”。我对着一张地图用BFS找最短路径它会像画同心圆一样从起点一层一层扩展哪怕终点明显在东北方向它依然要先把西南方向的整片区域全部扫一遍。这种对空间的无差别探索就是组合爆炸的根源。启发式搜索的思路是打破这种“一视同仁”在扩展节点时利用问题本身的额外信息估算哪个节点更接近目标优先扩展它。关键是找到合适的启发函数Heuristic Function记为h(n)。它不看已经走了多远只看“从当前节点到目标还有多远”的估计值。比如八数码问题里可以把“当前每个数字到正确位置需要的步数总和”作为h(n)这叫曼哈顿距离。h(n)是启发式搜索的灵魂它决定了算法最终是高效还是低效。h(n)0时本质上就退化成迪杰斯特拉算法虽然能保证最优但效率不高h(n)值偏大且超过真实代价时算法会变得非常快却有可能丢掉最优解。计算量和最优性之间如何取舍是启发式搜索里永远需要权衡的问题。2.2 A*算法的关键要素A*算法是最经典的启发式搜索。它使用一个评价函数f(n)来决定扩展节点的顺序f(n) g(n) h(n)其中g(n)是从起点到节点n已经付出的实际代价h(n)是从n到目标点的估计代价。整个算法的核心是每次从优先队列里取出f(n)最小的节点来扩展。A*为什么能保证找到最优解关键在于h(n)必须满足“可采纳性”Admissible也就是说h(n)永远不大于从n到达目标的真实代价。直觉上很容易理解如果评估函数总是不慌不忙地低估距离它就不会急着把一个非最优路径上的节点当成目标反过来如果高估了代价算法可能因为“觉得”某条路径太贵而直接剪掉从而错失最优解。还有一个相关但容易混淆的概念叫“一致性”Consistency也叫单调性。一致性要求h(n)不大于从n转移到下一个节点n‘的实际代价加上h(n’)。可以这样理解沿着转移走下去每一步的启发值都不能突然“跳涨”。可采纳性是全局最优性的下限条件一致性能让A*在第一次展开某节点时就已经确认拿到了它的最短路径从而避免重复的重新计算。实际做题时验证一致性比验证可采纳性更直观算一下相邻状态的差值就能判断。注意A*用优先队列实现优先队列的排序键是f(n)。当你确定h(n)满足一致性时一个节点一旦被弹出队列它的g值就已经是最终值不需要再处理后续到达同一节点的更短路径。2.3 一个用手算出来的A*算例我学习的时候最受益的是自己手算一遍经典的“八数码问题”。八数码是一个3×3方格里有1到8八个数字和一个空格每次把空格和相邻数字交换最终要摆成目标状态。我设置了一个简化场景来验证A*。初始状态为283164705目标状态为123804765我选择h(n)为每个数字的曼哈顿距离之和g(n)为已经走过的步数。从初始状态开始空格0在第三行第二列它有三种移动可能空格上移、左移、右移。分别计算每个邻居状态的f值取最小者继续扩展。手动推演时最重要的是要维护两个集合已经找到最优路径的“已扩展集合”和还没有展开的“候选集合”。算了几层之后我发现h(n)起了明显的导向作用那些把大数字堆在正确位置附近的状态f值往往更小自然会被优先扩展。这就是启发式搜索和盲目搜索视觉上的最大差别——它不会漫无目的地扩散而是顺着一条“看起来就是正确方向”的路径走。A*没有固定公式可套每个问题的h(n)设计都不一样。我后来尝试把八数码的h(n)改成“错位数”结果搜索时间明显变长。同一个问题评估函数的精确度直接决定了算法效率这点在考试和实际工程里都很重要。3. 博弈搜索让机器学会在对抗中决策3.1 极大极小搜索的原理第二章之后的印象还很新鲜。第三章下册紧接着就把搜索从一个玩家扩展到了两个玩家。棋类博弈就是典型的对抗场景我走一步对手走一步我要找到让我最终获胜的走法但对手总是会选对他最有利、对我最不利的招法。极大极小算法Minimax用一棵树来模拟这个过程。树的每一层角色交替我的回合叫“极大层”因为我要选收益最大的子节点对手的回合叫“极小层”因为对手会选让我收益最小的子节点。从叶子节点向上回溯每个节点都带着一个“对我来说的收益值”最后根节点会告诉你第一步该走哪条路。这看起来很容易但实际上博弈树的规模大得惊人。国际象棋平均分支因子约35深度40层的博弈树分支数量是个天文数字直接搜索根本算不完。这也是为什么纯粹用极大极小只能解决非常浅层的棋类问题实际系统中必须引入剪枝和启发式评估。3.2 α-β剪枝如何提升效率α-β剪枝是极大极小算法最经典的优化。核心思想一句话就能概括如果当前已经确定某个分支不可能比已有选择更好就不要继续搜索这个分支了。我用一个简单的例子说明。假设当前在一层极大节点上它已经找到左边分支的估值是10正在搜索右边分支的第一个子节点发现这个子节点在极小层返回的值是4。因为极小层后续返回的值只会小于等于4这个父节点最终拿到的值不可能超过4而左边分支已经拿到10了那么右边分支直接剪掉。α代表极大层目前确认的最大下限β代表极小层目前确认的最小上限。搜索过程不断更新这两个值当α大于等于β时就剪枝。剪枝的效果非常显著实际测试中平均能减少大约一半的节点扩展对深一层搜索的帮助是决定性的。提示α-β剪枝的结果和没剪枝的极大极小搜索结果完全一致它只减少计算量不改变决策。考试时遇到要求写搜索顺序的题务必先按深度优先生成节点再在回溯时判断能否剪枝顺序写错会把整个判定结果带偏。3.3 评估函数设计的实际经验棋类博弈里不可能一直搜索到终局大部分时候需要在固定深度停下来评估局面。这个评估函数Evaluation Function的作用是把一个局面的“好/坏”量化成一个数字。设计评估函数的经验主要有几点。第一特征要选对。简单五子棋可以用“连子数”和“活三、冲四数量”来加权象棋可以用“棋子子力价值位置价值机动性”来综合。第二权重需要反复调。我试过把“活三”权重视为“冲四”的1.5倍结果棋风偏保守后来改成1.0倍进攻性明显提升。第三评估函数必须和搜索深度配合。一般来说搜索深度越深评估函数可以稍微粗糙一点反之评估函数要更准确。这里也回应一下很多同学关心的“人工智能机器人”到底强在哪。AlphaGo这类系统的核心思想依然是博弈搜索但它用深度网络学出一个很强的局面评估函数再用蒙特卡洛树搜索把这个评估结果部署到策略搜索里去。搜索框架没变变化的是评估函数从一个粗糙的公式进化为一个能拟合大量棋谱的神经网络。4. 约束满足问题求解4.1 把现实问题建模成CSP第三个大主题是约束满足问题。这类问题在人工智能课程里地位很高因为它把很多实际调度、排课、填色、地图着色问题都归到一个统一的框架里变量、值域、约束。八皇后问题里8个皇后就是8个变量每个变量的值域是0到7表示所在列约束是任意两个皇后不能在同一行、同一列或同一斜线。地图填色问题是各个区域是变量颜色是值域约束是相邻区域颜色不同。CSP建模的巧妙之处在于把问题从“怎么搜索路径”换成了“怎么分配值”。路径搜索看重的是动作序列CSP看重的是状态本身是否合法。这种视角转换非常有用很多看起来复杂的组合问题只要你能把约束条件列清楚就能直接套用通用的CSP求解算法。我实操时最大的感受是约束写得好不好直接决定求解器的效率。同样一个排课问题冗余约束能让搜索空间大幅缩小约束少了求解器会花很多时间在候选解里摸索约束写错求解器给出一个看似合法实则错误的解。所以建CSP模型时一定要把约束一个个列出来并对照原问题检查。4.2 回溯搜索与约束传播CSP最基础的求解方法是回溯搜索给一个变量赋一个值检查是否与已有赋值冲突不冲突就继续给下一个变量赋值冲突就换一个值所有值都冲突就退回上一层重新选值。只靠回溯很容易出现一个效率陷阱某个冲突要到很深的层数才暴露导致大量无效搜索。解决办法是约束传播最经典的是AC-3算法。它的思路是维护弧一致性遍历所有约束不断删掉变量值域里不可能出现在任何解中的值直到整个约束网络满足弧一致。用生活经验来类比就像解数独时先看看一个格子还能填哪些数字把所有确定不可能的候选标记掉后续填数就轻松很多。把回溯搜索和约束传播结合起来就是当前主流CSP求解器的基本范式。传播负责把搜索中每步决定带来的连锁影响提前消化掉回溯负责在决策树里寻找正确组合。4.3 手写最小冲突法解N皇后为了加深理解我自己写了一个N皇后求解器参考的是局部搜索算法里的“最小冲突法”。它不是从头构建一个合法解而是先随机把所有皇后放好然后不断挑出某个冲突最多的皇后把它移动到冲突数最小的那一列重复这个步骤直到没有冲突。这个方法和回溯搜索的思路完全不同它不是系统搜索而是迭代修复很多时候收敛得很快。我的代码里大概一百多行就解决了千皇后规模的题目比单纯用回溯加约束传播更容易写出可运行版本。5. 实操编码把算法跑起来5.1 八数码问题的A*实现纸上推演终归不够扎实我建议一定把A*用代码实现一次。我用Python重写了一个八数码求解器关键部分如下import heapq def manhattan(state, goal): dist 0 for i in range(3): for j in range(3): val state[i][j] if val 0: continue gi, gj divmod(goal.index(val), 3) dist abs(i - gi) abs(j - gj) return dist def solve(start_tuple, goal_tuple): # state 用三元组表示方便哈希 goal list(goal_tuple) start [list(start_tuple[i:i3]) for i in range(0, 9, 3)] # ... # 核心逻辑用堆维护 f g h每次弹出 f 最小的状态 pass实际跑起来之后我第一次意识到了两个容易出错的地方。第一是从二维数组到一维元组的转换如果你在代码里频繁用二维列表做哈希会直接报unhashable type我改用展平的一维元组表示状态顺手解决了这个问题。第二是移动空格时需要注意边界不要在二维数组里试图把空格移出棋盘。5.2 N皇后最小冲突法的代码要点再给一个N皇后最小冲突法的核心片段虽然逻辑不长但很能帮助理解局部搜索在CSP里的应用。import random def min_conflicts(n, max_steps1000): # 每行皇后所在列 queens [random.randint(0, n - 1) for _ in range(n)] col_count [0] * n diag1 [0] * (2 * n - 1) # row - col diag2 [0] * (2 * n - 1) # row col # 初始化冲突计数然后循环选冲突最大的行移到冲突最小的列 return queens我测试时发现N1000时随机初始位置通常能在几十步内收敛但偶尔会陷入局部震荡。解决办法是加入随机重启连续若干轮没有改善就重新随机初始化。这也是很多实际求解器采用的策略单个随机搜索可能失败多次重启后成功率非常可观。6. 学习踩坑与疑问排查6.1 概念混淆点有几处是我学的时候反复绕晕的地方单独列出来提醒自己也方便你对照排查。第一g(n)和h(n)到底谁负责最优性。答案是h(n)决定方向和最优性g(n)保证最终结果不是假的。g(n)算错或没累加f值排序就会紊乱很可能跳出一个看似不错实际上代价很大的解。第二可采纳性与一致性不能等同。可采纳性针对全局目标一致性针对相邻节点传递。很多教材只在讲可采纳性时强调最优性条件但代码实现里如果只用可采纳h而不用一致性某些情况下一个节点可能会被重复展开效率和正确性都会受影响。第三博弈搜索里的“层”容易数错。极大层和极小层必须严格交替从根节点开始如果自己是玩家第一层就是极大层第二层是极小层。判卷和调试时最常见的问题就是层数搞错导致剪枝结果完全错误。6.2 一组方便记忆的对照算法/概念核心作用常见错误BFS保证最短路径空间开销大忘记visited集合造成死循环DFS搜索深度优先内存小没有深度限制可能无限下降A*利用fgh高效搜索h高估导致丢失最优解Minimax对抗条件下选择最优行动层角色搞反α-β剪枝减少无效分支的搜索剪枝顺序错误导致结果不同AC-3删减值域中的不可能值删除时没有持续传播直到稳定6.3 学完这一章对后续内容的影响学到第三章下半部分我对人工智能课程的整体结构有了一种“看见了地图”的感觉。以前在新闻里听到“人工智能机器人”“自动驾驶路径规划”这些词总觉得技术门槛很高现在回头看里面很多核心方法依然是用搜索解决问题的变体。比如自动驾驶里的路径规划本质上是在状态空间里搜索出一条代价最小的轨迹A*和它的变体RRT就是常用工具。机器人做任务规划通常是把高层任务分解成若干动作序列然后在动作状态空间里搜索可行序列。再比如需要排课排班、生产调度的系统就是CSP模型配合求解器在产出排程结果。这些例子让我理解了一个更本质的事情人工智能课程里教的搜索、知识表示、推理并不是过时的老古董而是今天大模型时代依然在发挥作用的底层方法。大模型负责“生成”搜索负责“在生成的候选里做选择和规划”两者结合才是目前Agent类应用很常见的架构。顺便说一句网上关于“人工智能学习路径”和“人工智能训练师”的讨论越来越多。我个人的学习路线建议是先把搜索、概率推理这些经典基础打牢再去接触机器学习和大模型就不会觉得那些新概念悬在空中。第三章正好是打这种基础的关键一环。7. 最后再分享一点我的操作心得这一章的学习我前后花了差不多一整周最推荐的检验方式是不看任何参考资料自己手动推演一遍A*在八数码或地图寻路上的完整过程再手算一道α-β剪枝顺序。这两件事能做到说明基本就掌握了。如果你也在学这门课建议动手写一版自己的A*和N皇后求解器代码不一定要长但一定要亲手调通。我在写完最小冲突法之后再回头看回溯搜索才彻底明白为什么教材要先讲系统搜索再讲局部搜索。第三章的下册到这里就整理完了。这章所有的知识都有一个共同点它们不是在仓库里找现成答案而是在一个巨大的可能性空间里用不同的策略逼近一个更好的答案。这种“搜索思维”会在你后续学习机器学习、强化学习、多智能体系统时反复出现。希望这篇笔记能帮到正在啃同一章的同学少走一点我走过的弯路。