企业官网建设流程全解析

第三章的下册我连着啃了两遍。上篇讲完盲目搜索之后，我一直觉得哪里没通：广度优先和深度优先确实能解决问题，但一旦状态空间变大，那种一层一层往外扩的做法就非常吃力。直到周末把启发式搜索、博弈搜索、约束满足这三块学完，才意识到第三章真正的核心不是“教会机器找到答案”，而是“教会机器用知识去逼近答案”。很多人问我现在入行人工智能应该先学什么，我的回答一直很统一：先把搜索这一章吃透，别急着上大模型和深度学习框架。搜索是很多决策问题的底层骨架，后面学的路径规划、自动规划、智能体决策，全都能在第三章找到影子。

这篇笔记把第三章（下）的内容重新梳理一遍，包括我手动推演过的算例、跑过的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*。初始状态为：

目标状态为：

我选择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:i+3]) 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_steps=1000): # 每行皇后所在列 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

我测试时发现，N=1000时随机初始位置通常能在几十步内收敛，但偶尔会陷入局部震荡。解决办法是加入随机重启：连续若干轮没有改善就重新随机初始化。这也是很多实际求解器采用的策略，单个随机搜索可能失败，多次重启后成功率非常可观。

6. 学习踩坑与疑问排查

6.1 概念混淆点

有几处是我学的时候反复绕晕的地方，单独列出来提醒自己，也方便你对照排查。

第一，g(n)和h(n)到底谁负责最优性。答案是h(n)决定方向和最优性，g(n)保证最终结果不是假的。g(n)算错或没累加，f值排序就会紊乱，很可能跳出一个看似不错实际上代价很大的解。

第二，可采纳性与一致性不能等同。可采纳性针对全局目标，一致性针对相邻节点传递。很多教材只在讲可采纳性时强调最优性条件，但代码实现里如果只用可采纳h而不用一致性，某些情况下一个节点可能会被重复展开，效率和正确性都会受影响。

第三，博弈搜索里的“层”容易数错。极大层和极小层必须严格交替，从根节点开始如果自己是玩家，第一层就是极大层，第二层是极小层。判卷和调试时最常见的问题就是层数搞错，导致剪枝结果完全错误。

6.2 一组方便记忆的对照

6.3 学完这一章对后续内容的影响

学到第三章下半部分，我对人工智能课程的整体结构有了一种“看见了地图”的感觉。以前在新闻里听到“人工智能机器人”“自动驾驶路径规划”这些词，总觉得技术门槛很高，现在回头看，里面很多核心方法依然是用搜索解决问题的变体。

比如自动驾驶里的路径规划，本质上是在状态空间里搜索出一条代价最小的轨迹，A*和它的变体RRT就是常用工具。机器人做任务规划，通常是把高层任务分解成若干动作序列，然后在动作状态空间里搜索可行序列。再比如需要排课排班、生产调度的系统，就是CSP模型配合求解器在产出排程结果。

这些例子让我理解了一个更本质的事情：人工智能课程里教的搜索、知识表示、推理，并不是过时的老古董，而是今天大模型时代依然在发挥作用的底层方法。大模型负责“生成”，搜索负责“在生成的候选里做选择和规划”，两者结合才是目前Agent类应用很常见的架构。

顺便说一句，网上关于“人工智能学习路径”和“人工智能训练师”的讨论越来越多。我个人的学习路线建议是：先把搜索、概率推理这些经典基础打牢，再去接触机器学习和大模型，就不会觉得那些新概念悬在空中。第三章正好是打这种基础的关键一环。

7. 最后再分享一点我的操作心得

这一章的学习，我前后花了差不多一整周，最推荐的检验方式是：不看任何参考资料，自己手动推演一遍A*在八数码或地图寻路上的完整过程，再手算一道α-β剪枝顺序。这两件事能做到，说明基本就掌握了。

如果你也在学这门课，建议动手写一版自己的A*和N皇后求解器，代码不一定要长，但一定要亲手调通。我在写完最小冲突法之后，再回头看回溯搜索，才彻底明白为什么教材要先讲系统搜索再讲局部搜索。

第三章的下册到这里就整理完了。这章所有的知识都有一个共同点：它们不是在仓库里找现成答案，而是在一个巨大的可能性空间里，用不同的策略逼近一个更好的答案。这种“搜索思维”会在你后续学习机器学习、强化学习、多智能体系统时反复出现。希望这篇笔记能帮到正在啃同一章的同学，少走一点我走过的弯路。