算法设计与分析 · 期末复习

外观

05 贪心算法与拟阵 ​

本章对应考试中的：G1 多机调度（样题1/试卷1，15 分）、G2 方格阵最大权路径（样题2/试卷2，15 分）、G3 任务指派（试卷4，15 分）、G4 贪心最优例子（试卷7）、简答 Q8 拟阵（Prim/Kruskal 是否构成拟阵，高频）、R3 Huffman 最少期望提问（样题1/样题2）、作业 O3（Prim 与 Kruskal 的集成）。

核心考点 ​

贪心（greedy）：每一步都做"当前看起来最好"的选择，并且选了就不反悔，希望这样一路选下去得到全局最优。

本章要能：写贪心算法（G1～G3，含伪代码、复杂度、说明是否最优）；答贪心的概念题（G4、贪心选择性质）；答拟阵这道高频简答（Q8，判断 Prim/Kruskal 是否构成拟阵）；用 Huffman 树 求最少期望提问次数（R3）。

从零开始的前置知识 ​

贪心算法的两个前提 ​

一个问题能用贪心法正确求解，需要两个性质：

  1. 贪心选择性质（greedy-choice property）：全局最优解可以通过"每一步都取局部最优"这一系列选择达到。
  2. 最优子结构（optimal substructure）：做完当前这一步贪心选择后，剩下的子问题的最优解，加上这一步的选择，就是原问题的最优解。

⚠️ 关键：不是所有问题都有贪心选择性质。贪心选了就不回头，所以经常得不到最优解。能不能用贪心、贪心对不对，是需要判断/证明的（其理论依据就是后面的"拟阵"）。所以贪心大题常注明"不一定要找到最优解"。

贪心和动态规划的区别 ​

贪心动态规划（04）
每一步只选当前最优，不回头考虑所有可能选择并比较
是否最优不一定（需满足贪心选择性质才行）保证最优
速度快慢一些

一句话：拿不准能不能贪心，就用动态规划保险。

什么是最小生成树（MST） ​

最小生成树（minimum spanning tree, MST）：在一个连通的、带权的无向图里，选出一些边，把所有顶点连起来、不形成环、且所选边的总权值最小。求 MST 有两个经典贪心算法：

  • Prim 算法：从任意一个顶点出发，每次把"连接【已选顶点集合】和【外部顶点】之间权值最小的那条边"加进来，直到所有顶点都被连上。它是按顶点扩展的。
  • Kruskal 算法：把所有边按权值从小到大排序，依次考察每条边，只要加入它不会形成环就加入，直到选够 n−1 条边。它是按边排序的。

答题模板 ​

【贪心策略】每一步按什么标准、选什么（说清排序依据和选取规则）。
【伪代码】通常是：排序（或建堆）+ 循环依次贪心选取。
【复杂度】排序 O(n log n) + 选取过程，合计 O(...)。
【是否最优】贪心不一定最优；若有已知近似比就给出（如列表调度 2-1/m）；
            若要保证最优需改用动态规划（给出对应的 DP 转移方程）。

逐题精解 ​

G1 多机调度 / 最小化工期（样题1/试卷1，15 分） ​

原题：m 台机器、n 项作业，作业 j 的处理时间为 tj。把每项作业分给一台机器，机器 Mi 的负载 Ti=∑j∈A(i)tj（A(i) 是分给 Mi 的作业集）。工期 T=maxiTi（最大负载）。求使工期 T 最小的分配方案。

贪心策略（LPT，最长处理时间优先）：把作业按处理时间从大到小排序，然后依次把每个作业分给当前负载最小的机器。用一个最小堆（一种能快速取出最小值的数据结构）维护各机器的当前负载。

text
把作业按 t_j 从大到小排序
所有机器负载初始化为 0，放入最小堆
for 每个作业 j（按降序）:
    取出当前负载最小的机器 Mi          // 堆顶
    把作业 j 分给 Mi：load(Mi) += t_j
    把 Mi 放回堆
return max_i load(Mi)                  // 最大负载即工期

演示（处理时间 [7,4,3,2,2,2]，m=3 台，已降序）：

  • 7 → M1（负载 7）；4 → M2（4）；3 → M3（3）；
  • 下一个 2 → 当前最小是 M3(3) → M3 变 5；2 → 最小 M2(4) → M2 变 6；2 → 最小 M3(5) → M3 变 7。
  • 负载：M1=7、M2=6、M3=7，工期 =max=7。

复杂度：排序 O(nlog⁡n)，每个作业一次堆操作 O(log⁡m)，合计 O(nlog⁡n+nlog⁡m)。

是否最优：贪心不保证最优，但有性能保证（近似比 = 贪心解与最优解的比值，详见 08_下界_近似算法与性能比.md）：普通列表调度近似比为 2−1m；按降序的 LPT 近似比为 43−13m。

G2 方格阵最大权路径（样题2/试卷2，15 分） ​

原题：N×M 方格阵，每格有一个权值。每次只能向上或向右移动，找一条从左下角到右上角、所经过权值之和最大的路径。

贪心策略：每一步在"上邻格"和"右邻格"中选权值较大的那个前进，直到右上角。

text
i ← 左下角格; sum ← w[i]
while 未到右上角:
    在(上邻格, 右邻格)的可行格中选权值较大者 next
    sum ← sum + w[next]; i ← next
return sum

复杂度：每步走一格，共走 N+M 步左右，O(N+M)。

⚠️ 本题贪心不保证全局最优：当前选了较大的邻格，可能错过后面更大的权值。若要保证最优应改用动态规划：设 f(i,j) 为到达格 (i,j) 的最大权值和，则

f(i,j)=w(i,j)+max{f(i−1,j), f(i,j−1)},

复杂度 O(NM)。考试若明确要求贪心，就按上面贪心法作答，并写明它不保证最优、最优应用 DP。

G3 任务指派（试卷4，15 分） ​

原题：n 项任务、n 个人，效率矩阵 C 的元素 cij 表示第 i 人完成第 j 项任务所需时间。每人做一项、每项一人，求总时间最少的分派（不一定要找到最优解）。

贪心策略：从第 1 个人到第 n 个人，每人依次在当前尚未被指派的任务中，挑选自己执行时间最小的那一项。

text
已指派任务集合 ← 空
for i ← 1 to n:                        // 逐个人
    在未指派任务中找 c[i][j] 最小的任务 j
    把任务 j 指派给第 i 人；把 j 加入已指派集合
return 总时间

复杂度：每个人扫一遍剩余任务 O(n)，共 n 人，O(n2)。

是否最优：贪心只得近似解、不保证最优。求最优需用匈牙利算法，复杂度 O(n3)。

G4 贪心最优例子（试卷7，概念） ​

原题：举一个有最优解的贪心算法例子。

答案：Dijkstra 单源最短路径算法、Huffman 编码、最小生成树的 Prim/Kruskal 算法、活动安排问题等。这些问题都具备贪心选择性质，贪心能得到最优解。

简答 Q8：Prim/Kruskal 是否构成拟阵（高频） ​

原题：说明最小生成树的 Prim 算法和 Kruskal 算法是否具有拟阵的结构，即说明这两个算法对应的二元组 M=(S,I) 是否满足遗传性质和交换性质。

前置：什么是拟阵。 拟阵（matroid） 是一个二元组 M=(S,I)，其中 S 是一个有限集合，I 是 S 的一些子集组成的族（这些子集称为独立集），并且满足两条性质：

  1. 遗传性（hereditary property）：若 A∈I（A 是独立集）且 B⊆A（B 是 A 的子集），则 B∈I。也就是"独立集的任何子集也是独立集"。（空集 ∅ 是独立集。）
  2. 交换性（exchange property）：若 A,B∈I 且 |A|<|B|（A 的元素比 B 少），则存在某个 x∈B−A，使得 A∪{x}∈I。也就是"较小的独立集总能从较大的独立集里借一个元素进来，仍保持独立"。

拟阵的意义：如果一个问题能套上拟阵结构，那么贪心算法在它上面一定能得到最优解。 这就是贪心为什么有时对、有时错的理论根源。

答案：

Kruskal —— 满足拟阵（称为图拟阵 graphic matroid）。 取 S=E（图的全部边），I= 所有"不含环的边子集（即森林）"。

  • 遗传性成立：空集是森林；一个森林去掉任意一些边，仍然没有环，还是森林。所以独立集（森林）的子集仍是独立集。
  • 交换性成立：若森林 I 和 J 满足 |I|<|J|，则 J 的边更多、它把顶点连成的"连通块"更少，于是 J 中必有一条边 e∈J−I，把它加到 I 上不会形成环，即 I∪{e} 仍是森林。
  • Kruskal 按权从小到大、只要不成环就加边，正是"在图拟阵上做贪心"，所以 Kruskal 对应一个拟阵，贪心得到最优 MST。

Prim —— 不满足拟阵。 Prim 从一个顶点出发、按"到已选顶点集合的最小边权"扩展，它的"已选边集合"不是用单纯的子集关系定义的独立集：

  • 遗传性不成立：从 Prim 选出的（部分）生成树里去掉一条边，会变成不相连的森林片段，不符合 Prim "从单一顶点逐步连通扩展"的结构要求。
  • 交换性不成立：Prim 的加边规则是基于"与已选顶点集合的距离"，而不是拟阵那种通用的元素交换规则。
  • 所以 Prim 对应的 M=(S,I) 不能同时满足遗传性与交换性，不构成拟阵。

一句话记忆：Kruskal 满足拟阵（图拟阵），Prim 不满足。 这是历年高频简答，务必记住结论和"遗传性、交换性"两个词。

R3 Huffman 最少期望提问次数 ​

原题（版本 A）：一副牌由 1 张 A、2 张 2、3 张 3、……、9 张 9 组成。抽出一张，用一连串"是/否"问题确定它的点数，设计使期望提问次数最少的策略。

原题（版本 B）：黑盒内有 1 红、2 蓝、3 绿、4 黄、5 黑、6 白、7 紫共 7 种球，随机拿一个，用"是/否"问题确定颜色，求期望提问次数最少的策略。

前置：这是 Huffman 编码问题。 每一个"是/否"问题相当于二叉判定树里的一次分叉，一个结果（某点数/某颜色）对应树里的一个叶子，确定它所需的提问次数 = 它在树中的深度。期望提问次数 =∑(该结果频数×它的深度)总频数。要让它最小，就要给频数大的结果分配浅的深度——这正是 Huffman 树 干的事。

Huffman 树构造法：把所有频数看成一堆数，每次取出最小的两个合并成一个新结点（新结点的频数 = 两者之和），放回堆里，重复直到只剩一个根。各结果的码长（深度）由树决定。所有合并值之和，正好等于 ∑(频数×深度)。

版本 B 手算（频数 {1,2,3,4,5,6,7}，总和 28）：每次合并最小两个，记下合并值：

1+2=3,3+3=6,4+5=9,6+6=12,7+9=16,12+16=28.

合并值之和 =3+6+9+12+16+28=74。故

期望提问次数=7428≈2.64 次.

（各颜色码长：频数 1、2 的为 4 次，频数 3、4、5 的为 3 次，频数 6、7 的为 2 次；验证 1⋅4+2⋅4+3⋅3+4⋅3+5⋅3+6⋅2+7⋅2=74。）

版本 A 手算（频数 {1,2,…,9}，总和 45）：

1+2=3, 3+3=6, 4+5=9, 6+6=12, 7+8=15, 9+9=18, 12+15=27, 18+27=45.

合并值之和 =3+6+9+12+15+18+27+45=135。故

期望提问次数=13545=3.0 次.

结论：按频数构造 Huffman 树得到的判定策略，就是期望提问次数最少的策略。

作业 O3：Prim 与 Kruskal 的集成（HW1） ​

原题：Prim 与 Kruskal 设计思路不同，导致对不同问题实例效率不同。简述：1）如何把两种算法集成以适应不同输入；2）如何评价这一集成的意义。

答案：

  • 效率差异：Prim 基于顶点扩展，适合顶点相对少、边很多的稠密图（边数 |E| 接近 |V|2）；Kruskal 基于边排序，适合边少的稀疏图。
  • 集成方法：先判断输入图是稀疏还是稠密（例如比较边数 |E| 与 |V|2 的关系），稠密就调用 Prim、稀疏就调用 Kruskal。
  • 意义：没有对所有实例都最优的"万能算法"，应当具体问题具体分析，按图的特征（稀疏/稠密）选择合适的算法，才能充分发挥效率、更好地解决实际问题。

高频陷阱 / 易错点小结 ​

  1. 贪心不一定最优：G2 方格路径、G3 任务指派都不保证最优，作答要点明，并给出"要最优就用 DP / 匈牙利算法"。
  2. 拟阵结论：Kruskal 满足、Prim 不满足；答题必须出现"遗传性""交换性"两个词。
  3. Huffman 每次合并最小两个，期望次数 = 合并值之和 ÷ 总频数；别忘了除以总频数。
  4. 多机调度用 LPT（先排降序），并用最小堆维护负载；近似比 43−13m。
  5. 贪心 vs DP：题目说"不一定要最优"就大胆贪心；说"求最优"且没说贪心，优先 DP。

自测清单 ​

  • [ ] 说出贪心的两个前提（贪心选择性质、最优子结构）。
  • [ ] 写出多机调度 LPT 的伪代码与复杂度 O(nlog⁡n+nlog⁡m)。
  • [ ] 说清方格路径贪心不最优、并写出对应 DP 方程。
  • [ ] 默写拟阵定义（遗传性 + 交换性），答出 Kruskal 满足、Prim 不满足。
  • [ ] 对频数 {1,2,3,4,5,6,7} 构造 Huffman 树，得期望提问 ≈2.64。
  • [ ] 说出 Prim 适稠密图、Kruskal 适稀疏图，以及集成的意义。
赣ICP备2026014065号-1