人工智能导论：非神经网络部分期末学习指南

0. 怎么用这份指南

如果你之前完全没听课，最重要的不是先背概念，而是先把“考试会让你做什么”看清楚。2021 与2024真题的共同重点非常清楚：α-β剪枝、修正A*、ID3/C4.5决策树，以及围棋策略网络/MCTS训练思路。课件里还覆盖 MCTS、AlphaGo、AlphaGo Zero、Viterbi、模拟退火、遗传算法等知识点，其中有些更偏理解题或选择题。

1. 期末题型地图：你最终要能做什么

1.1 2024真题增补：本版新增了哪些东西

2. 搜索问题总览

搜索问题的本质：在一个巨大的状态空间里，从初始状态 S₀ 找到目标状态 Sg，最好还能找到代价最小的解路径。课件1从导航、机器证明、大模型解码引入搜索，强调关键问题是“如何利用知识，尽可能有效地找到解或最佳解”。

2.0.1 搜索算法的共同语言

2.1 深度优先、宽度优先、Dijkstra

2.1.1 深度优先搜索 DFS

深度优先搜索优先扩展深度更深的节点，像“沿着一条路走到底，不行再退回来”。课件用八皇后展示了它的状态空间：每放一个皇后，状态就多一行皇后位置；若冲突则回溯。

2.1.2 宽度优先搜索 BFS

宽度优先搜索优先扩展深度浅的节点，像“先看一步能到哪里，再看两步能到哪里”。

2.1.3 Dijkstra算法

Dijkstra 弥补 BFS 不看边权的问题：每次优先扩展当前离起点最近的节点，也就是 g(n) 最小的节点。它不使用目标方向信息，因此能保证最短路，但可能在目标反方向也扩展很多节点。

2.2 A算法、A*算法、启发函数与单调性

2.2.1 A算法

A算法引入启发知识，用 f(n)=g(n)+h(n) 对 OPEN 中的节点排序。g(n) 表示已经走了多远，h(n) 猜还要走多远。每次扩展 f 最小的节点。

OPEN = {s}, CLOSED = {}
while OPEN 非空:
    n = OPEN 中 f 最小的节点
    if n 是目标: 返回路径
    从 OPEN 删除 n，加入 CLOSED
    扩展 n 的后继 m
    计算经 n 到 m 的新 g 和 f = g + h
    如果 m 新发现: 加入 OPEN，父指针指向 n
    如果 m 已在 OPEN 且新 f 更小: 更新 f 和父指针
    如果 m 已在 CLOSED 且新 f 更小: 重新放回 OPEN，更新父指针

2.2.2 A*算法：可采纳的A算法

如果启发函数满足 h(n) ≤ h*(n)，其中 h*(n) 是 n 到目标的真实最短代价，那么这个 A 算法叫 A*。直观理解：启发函数要“乐观”，可以低估剩余距离，但不能高估。

2.2.3 8数码的两个典型 h

2.2.4 启发信息越多，扩展节点越少？

课件给出定理：同一问题上两个A*算法 A₁、A₂，若对所有非目标节点都有 h₂(n)>h₁(n)，则 A₁ 扩展的节点数至少与 A₂ 一样多。注意这里是严格大于，且评价指标是“扩展过的不同节点数”，同一节点重复扩展多次只算一次。

2.2.5 单调性：让A*不必反复重开节点

启发函数 h 如果对每条边 nᵢ→nⱼ 都满足：

就叫单调启发函数，也叫一致启发函数。它的含义类似三角不等式：从 nᵢ 到目标的估计，不应大于“先走到 nⱼ 的代价 + 从 nⱼ 到目标的估计”。

2.2.6 A*考场流程

1. 先在图上标出每个节点的 h 和每条边代价。
2. 建立表格：步骤、扩展节点、g、h、f、OPEN、CLOSED、父指针。
3. 每扩展一个节点，计算后继的 g_new=g(parent)+cost，再算 f_new=g_new+h。
4. 如果后继已出现，比较新旧 g 或 f；若新路径更优，更新父指针。
5. 只在目标成为下一次扩展节点时停止。
6. 从目标沿父指针回溯到起点，写出路径和总代价。

2.2.7 一个可手算的A*小例子

假设图如下：S 到 A 代价2，S 到 B 代价5；A 到 C 代价2，B 到 C 代价1；C 到 G 代价3，A 到 G 代价8。启发函数为 h(S)=5,h(A)=4,h(B)=3,h(C)=2,h(G)=0。

解路径由父指针回溯为 S→A→C→G，总代价7。注意第2步生成 G 时不能立刻停，因为当时 OPEN 中有 C 的 f=6 小于 G 的 f=10。

2.2.8 启发函数设计与评价

课件用“传教士与野人”说明启发函数设计：放宽安全约束，只保留船容量约束，估计至少还需摆渡多少次。这样得到的是宽松问题下的最少次数，因此不会高估真实问题的剩余代价，满足A*条件。课件中还给出一种状态表示下的估计 h=M+C-2B，其中 M、C 是左岸剩余人数，B 表示船是否在左岸。

启发函数的效果可用平均分叉数 b* 评价。若解深度为 d、总搜索节点数为 N，则近似满足：

b* 越小，说明启发函数越有效。课件的8数码实验中，曼哈顿距离和通常比“不在位牌数”有更小的平均分叉数。

2.3 修正的A*算法：fm 与 NEST

修正A*是2021明确出现的题型。它的目标是：在保持可采纳性的前提下，减少普通A*由于重新打开 CLOSED 节点造成的重复扩展，而且不比普通A*扩展更多节点。

2.3.1 为什么要改

普通 A 算法中，如果某个已经扩展过的节点后来发现更短路径，就要把它重新放回 OPEN，这会导致重复扩展。课件提出两个途径：一是限制 h，使它单调；二是改算法，用 fm 和 NEST 控制扩展顺序。

NEST 不为空时，为什么选 g 最小的节点？
答：g 最小意味着该节点在搜索树中最靠近起点（处于上游）。这样做是为了“先把靠近起点的基础夯实，把真实的代价确定下来”，再去探索深处的节点。这样就能极大程度上避免“深层的节点被扩展完后，因为浅层节点找到更优路径而被迫重算”。

2.3.2 修正A*规则

Modified-A*(s):
    OPEN = {s}; CLOSED = {}; f(s)=g(s)+h(s); fm=0
    while OPEN 非空:
        NEST = { n in OPEN | f(n) < fm }
        if NEST 非空:
            n = NEST 中 g 最小的节点
        else:
            n = OPEN 中 f 最小的节点
            fm = f(n)
        if n 是目标: 返回路径
        扩展 n，更新 OPEN/CLOSED/父指针

2.3.3 这道题怎么写才稳

2.3.4 2024真题同型例题：修正A*完整表

2024第2题给的是一个有向图，弧线边数字为代价，启发值为：\(h(S)=14,h(E)=8,h(A)=1,h(B)=4,h(C)=8,h(D)=14,h(T)=0\)。可读出的关键有向边如下：

因此扩展/选出顺序可写为 S, B, A, C, B, A, D, C, B, A, T；若只写“真正展开后继”的节点，则最后的 T 可单独说明为“目标被选出，停止”。最终路径为：

2.4 动态规划、Viterbi 与拼音输入法

课件1后半部分把搜索用于拼音输入法。一个拼音串可能对应海量汉字序列，例如每个音平均10个候选，11个音就有约 10¹¹ 个句子，穷举不可行。

2.4.1 从概率到最短路径

输入拼音 O，候选汉字句子 S=w₁…wₙ。目标是找最大后验概率的句子：

如果简化地忽略多音字，P(O|S) 近似常量，问题变成最大化语言模型概率 P(S)。二元语法下：

于是每个候选字是图中的节点，相邻拼音位置之间的边权是 -log P(wᵢ|wᵢ₋₁)，找最小代价路径就是找最可能句子。

2.4.2 Viterbi动态规划

这就是有限宽度分层图上的最短路径。若每一层只保留前 K 个候选，就变成 beam search。

2.4.3 平滑与识别后处理

二元概率常用最大似然估计：

若语料中没见过某个搭配，概率可能为0，所以要平滑。课件给出一种线性插值形式：

汉字识别后处理也类似：每个位置有多个识别候选及识别信度，用语言模型概率和识别信度共同决定最优汉字序列。

2.5 局部搜索、模拟退火、遗传算法

课件1提到爬山法、随机搜索；2021和旧题明确考模拟退火与遗传算法。它们都属于“不系统展开整棵搜索树，而是在候选解空间中移动”的方法。

2.5.1 爬山法与局部最优

爬山法每次选择邻域中更优的状态，优点是简单，缺点是容易卡在局部最优或平台。模拟退火就是为了解决“偶尔需要走差一步才能跳出坑”的问题。

2.5.2 模拟退火 SA

如果目标是最小化能量 E，从当前状态到候选状态的能量变化为 ΔE=E_new-E_current：

2.5.3 遗传算法 GA

遗传算法把候选解看作个体，多个个体组成种群。基本流程是：编码、初始化种群、计算适应值、选择、交叉、变异、形成新一代。

轮盘赌选择

若种群 A、B、C、D 适应值分别为 4、6、2、8，总适应值20，则选择概率和累积区间为：

随机数 0.15、0.55、0.25、0.45 对应选择 A、C、B、B。

确定性选择

一种常见做法是计算期望复制数 N·fitness_i / Σfitness，先取整数部分，再按小数部分从大到小补足种群规模。例如上例种群大小4，期望复制数 A=0.8、B=1.2、C=0.4、D=1.6，整数部分给 B、D 各1个，还差2个，按小数部分 A=0.8、D=0.6 最大，补 A 和 D，因此新种群可为 A、B、D、D。不同课件若指定了确定性采样方式，以题目给定规则为准。

3. 对抗搜索与 \(\alpha\)-\(\beta\) 剪枝

对抗搜索处理的是“我走一步、对手走一步”的博弈。课件里的典型前提是：双人、轮流行动、信息完备、零和。零和的意思是：一个局面对我越好，对对手就越坏，所以一棵博弈树可以只用一个效用值来描述。

3.1 先把博弈树看懂：状态、行动、效用

如果轮到我方行动，这一层叫 MAX 层，因为我会选择让局面对我最好的孩子；如果轮到对手行动，这一层叫 MIN 层，因为对手会选择让我最难受的孩子。于是博弈树的值递归定义为：

3.2 Minimax 手算模板：先叶子、后内部、最后根

1. 先标层：根节点是 MAX 还是 MIN，下一层交替。
2. 把所有叶子估值写清楚；如果题目只给叶子值，不要自己改。
3. 从倒数第二层开始往上算：MAX 取最大，MIN 取最小。
4. 根节点的孩子中，哪个给出根值，哪个就是当前应选择的走法。

3.3 为什么需要 \(\alpha\)-\(\beta\) 剪枝

Minimax 的问题是爆炸式增长。若每个局面平均有 \(b\) 个合法行动，向前看 \(d\) 层，叶节点数量约为 \(b^d\)。围棋、象棋一类游戏不可能完整搜完，于是我们希望：不改变 minimax 结果，但少看一些分支。

\(\alpha\)-\(\beta\) 剪枝的核心判断是：有些分支即使继续算完，也不可能改变祖先节点已经能做出的选择，因此可以提前不看。

3.4 \(\alpha\) 和 \(\beta\) 到底是什么

更贴近笔记的说法是：极大节点维护下界 \(\alpha\)，极小节点维护上界 \(\beta\)；后辈节点的 \(\beta\) 值不超过祖先的 \(\alpha\) 值时可剪，后辈节点的 \(\alpha\) 值不小于祖先的 \(\beta\) 值时也可剪。注意比较对象可以是祖先，不只是父节点。

3.5 从左到右剪枝例题

设根为 MAX，按从左到右访问叶子。左子树是 MIN，叶值为 \(3,5\)；右子树是 MIN，叶值为 \(2,9\)。

3.6 考场最容易错的四件事

3.7 2024真题补强：不齐博弈树怎么做

2024第1题的树有一个重要变化：有些“看起来像叶子”的方框下面还接着一层后继，说明它不是终局叶节点，而是一个需要继续倒推的生成节点。做这种题时，不要按外观把所有底层方框都当成叶子；只要某个节点还有孩子，就必须继续按 MAX/MIN 规则向下算。

4. 蒙特卡洛方法与蒙特卡洛树搜索 MCTS

蒙特卡洛方法的思想很朴素：如果一个量精确算不出来，就随机试很多次，用平均结果估计它。在博弈里，一个落子点到底好不好，可能难以用公式直接判断，于是可以从这个落子点开始随机模拟很多盘，看最后赢的比例。

4.1 从“随机试很多次”到期望估计

设随机变量 \(X\) 表示一次模拟的收益，例如赢为 \(1\)，输为 \(0\)，或者赢为 \(1\)、输为 \(-1\)。真实期望 \(\mathbb E[X]\) 不容易直接求，但可以做 \(N\) 次独立模拟：

模拟次数越多，样本平均通常越接近真实期望。放到棋局里，如果某个行动经过 100 次随机模拟赢了 63 次，就可以暂时估计它的胜率为 \(0.63\)。

4.2 MCTS 的四步循环

4.3 节点上到底存什么

一个 MCTS 节点通常至少保存两个统计量：访问次数和累计收益。若从节点 \(s\) 选择行动 \(a\) 到达子节点，则常写作：

如果收益记为胜利次数，\(Q\) 就是胜率；如果收益记为 \(-1,0,1\)，\(Q\) 就是平均局面价值。笔记中特别提醒：节点写成“获胜次数/模拟总次数”时，获胜次数是从该节点角度说的；如果题目约定从根节点玩家角度统计，就按题目约定来。

4.4 UCB / UCT：为什么不是永远选胜率最高

如果永远选当前胜率最高的孩子，早期随机好运的分支会被过度利用，其他潜在好分支没有机会被探索。UCB 用一个“利用项 + 探索项”解决这个问题：

• \(\overline{X}_j\)：第 \(j\) 个拉杆/子节点目前获得回报的均值，也就是利用项。
• \(n\)：到当前时刻为止，总访问次数。
• \(T_j(n)\)：第 \(j\) 个拉杆/子节点已经被访问的次数。
• \(\sqrt{2\ln n/T_j(n)}\)：探索项。访问越少，探索奖励越大；总访问越多，仍会给没试够的分支机会。

把 UCB 用到树上就常称为 UCT。选择阶段在每个内部节点都计算孩子的 \(I_j\)，选 \(I_j\) 最大的孩子向下走。

4.5 UCT 计算小例子

某节点总访问次数 \(n=20\)。三个孩子的“胜利次数/访问次数”分别为 A: \(6/10\)，B: \(2/5\)，C: \(1/1\)。按笔记公式：

所以本轮会优先选 C。它不只是因为目前胜率高，还因为访问次数太少，探索项很大。

4.6 MCTS 与 \(\alpha\)-\(\beta\) 的区别

5. 强化学习、AlphaGo 与 AlphaGo Zero

这一节按补充笔记中的 AlphaGo 公式重新整理：AlphaGo 不是“单纯一个神经网络下棋”，也不是“普通 UCT 直接套用”。它把策略网络、估值网络、快速 rollout 和 MCTS 结合起来，用神经网络减少盲目搜索，用树搜索修正神经网络的一步判断。

5.1 强化学习先抓三句话

强化学习学习策略 \(\pi(a\mid s)\)：在状态 \(s\) 下应选择动作 \(a\) 的概率或规则。它与监督学习不同：监督学习通常给出“这一步标准答案”，强化学习更多依靠试错和最终回报。

5.2 AlphaGo 中 MCTS 的节点收益：价值网络与 rollout 的混合

在普通 MCTS 中，一次模拟的收益可以直接来自随机走到终局的胜负。AlphaGo 的笔记公式把节点 \(s\) 的第 \(i\) 次模拟收益写成：

• \(value(s)\)：估值网络对局面 \(s\) 的输出，表示这个局面最终胜负倾向。
• \(rollout(s)\)：从 \(s\) 出发快速模拟一次得到的结果。
• \(\lambda\)：混合系数，用来平衡“神经网络估值”和“快速模拟结果”。

因此，AlphaGo 并不是只相信价值网络，也不是只相信随机模拟，而是把两者合成一次模拟收益。

5.3 平均收益 \(Q\)：走到某个子局面后平均有多好

设 \(s_a\) 表示在局面 \(s\) 的位置/动作 \(a\) 落子后的新局面。补充笔记中的平均收益为：

这就是“这个落子点已经被模拟过的平均效果”。若某个子局面被模拟很多次且收益高，它的 \(Q\) 会高；但如果只看 \(Q\)，仍然可能过早陷入某个看起来好的分支。

5.4 探索项 \(u\)：策略网络告诉搜索应该往哪里看

普通 UCT 的探索项是 \(\sqrt{2\ln n/T_j(n)}\)。AlphaGo 的笔记公式改成带策略先验的探索项：

• \(p(s_a)\)：策略网络认为在 \(a\) 处落子的概率。概率越高，越值得探索。
• \(N(s)\)：父局面 \(s\) 的模拟次数。
• \(N(s_a)\)：子局面 \(s_a\) 已被访问的次数。访问越多，探索奖励越小。
• \(c\)：加权系数，控制探索强度。

实际选择时，可以理解为选择使下面分数最大的动作：

5.5 AlphaGo 的整体流程

5.6 AlphaGo 与 AlphaGo Zero 的区别

5.7 2024真题补强：softmax策略网络如何用 MCTS 次数训练

2024第6题把围棋策略网络简化成“没有隐藏层的 softmax 分类器”。输入 \(x_i(i=1,\ldots,N)\) 表示当前棋局特征；输出 \(p_j(j=1,\ldots,N)\) 表示在第 \(j\) 个点落子的概率；\(m_j\) 是 MCTS 结束后第 \(j\) 个后继局面被选中的次数。题目希望 \(m_j\) 越大，网络输出 \(p_j\) 越大。

第一步：写出前向传播

第二步：把 MCTS 次数变成目标分布

令总访问次数 \(M=\sum_{k=1}^{N}m_k\)，目标概率为：

这样 \(q_j\) 就是“搜索认为第 \(j\) 个动作应该被选的比例”。这一步和 AlphaGo Zero 里用 MCTS 搜索策略 \(\pi\) 训练策略头的思想是一致的。

第三步：定义损失函数

这是交叉熵。若某个动作的 MCTS 比例 \(q_j\) 很大，而网络给的 \(p_j\) 很小，\(-q_j\log p_j\) 就会变大，迫使网络提高该动作概率。

第四步：推导梯度和更新式

6. 决策树：ID3 与 C4.5

决策树学习就是从训练集中归纳出一组分类规则，得到一棵与训练集矛盾较小、同时尽量能泛化到新样本的树。它的直观形式是“先问哪个问题，再根据答案继续问”，直到给出类别。

6.1 决策树在学什么

训练集 \(D\) 由很多样本组成，每个样本有若干特征和一个类别。决策树的内部节点是特征测试，边是特征取值，叶节点是类别标记。例如先问“天气=晴/阴/雨”，再问“湿度=高/正常”，最后判断是否打球。

6.2 熵：当前数据集有多不确定

若训练集 \(D\) 中有 \(K\) 个类别 \(C_1,\ldots,C_K\)，类别 \(C_k\) 的样本数为 \(|C_k|\)，总样本数为 \(|D|\)，则熵为：

熵越大，类别越混杂；熵越小，类别越纯。如果所有样本都属于同一类，熵为 \(0\)。计算时约定 \(0\log 0=0\)。

6.3 条件熵：按某个特征划分后还剩多少不确定

设特征 \(A\) 有 \(n\) 个可能取值 \(a_1,\ldots,a_n\)。按 \(A\) 的取值把 \(D\) 划分为 \(D_1,\ldots,D_n\)。其中 \(D_{ik}\) 表示子集 \(D_i\) 中属于类别 \(C_k\) 的样本集合。笔记中的条件熵公式可写为：

它是“先按特征 \(A\) 分组，再看每组内部还乱不乱”的加权平均。权重 \(|D_i|/|D|\) 不能漏，因为大分支比小分支影响更大。

6.4 信息增益：这个特征让不确定性减少了多少

信息增益越大，说明用特征 \(A\) 划分后，不确定性减少越多。ID3 每一步都选择当前信息增益最大的特征作为当前节点。

6.5 ID3 算法：按笔记整理的递归流程

6.6 完整手算例子：选根节点

考虑 8 条训练样本，类别为“打球=是/否”。候选特征有天气、湿度、风。

总数据集中“是”有 5 个，“否”有 3 个：

最大信息增益来自“天气”，所以 ID3 选择“天气”作为根节点。接着每个分支继续递归：例如“阴”分支全是“是”，可直接成为叶节点；“晴”和“雨”分支仍有混杂，需要继续选剩余特征。

6.7 C4.5：为什么要从信息增益改成信息增益比

ID3 的一个重要问题是：它偏爱取值很多的属性。极端地说，如果有一个“编号”特征，每个样本编号都不同，那么按编号划分后每个子集只有一个样本，条件熵为 0，信息增益会非常大，但这显然只是记住训练集，不能泛化。

C4.5 用信息增益比来惩罚这种“分支过多”的属性。先定义属性 \(A\) 自身造成的划分熵：

\(H_A(D)\) 越大，说明这个属性把数据切得越碎；除以它之后，可以降低多取值属性的虚高优势。

6.8 连续属性怎么处理

如果特征是连续值，例如“年龄”“收入”，不能像离散属性那样直接按每个数值开分支。常见做法是把连续属性转成二分测试：

1. 把样本按该连续特征从小到大排序。
2. 在相邻不同取值之间取候选阈值，例如 \(t=(a_i+a_{i+1})/2\)。
3. 对每个候选阈值计算划分后的信息增益或增益比。
4. 选择最好的阈值作为该节点的测试条件。

6.9 剪枝：防止过拟合

树长得太深时，可能把训练集里的偶然噪声也记住，导致新样本表现变差。C4.5 常配合后向剪枝：先长出较完整的树，再自底向上检查某些子树是否应替换为叶节点。如果替换后验证误差或估计泛化误差更好，就剪掉该子树。

6.10 2024真题同型例题：两特征数据集完整计算

2024第5题的数据集如下。类别 Y 有3个，N 有3个，所以总体最混杂：

第一步：总体熵

第二步：按特征 A 划分

\(A=T\) 子集有 N,N,Y；\(A=F\) 子集有 N,Y,Y。两个子集都是 2:1 混合，熵相同：

A 的取值比例是 3:3，所以划分熵为 \(H_A(D)=1\)，信息增益比约为 \(0.082\)。

第三步：按特征 B 划分

\(B=T\) 子集有 N,N,Y,Y，熵为1；\(B=F\) 子集有 Y,N，熵也为1：

如果题目继续要求画树

根节点选 A 后，两个分支都可以继续用 B 完全分开：

也就是说这个训练集的类别规律等价于“\(A\) 与 \(B\) 不同时为 Y，相同时为 N”。但考试第一问通常只要求第一步选哪个特征，别忘了把信息增益和信息增益比都列出来。

7. 考场作答模板

7.1 \(\alpha\)-\(\beta\) 剪枝模板

1. 标层：根为 MAX / MIN，后续交替。
2. 从左到右访问叶子，不要擅自换顺序。
3. MAX 节点维护下界 alpha：已看孩子的最大值。
4. MIN 节点维护上界 beta：已看孩子的最小值。
5. 继承祖先边界；比较对象不只父节点。
6. 若 alpha >= beta：剪去当前节点剩余未访问孩子，并在图上画叉。
7. 所有未剪部分算完后，在每个内部节点旁写最终值。
8. 根节点按 MAX / MIN 规则选最终走步。

7.2 A*/修正A*模板

表格列：step | OPEN | CLOSED | fm | NEST | expand | generated/updated | parent
普通 A*: 每步选 OPEN 中 f=g+h 最小节点。
修正 A*: 先找 NEST={n in OPEN | f(n)<fm};
          NEST 非空选其中 g 最小，否则选 OPEN 最小 f 并更新 fm。
结束：被选中的节点是目标，而不是目标刚生成。
路径：目标沿父指针回溯到起点。

7.3 MCTS / UCT模板

四步：选择 -> 扩展 -> 模拟 -> 回传。
节点统计：访问次数 N，累计收益 W，平均收益 Q=W/N。
UCT：I_j = Xbar_j + sqrt(2 ln n / T_j(n))。
含义：第一项是利用，第二项是探索。
做题：对每个候选孩子算 I_j，选最大的继续向下。

7.4 AlphaGo模板

一次模拟收益：v_i(s)=lambda*value(s)+(1-lambda)*rollout(s)。
平均收益：Q(s_a)=sum_i v_i(s_a)/n。
探索项：u(s_a)=c*p(s_a)*sqrt(N(s))/(N(s_a)+1)。
选择：比较 Q(s_a)+u(s_a)。
解释：value 来自估值网络；rollout 是快速模拟；p 来自策略网络。

7.5 模拟退火模板

当前能量 Ecur。
对每个候选 Enew:
    Delta = Enew - Ecur。
    若 Delta <= 0: 接受，Ecur = Enew。
    若 Delta > 0: p = exp(-Delta/T)。若随机数 r < p 接受，否则拒绝。
接受率 = 接受次数 / 尝试次数。
注意：拒绝后 Ecur 不变。

7.6 遗传算法模板

轮盘赌：
1. 求总适应值 F。
2. 每个个体概率 p_i=f_i/F。
3. 写累积区间。
4. 每个随机数落在哪个区间，就选择哪个个体。

确定性：
1. 期望复制数 e_i=N f_i/F。
2. 先取整数部分。
3. 剩余名额按小数部分从大到小补足。
4. 后续按题目给定交叉/变异规则操作。

7.7 ID3 / C4.5模板

ID3：
1. 统计总数据集 D 的类别数量，算 H(D)。
2. 对每个特征 A，按取值分组 D_i。
3. 每组算 H(D_i)，加权得 H(D|A)。
4. 信息增益 g(D,A)=H(D)-H(D|A)。
5. 选 g 最大的特征作为当前节点。
6. 分支纯净则标叶；不纯则递归。
7. 若特征用完、子集为空或增益低于阈值，标多数类。

C4.5：
1. ID3 的问题：偏好多取值属性，不能直接处理连续属性。
2. 信息增益比 g_R(D,A)=g(D,A)/H_A(D)。
3. 连续属性用阈值 A<=t / A>t 划分。
4. 防止过拟合：后向剪枝。

7.8 2024策略网络/softmax模板

输入：棋局特征 x_i；输出：每个候选落子点概率 p_j；MCTS 次数 m_j。
1. net_j = sum_i w_ji x_i + b_j。
2. p_j = exp(net_j) / sum_k exp(net_k)。
3. M = sum_k m_k，q_j = m_j / M。
4. L = - sum_j q_j log p_j。
5. softmax + 交叉熵结论：dL/dnet_j = p_j - q_j。
6. dL/dw_ji = (p_j - q_j) x_i；dL/db_j = p_j - q_j。
7. 梯度下降：w_ji <- w_ji - eta (p_j - q_j)x_i。

8. 自测题与复习路线

8.1 一天速成路线

1. 1小时：读第1节题型地图，知道每题交什么。
2. 2小时：练 A*/修正A*，至少手算2个图。
3. 2小时：练 \(\alpha\)-\(\beta\) 剪枝，重点是不齐树、从左到右、祖先边界。
4. 1小时：练 MCTS/UCT，至少会代入 \(\overline X_j+\sqrt{2\ln n/T_j(n)}\)。
5. 1小时：背 AlphaGo 的 \(v_i\)、\(Q\)、\(u\) 三个公式，以及 2024 softmax策略网络的 \(p_j-q_j\) 梯度。
6. 2小时：练 ID3/C4.5，至少完整算一次信息增益并能解释信息增益比。
7. 30分钟：背模拟退火、遗传算法模板。

8.2 三天稳妥路线

8.3 考前检查清单

• 我能解释 \(g,h,f\)，并知道A*何时结束。
• 我能写出单调性条件，并说明单调推出A*条件、避免重复扩展。
• 我能按修正A*规则计算 NEST 和 \(f_m\)。
• 我能独立做一棵不齐树的 \(\alpha\)-\(\beta\) 剪枝，并说明剪枝依据来自祖先边界。
• 我能写出 MCTS 四步和 UCT 中探索/利用两项。
• 我能说清 AlphaGo 中 \(value(s)\)、\(rollout(s)\)、\(Q(s_a)\)、\(u(s_a)\)、\(p(s_a)\) 的作用，并能把 MCTS 次数 \(m_j\) 转为策略网络目标 \(q_j\)。
• 我能从数据表中算出 \(H(D)\)、\(H(D\mid A)\)、\(g(D,A)\)，并选出 ID3 根节点。
• 我能解释 C4.5 为什么使用信息增益比，以及如何处理连续属性和过拟合。
• 我能根据温度、能量差和随机数判断模拟退火是否接受。
• 我能根据适应值和随机数完成遗传算法选择步骤。

8.4 最小自测题

9. 来源与取舍说明

本版在原 HTML 的基础上重写和扩充了“对抗搜索与 \(\alpha\)-\(\beta\) 剪枝”“蒙特卡洛方法与 MCTS”“AlphaGo”三节，并按补充笔记替换为“决策树：ID3 与 C4.5”内容。本次又根据 2024 真题第1、2、5、6题补充了不齐 \(\alpha\)-\(\beta\) 树、修正A*完整表、决策树小数据集计算、softmax策略网络训练推导；按要求未纳入第3题 SVM 与第4题 GoogleNet/Inception。

2013年及以前的旧题包含 AO*、专家系统、归结、逆向演绎、SOM 等内容。根据当前复习重点，本指南优先保留 A/A*/修正A*、\(\alpha\)-\(\beta\) 剪枝、MCTS、AlphaGo、模拟退火、遗传算法、ID3/C4.5。已单独整理的内容没有再放入本文件，以免挤占核心题型复习时间。

AlphaGo 部分采用补充笔记中的写法：一次模拟收益 \(v_i(s)=\lambda value(s)+(1-\lambda)rollout(s)\)，平均收益 \(Q(s_a)\)，以及带策略先验的探索项 \(u(s_a)=c p(s_a)\sqrt{N(s)}/(N(s_a)+1)\)。决策树部分采用笔记中的熵、条件熵、信息增益、ID3递归终止条件、C4.5信息增益比和后向剪枝框架。