《算法设计与分析》期末复习题汇总

课程：算法设计与分析（北京航空航天大学 / 计算机科学系）

整理说明：本文档由 data/raw/ 中历年试卷、答案、作业、复习资料经 OCR/识别后，按题型归类、去重、题答关联整理而成。

编写原则：保留每道题的原始题面文字（仅纠正识别错误，不做简化改写）；同一题在多份资料中重复出现时，给出一份完整原题并标注其全部出现来源与年份；有参考答案的附在题后。

原始逐文件识别结果完整保留在 data/markdown/<来源>/ 目录下，本文件为汇总复习版。

生成日期：2026-06-27

整理人：ZR with Claude Code

---

〇、资料来源清单与年份标注

来源标签	原始文件	年份 / 说明	是否含答案
2011期末	算法11年期末考试卷.pdf/.doc	北航 2010–2011 学年第二学期（2011-06-09）	✅ 有答案 doc
2011影印	算法2011影印版.pdf	2011 影印（扫描）试卷	部分（见历年答案）
2012影印	算法2012影印版.pdf / -答案.pdf	2012 影印（扫描）试卷 + 答案	✅
2012答案	2012年答案.doc	2012 判断题 + 多数元素答案	✅ 仅答案
2013	算法2013.doc	北航 2013–2014 学年第一学期（2013-12-24，A 卷）	❌
2020	2020试卷_Word.doc	北航 2019–2020 学年第二学期（2020-07-02，A 卷）	❌
merged	merged(2).pdf	一套含完整手写解答的综合卷	✅ 全解
HW1	ZY1806707_石发强_HW1.pdf	作业 1（含解答）	✅ 全解
试卷1	试卷1.pdf/.doc	与"样题1"同族	❌
试卷2	试卷2.pdf/.doc（+ 第三题分析.doc）	与"样题2"同族	第三题有分析
试卷3	试卷3.pdf（+ 参考答案1/2.doc）	与"样题1"同族	参考答案为题面重排，无实际答案
试卷4	试卷4本科试题.pdf/.doc（+ 答案.doc）	北航 2008–2009《算法与数据结构(2)》（2009-06-08）	✅
试卷5	试卷5.pdf/.doc（+ 答案.doc）	计算机科学系《算法设计与分析》A 卷（2002-01-11，98 级）	部分
试卷6	试卷6.doc	中英双语算法卷（含 04 研 / 02 本科题）	❌
试卷7	试卷7.doc	考点提纲 / 简要回忆卷	提纲
样题1	样题1.pdf	复习样题（≈ 试卷3 / 试卷1）	❌
样题2	样题2.pdf	复习样题（≈ 试卷2）	❌
历年汇总	算法分析设计历年题目.docx	历年题目题库（判断 16 / 问答 5 / 分治 2 / DP 2 / 分支 2）	配"历年答案"
历年答案	算法设计与分析历年题目答案（修改版）.pdf	历年题目答案（原作者注明"错了概不负责"）	✅
算法整理	算法整理(1).docx	学生整理的判断 / 简答 / 大题合集（判断题含答案）	部分
微信图片1/2	微信图片_20250305100035/41.jpg	Kruskal / Prim 是否满足拟阵的解答截图	✅ 答案
微信图片3	微信图片_20250305100046.jpg	2020 同型卷第 2 页照片	❌

去重说明：样题1 ≈ 试卷3 ≈ 试卷1（同族，仅个别题不同）；样题2 ≈ 试卷2；2012影印 ≈ 2013 ≈ 历年汇总（同模板）。下文已合并同类题并标注其出现来源；题面文字保持原样。

---

一、判断题库（合并去重 · 原文保留 · 附答案与解析）

题型说明：请在正确的陈述前面括号中打 √，在错误的陈述前面括号中打 ×。

判断题在各年高度重复。下面按知识点把措辞不同的题分别列出（措辞差异本身常是考点，故不合并），完全相同者只列一次并汇总来源。

答案综合各份答案键与算法理论给出。原"历年答案（修改版）"作者自注"错了概不负责"，故凡有概念分歧处以算法理论为准并加注。

1.1　渐进记号与复杂度

1.　$f(n)=O(f(n))$

• ✓ 对　·　大 O 自反。　·　来源：样题1 试卷1 试卷3 样题2 试卷2

2.　$O(f(n))+O(g(n))=O(max\{f(n),g(n)\})$

• ✓ 对　·　两项之和的阶由较大者决定。　·　来源：样题1 试卷1 试卷3

3.　$O(f(n))+O(g(n))=O(min\{f(n),g(n)\})$

• ✗ 错　·　应为 $max$。　·　来源：样题2 试卷2 2012影印 2013 历年汇总 merged 算法整理

4.　若 $f(n)=\mathrm{\Omega }(g(n))$，$g(n)=\mathrm{\Omega }(h(n))$，则 $f(n)=\mathrm{\Omega }(h(n))$

• ✓ 对　·　$\mathrm{\Omega }$ 的传递性。　·　来源：历年汇总 2011影印 算法整理

5.　若 $f(n)=O(g(n))$，则 $g(n)=\mathrm{\Omega }(f(n))$

• ✓ 对　·　$O$ 与 $\mathrm{\Omega }$ 互为对偶。　·　来源：2012影印 2013 试卷4 历年汇总

6.　若 $f(n)=\mathrm{\Omega }(g(n))$，则 $g(n)=\mathrm{\Omega }(f(n))$

• ✗ 错　·　方向相反，应为 $g(n)=O(f(n))$。　·　来源：算法整理

7.　$max(f(n),g(n))=\mathrm{\Theta }(f(n)+g(n))$

• ✓ 对　·　非负函数下 $max$ 与求和同阶。　·　来源：试卷4

8.　$2^{n+1}=O(2^n)$ 且 $2^n=O(2^{2n})$

• ✓ 对　·　$2^{n+1}=2\cdot 2^n$；$2^n\le 2^{2n}$。　·　来源：2011期末

9.　$2^{n+1}=O(2^n)$ 且 $2^{2n}=O(2^n)$

• ✗ 错　·　$2^{2n}=4^n\ne O(2^n)$。　·　来源：试卷4

10.　若求解问题 $p$ 的一个算法 A 的复杂性为 $f(n)$，则 $p$ 的复杂性 $C(p)\le f(n)$

• ✓ 对　·　任一算法都给出问题复杂度的一个上界。　·　来源：样题1 样题2 试卷1 试卷2 试卷3

11.　通常来说，算法的最坏情况的时间复杂性比平均情况的时间复杂性容易计算

• ✓ 对　·　平均情况需对输入分布求期望，更难。　·　来源：2012影印 2013 merged 历年汇总

1.2　排序与查找下界

12.　合并排序使用了分治策略

• ✓ 对　·　二分 + 合并。　·　来源：2011期末

13.　快速排序的 worst case 出现于输入数组恰好为已按非降序排列的情况（假设输出的排序结果也要求是非降序）

• ✓ 对　·　取首/尾元素为枢轴的确定性快排，已序输入退化为 $O(n^2)$。　·　来源：样题2 试卷2

14.　随机化快速排序的 worst case 出现于输入数组恰好为已按非降序排列的情况（假设输出的排序结果也要求是非降序）

• ✗ 错　·　随机选枢轴后，最坏情况与具体输入无关。　·　来源：样题1 试卷1 试卷3

15.　快速排序算法的平均时间复杂度是 $O(n\log n)$，使用随机化快速排序算法可以将平均时间复杂度降得更低

• ✗ 错　·　随机化只消除对输入的依赖，平均阶仍为 $O(n\log n)$。　·　来源：2011期末 2012影印 2013 试卷4 merged 历年汇总

16.　基于比较的排序问题的下界是 $0.5n\log n$

• ✓ 对　·　即 $\mathrm{\Omega }(n\log n)$，判定树高度下界 $\log (n!)=\mathrm{\Theta }(n\log n)$。　·　来源：样题1 试卷3（样题2 试卷2 此处识别模糊作"$(\log )n$"，应为 $\mathrm{\Omega }(n\log n)$）

17.　基于比较的寻找数组 $A[1\dots n]$ 中最大值元素和最小值元素问题的下界是 $n/2$

• ✓ 对　·　$n/2$ 是一个合法（非紧）下界；紧下界为 $\lceil 3n/2\rceil -2$。　·　来源：2011期末（答案标 √）

18.　基于比较的寻找数组 $A[1\dots n]$ 中最大值元素问题的下界是 $\mathrm{\Omega }(n/3)$

• ✗ 错　·　找最大值需 $n-1$ 次比较，紧下界为 $\mathrm{\Omega }(n)$，$\mathrm{\Omega }(n/3)$ 作为"问题下界（紧下界）"的判断为错。　·　来源：2012影印 2013 试卷4 2011影印 历年汇总 算法整理

19.　基于比较的寻找数组 $A[1\dots n]$ 中最小值元素问题的下界是 $\mathrm{\Omega }(n/2)$

• ✓ 对　·　找最小需 $n-1$ 次比较，$\mathrm{\Omega }(n/2)$ 是合法下界。　·　来源：merged

1.3　算法策略概念

20.　回溯法用深度优先法搜索状态空间树

• ✓ 对　·　回溯法本质即 DFS。　·　来源：merged 算法整理

21.　回溯法用深度优先或广度优先法搜索状态空间树

• ✗ 错　·　回溯法仅用 DFS；BFS 式搜索属分支限界法。　·　来源：样题1 样题2 试卷1 试卷2 试卷3 试卷4

22.　回溯法用深度优先法或广度优先法搜索状态空间树

• ✗ 错　·　同上，仅 DFS。　·　来源：2012影印 2013 历年汇总

23.　动态规划算法通过增加空间复杂性来降低时间复杂性

• ✓ 对　·　以表存子问题解，空间换时间。　·　来源：样题1 样题2 试卷1 试卷2 试卷3

24.　在动态规划中，各个阶段所确定的策略就构成一个策略序列，通常称为一个决策

• ✗ 错　·　该序列应称"策略(policy)"；单个阶段的选择才叫"决策(decision)"。　·　来源：2012影印 2013 历年汇总

25.　贪婪技术所做的每一步选择所产生的部分解，不一定是可行性的（变体："贪心法所做的每一步选择所产生的部分解，不一定是可行性的"）

• ✗ 错　·　贪心每步均在可行范围内做选择，部分解保持可行。　·　来源：历年汇总 算法整理（变体见 2012影印 2013）

26.　贪心算法通过增加空间复杂性来减少时间复杂性

• ✗ 错　·　"空间换时间"是动态规划的特征，不是贪心。　·　来源：试卷4

27.　经典贪心算法所做的每一步选择，可以基于局部信息，也可以基于全局信息

• ✓ 对（按 merged 键）　·　来源：merged

28.　一个正确的算法，对于每一个合法输入，都会在有限的时间内输出一个满足要求的结果

• ✓ 对　·　正确性 + 有限性。　·　来源：2012影印 2013 历年汇总

1.4　概率算法

29.　拉斯维加斯算法有时不能给出问题的解，但只要给出解就是正确的

• ✓ 对　·　Las Vegas 的定义。　·　来源：样题2 试卷2

30.　Las Vegas 算法只要给出解就是正确的

• ✓ 对　·　同上。　·　来源：历年汇总 2011影印

31.　Monte Carlo 算法有时不能给出问题的解，但只要给出解就是正确的

• ✗ 错　·　此为 Las Vegas 的性质；Monte Carlo 总能给出解但可能错误。　·　来源：样题1 试卷1 试卷3 算法整理

1.5　P / NP 理论（高频陷阱区）

32.　所有问题当中最难的一组问题被称为 NP 完备 (NP-Complete) 问题

• ✗ 错　·　NP 完全是 NP 类内最难，并非"所有问题"中最难；NP-hard 可更难。　·　来源：样题1 样题2 试卷1 试卷2 试卷3

33.　NP 完全问题比其它所有 NP 问题都要难

• ✗ 错　·　NP 完全问题彼此等难（互相多项式归约），只是"至少和其它 NP 问题一样难"，并非严格更难。　·　来源：2012影印 2013 merged 历年汇总

34.　NP 完备 (NP-Complete) 问题是所有 NP 问题中最难的，目前还没有找到用于解决 NP 完备问题的多项式算法

• ✗ 错　·　症结在"比其它所有都难"的含义——NP 完全问题之间等难；后半句"未找到多项式算法"本身属实。　·　来源：2011期末

35.　P 类和 NP 类问题的关系用 $P\subset NP$ 来表示是错误的

• ⚠️ 见解析　·　已知 $P\subseteq NP$；$P⊊NP$（真包含）尚未证明，故断言真包含缺乏依据。与第 36 条对照理解。　·　来源：样题1 样题2 试卷1 试卷2 试卷3 2012影印 2013 历年汇总

36.　P 类和 NP 类问题的关系不可以用 $P\subset NP$ 来表示

• ✓ 对（按 merged 键）　·　来源：merged

37.　如果一个问题是 NP 问题，则它一定不是 P 问题

• ✗ 错　·　$P\subseteq NP$，P 问题也是 NP 问题。　·　来源：2011期末

38.　如果一个问题不是 NP 问题，那么它有可能是 P 问题

• ✗ 错　·　非 NP $\Rightarrow$ 非 P（因 $P\subseteq NP$）。　·　来源：试卷4

39.　直观地讲，P 类问题是易解的问题；而 NP 问题是易被验证的问题

• ✓ 对　·　标准直观刻画。　·　来源：试卷4

40.　若 P2 多项式时间转化为 (polynomially transforms to) P1，则 P2 至少与 P1 一样难

• ✗ 错　·　转化方向表示 P1 至少和 P2 一样难（$P_2{\le }_p{P}_1$）。　·　来源：2012影印 2013 merged 历年汇总

41.　下列问题是一个判定问题：给定一个合取范式 Γ，对 Γ 中的所有逻辑变量求一组真值赋值，使得在该组真值赋值下为真

• ✗ 错　·　这是搜索/构造问题（求赋值）；判定问题只问 yes/no（是否存在）。　·　来源：2011期末 试卷4

42.　已知团问题（Clique problem）为 NP 问题，那么下列问题是一个判定问题：给定一个图 G，求 G 中最大团的尺寸（size）K

• ✗ 错　·　求最大团尺寸是优化问题，不是判定问题。　·　来源：试卷1 算法整理

1.6　近似算法

43.　一个完全多项式近似方案是一个近似方案 $\{A_{\epsilon }\}$，其中每一个算法 $A_{\epsilon }$ 在输入实例 I 的规模的多项式时间内运行

• ✗ 错　·　FPTAS 要求关于输入规模 $n$ 与 $1/\epsilon$ 都是多项式；此处漏了 $1/\epsilon$。　·　来源：2012影印 2013 历年汇总 2011影印

44.　若近似算法 A 求解某极小化问题一实例的解为 $s_a$，且已知该问题的最优解为 $s_a/3$，则该近似算法的性能比为 3

• ✗ 错（陷阱）　·　单个实例的比值 $=3$ 只能作为性能比的下界；算法性能比是对所有实例的最坏比值（上确界），不能由一个实例断定为 3。　·　来源：2012影印 2013 历年汇总

45.　若近似算法 A 求解某极大化问题一实例的解为 $s_a$，且已知该问题的最优解为 $2s_a$，则该近似算法的性能比为 2

• ✗ 错（陷阱）　·　同上：单实例比值不等于算法性能比。　·　来源：merged

本区高频陷阱小结：第 33／34（NP 完全"比所有 NP 都难"→错，等难）、第 44／45（性能比由单实例断定→错，须取所有实例的最坏比值）是历年最常考的判断陷阱。

---

二、选择题

来源：试卷5（2002 A 卷）　|　本题包含 12 个小题，占 24 分；请将正确答案填写在题目左侧的括号内。

（题面照录；粗体为参考答案。）

1.　分支限界法与回溯法都是在问题的解空间树 T 上搜索问题的解，二者（　C　）。

 A．求解目标不同，搜索方式相同  B．求解目标不同，搜索方式也不同  C．求解目标相同，搜索方式不同  D．求解目标相同，搜索方式也相同

2.　回溯法在解空间树 T 上的搜索方式是（　A　）。

 A．深度优先　　B．广度优先　　C．最小耗费优先　　D．活结点优先

3.　回溯算法和分支限界法的问题的解空间树不会是（　D　）。

 A．有序树　　B．子集树　　C．排列树　　D．无序树

4.　在对问题的解空间树进行搜索的方法中，一个活结点最多有一次机会成为活结点的是（　B　）。

 A．回溯法　　B．分支限界法　　C．回溯法和分支限界法　　D．回溯法求解子集树问题

5.　从活结点表中选择下一个扩展结点的不同方式将导致不同的分支限界法，以下除（　C　）之外都是最常见的方式。

 A．队列式分支限界法　　B．优先队列式分支限界法　　C．栈式分支限界法　　D．FIFO 分支限界法

6.　概率算法是一种非确定性地选择下一计算步骤的方法，力图消除问题复杂性与具体实例间的关联，以下算法中适合于求解问题近似解的是（　B　）。

 A．数值概率算法　　B．蒙特卡罗算法　　C．拉斯维加斯算法　　D．舍伍德算法

7.　（　B　）能够求得问题的解，但却无法有效地判定解的正确性。

 A．数值概率算法　　B．蒙特卡罗算法　　C．拉斯维加斯算法　　D．舍伍德算法

8.　下面算法实现的是素数测试，该方法使用的数学原理是（　A　）。

 A．费尔马小定理　　B．费尔马定理　　C．Wilson 定理　　D．二次探测定理

9.　以下关于判定问题难易处理的叙述中正确的是（　C　）。

 A．可以由多项式时间算法求解的问题是难处理的  B．需要超过多项式时间算法求解的问题是易处理的  C．可以由多项式时间算法求解的问题是易处理的  D．需要超过多项式时间算法求解的问题是不能处理的

10.　设 $f(N)$、$g(N)$ 是定义在正数集上的正函数，如果存在正的常数 $C$ 和自然数 $N_0$，使得当 $N\ge N_0$ 时有 $f(N)\le Cg(N)$，则称函数 $f(N)$ 当 $N$ 充分大时有上界 $g(N)$，记作 $f(N)=O(g(N))$，即 $f(N)$ 的阶（　A　）$g(N)$ 的阶。

 A．不高于　　B．不低于　　C．等价于　　D．逼近

11.　对于含有 $n$ 个元素的子集树问题，最坏情况下其解空间的叶结点数目为（　B　）。

 A．$n!$　　B．$2^n$　　C．$2^{n+1}-1$　　D．$\sum _{i=1}^{n}n!/i!$

12.　对于含有 $n$ 个元素的排列树问题，最坏情况下计算时间复杂性为（　C　）。

 A．$2^{n+1}-1$　　B．$\sum _{i=1}^{n}n!/i!$　　C．$n!$　　D．$2^n$

---

三、填空题

来源：试卷5（2002 A 卷）　|　本题包含 5 个小题，占 20 分，每空 1 分。配 试卷5答案。

1.　以下是对 x，y，z 三个数进行升序排序的一棵判定树，请在方框中填写相应的结果。

 【参考答案】 按比较 a:b、a:c、b:c 的结果填入各分支与叶结点的排序结论（如某叶为 b < a < c 等）。

2.　算法是由若干条指令组成的有序序列，并且具有（　）、（　）、（　）和（　）的性质。

 【参考答案】 输入、输出、确定性、有限性。

3.　评价算法的标准包括（　）、（　）以及正确性、简单性等。

 【参考答案】 时间复杂性、空间复杂性。

4.　下面是棋盘覆盖的分治策略算法（ChessBoard(...)，tile 为全局变量、初值 0）。由此算法可知，覆盖一个 $2^k\times 2^k$ 的特殊棋盘所需要的 L 型骨牌的个数为（　），算法时间复杂性 $T(k)=$（　）。

 【参考答案】 L 型骨牌个数 $=(4^k-1)/3$；时间复杂性 $T(k)=4T(k-1)+O(1)=O(4^k)$。

5.　若一个最优化问题的最优值为 $c^{\ast }$，求解该问题的一个近似算法所求得的近似最优解相应的目标函数值为 $c$，则将该近似算法的性能比定义为 $\eta =$（　）。

 【参考答案】 $\eta =max\{c/c^{\ast },c^{\ast }/c\}$（极小化问题取 $c/c^{\ast }$，极大化问题取 $c^{\ast }/c$，恒 $\ge 1$）。

---

四、简答 / 问答题（原题保留 · 按知识点归类 · 附参考答案）

来源遍布 2011期末 2012影印 2013 2020 历年汇总 merged 试卷4 试卷7 等。下面按知识点合并，每题给出原始题面（带分值），重复出现者标注全部来源。

4.1　数据结构与变治

Q1.（来源：2011影印 2012影印 2013 merged 历年汇总，本题 2–3 分）

二叉查找树属于减治策略的三个变种中哪一个的应用？什么情况下二叉查找树表现出最差的效率？此时的查找和插入算法的复杂性如何？

【参考答案】 属于**减治策略中"减去的规模可变（减可变规模）"**变种的应用。当树严格歪斜（退化为一条链，例如按有序序列依次插入）时表现出最差效率；此时查找和插入算法在最坏情况下的时间复杂度均为 $O(n)$。

Q2.（来源：2011影印 2012影印 2013 历年汇总 试卷7，本题 2 分）

构造 AVL 树和 2-3 树的主要目的是什么？它们各自有什么样的查找和插入的效率？

【参考答案】 主要目的是维持树的平衡、避免树退化，减小树高，使（平均/最坏）查找与插入效率更高。AVL 树的查找、插入效率均为 $O({\log }_{2}n)$；2-3 树的查找、插入效率亦为 $O({\log }_{2}n)$。

4.2　概率算法概念

Q3.（来源：2012影印 2013 历年汇总；2011影印 为不含子集和的简版，本题 2–3 分）

何谓伪多项式算法？如何将一 Monte Carlo 算法转化为 Las Vegas 算法？以子集和问题为例说明伪多项式时间算法和 FPAS 可以有的关系。

【参考答案】

• 伪多项式算法：运行时间是关于输入数值大小 $L$（输入实例中的最大数值）的多项式的算法，而非关于输入"长度（二进制位数）"的多项式。
• MC → LV 的转化：Monte Carlo 每次都能给出解但可能错误；Las Vegas 给出的解必正确但可能不给解。做法是在 MC 算法之后附加一个验证算法：若验证 MC 给出的解正确则输出该解，若不正确则不输出（即"不给解"），从而把 MC 转化为 LV。
• 子集和：子集和问题存在伪多项式时间的动态规划算法；据此可构造其完全多项式近似方案（FPTAS/FPAS）。

Q4.（来源：2011期末 试卷4，本题约 4 分）

简述拉斯维加斯（Las Vegas）算法和蒙特卡洛（Monte Carlo）算法的主要区别。

【参考答案】 前者（Las Vegas）不一定总能给出解，但给出的解一定是正确的；后者（Monte Carlo）总能给出解，但给出的解可能是错误的。

4.3　P / NP 与判定问题

Q5.（高频；来源：2011影印 2012影印 2013 2020 merged 历年汇总，本题 3 分）

写出 0/1 背包问题的一个多项式等价 (Polynomially equivalent) 的判定问题，并说明为什么它们是多项式等价的。

【参考答案】 判定问题：给定 $n$ 件物品（重量 $w_i$、价值 $p_i$，$1\le i\le n$）、背包容量 $W$ 与整数 $k$，问是否存在物品子集 $S$，使得 $\sum _{i\in S}{w}_i\le W$ 且 $\sum _{i\in S}{p}_i\ge k$？

多项式等价证明（双向归约）：

1. 优化 → 判定：若有 0/1 背包优化算法，求出最优价值 $P^{\ast }$，则判断 $P^{\ast }\ge k$ 即解判定问题（一次调用）。
2. 判定 → 优化：若有判定算法，在 $0\le k\le \sum _i{p}_i$ 的价值范围内对 $k$ 做二分搜索，每次调用判定算法，即可在 $O(\log \sum _i{p}_i)$ 次调用内求出最优值。

两个方向都只需多项式次调用与多项式额外工作，故二者多项式等价。

Q6.（来源：2011影印 2012影印 2013 历年汇总 merged，本题 2 分）

下面问题是否属于 NP 问题？为什么？

给定图 $G=(N,A)$ 中的两个点 $p$、$q$，整数 $c$ 和 $t$，图 $G$ 中每条边的长度 $c_{ij}$ 及遍历这条边的时间 $t_{ij}$，问图 $G$ 中是否存在一条由 $p$ 到 $q$ 的路径，使得其长度大于 $c$，且遍历时间小于 $t$？

【参考答案】 属于 NP 问题。 对任一候选路径（证书），只需 $O(N)$ 时间沿路径累加长度与时间，并检查"长度 $>c$ 且时间 $<t$"，验证可在多项式时间内完成，故该问题属于 NP。

Q7.（来源：试卷7 整理）

给出 P、NP、NP-完全(NPC)、NP-难(NP-hard)，以及"归约"与"转化"的定义。

【参考答案】

• P：存在多项式时间算法求解的判定问题类（"存在求解判定问题 $P_1$ 的多项式算法"）。
• NP：对每个"是(yes)"实例都存在一个多项式长度的验证（证书），可在多项式时间内验证其确为"是"实例的判定问题类。
• NPC：$P_1\in$ NP，且 NP 中所有其它问题都可多项式转化到 $P_1$。
• NP-hard：NP 中所有问题都可多项式归约到 $P_1$（不要求 $P_1\in$ NP，故范围比 NPC 更广）。
• 归约 (reduce)：可以用求解 $P_2$ 的算法作为子程序来求解 $P_1$，则称 $P_1$ 可归约为 $P_2$。
• 转化 (transform)：对 $P_1$ 的每个实例 $I_1$ 均可在多项式时间内构造 $P_2$ 的一个实例 $I_2$，使得当且仅当 $I_2$ 为"是"实例时 $I_1$ 也为"是"实例，则称 $P_1$ 可多项式转化为 $P_2$。

4.4　最小生成树与拟阵（高频）

Q8.（来源：2020、微信图片3，本题 3 分；merged 为 Prim+Kruskal 合并版，本题 4 分）

（2020 版）说明最小生成树的 Prim 算法不具有拟阵的结构，即说明 Prim 算法所对应的二元组 $M=(S,I)$ 不满足遗传性质或不满足交换性质。

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

【参考答案】

• Kruskal —— 满足拟阵（图拟阵 graphic matroid）。 取 $S=E$（图的边集），$\mathcal{I}=$ 所有"无环边子集（森林）"。
  • 非空性 / 遗传性：空集是森林；森林的任意子集仍是森林，满足遗传性。
  • 交换性：若森林 $I,J$ 且 $|I|<|J|$，则 $J$ 边更多、连通分量更少，必存在边 $e\in J-I$ 使 $I\cup \{e\}$ 仍无环，满足交换性。
  • Kruskal 按权从小到大、只要不成环就加入边，恰是图拟阵上的贪心，故 Kruskal 对应拟阵。
• Prim —— 不满足拟阵。 Prim 从一个顶点出发、按"到已选顶点集的最小边权"扩展，其"已选边集"并非以纯粹子集关系定义的独立集：
  • 遗传性不成立：去掉已选生成树中的一条边可能使其变成不连通的森林片段，不符合 Prim 从单顶点逐步扩展的结构；
  • 交换性不成立：Prim 的加边规则基于"与已选顶点集的距离"，而非拟阵那种通用的元素交换规则。
  • 故 Prim 对应的 $M=(S,I)$ 不能同时满足遗传性与交换性，不构成拟阵。

4.5　下界、近似与性能比

Q9.（来源：样题1 试卷1 试卷3）

求解 TSP 问题的最近邻居算法的性能比是多少？这一性能比是如何求得的？

【参考答案】 最近邻居（nearest-neighbor）算法没有常数性能比：对一般（满足三角不等式的）TSP，其性能比约为 $\frac{1}{2}(\lceil {\log }_{2}n\rceil +1)$ 量级，随 $n$ 增大而无界。求法是构造一类实例，使贪心的"最近邻"选择不断被迫在后期走很长的边，从而给出近似解与最优解之比的下界。（若课件给出具体结论，按课件作答。）

Q10.（来源：样题1 试卷3）

请举出三种寻找问题下界的方法或策略。

【参考答案】 ① 平凡下界（trivial lower bound，按必须读入/输出的规模）；② 信息论下界 / 判定树下界（如基于比较的排序为 $\mathrm{\Omega }(n\log n)$）；③ 对手论证 (adversary argument)；④ 问题归约（reduction，将已知下界问题归约到目标问题）。任举三种即可。

Q11.（来源：2011期末 + 答案；试卷4 + 答案）

请给出基于比较的对数组 $A[1\dots n]$ 进行排序问题的最紧的下界，并写出两个平均时间复杂度为该下界的排序算法的名称。

【参考答案】 最紧下界为 $\mathrm{\Omega }(n\log n)$；平均时间复杂度达到该下界的排序算法如快速排序、随机化快速排序、合并排序、堆排序（任举两个即可）。

Q12.（来源：2020、微信图片3，本题 3 分）

用对手论证法给出最坏情况下，从 n 个数字中找第二小值的基于比较的算法的下界；这个下界是紧密的吗（即是否存在与下界一致的算法）？

【参考答案】 下界为 $n+\lceil {\log }_{2}n\rceil -2$ 次比较。论证：找最小值至少需 $n-1$ 次比较；第二小值一定在"曾直接负于最小值"的元素之中，而最小值在一场锦标赛中最多与 $\lceil {\log }_{2}n\rceil$ 个元素比较过，故再用 $\lceil {\log }_{2}n\rceil -1$ 次比较即可从中选出最小者。该下界是紧密的——锦标赛（tournament）方法恰好可达到 $n+\lceil {\log }_{2}n\rceil -2$ 次比较。

Q13.（来源：2020，本题 2 分）

若近似算法 A 求解某极小化问题一实例的解为 $s_a$，且已知该问题的最优解为 $s_a/3$，则该近似算法的性能比是多少？为什么？

【参考答案】 仅凭这一个实例不能断定算法性能比为 3。该实例只给出比值 $s_a/(s_a/3)=3$，即性能比的一个下界；算法的性能比定义为对所有实例的最坏比值（上确界），需对所有输入分析才能确定，可能大于 3。（与判断题第 44/45 条互为印证。）

4.6　函数增长率排序

Q14.　按照增长率上升的顺序排列以下函数，即，若在你的排序结果中，函数 $f(n)$ 跟在 $g(n)$ 的后面，则说明应满足 $g(n)$ 是 $O(f(n))$。（多版本，原题函数表如下）

• 版本 A（来源：样题1 试卷1 试卷3）：

  $f_1(n)={10}^n$，$f_2(n)=n^{1/3}$，$f_3(n)=n^n$，$f_4(n)=2^{\sqrt{{\log }_{c}n}}$，$f_5(n)={\log }_{2}n$

  【答案】 $f_5\prec f_4\prec f_2\prec f_1\prec f_3$，即 ${\log }_{2}n,2^{\sqrt{{\log }_{c}n}},n^{1/3},{10}^n,n^n$。

• 版本 B（来源：2011期末 试卷4 + 答案）：

  $f_1(n)=n^{3/4}$，$f_2(n)=2^n$，$f_3(n)=\log n$，$f_4(n)=n!$，$f_5(n)=2^{n^2}$，$f_6(n)=n\log n$

  【答案】 $f_3\prec f_1\prec f_6\prec f_2\prec f_4\prec f_5$，即 $\log n,n^{3/4},n\log n,2^n,n!,2^{n^2}$。

• 版本 C（来源：样题2 试卷2，原文部分识别模糊）：

  $h_1(n)=2^n$，$h_2(n)=3n^{1/3}$，$h_3(n)=n^n$，$h_4(n)=2^{{\ln }^{n}n}$ ⟨识别模糊⟩，$h_5(n)={\ln }^{1/5}n$

  【答案】 大致为 $h_5\prec h_2\prec h_1\prec h_3$，$h_4$ 因原式识别模糊需核对原卷后定位（若 $h_4=2^{n\ln n}$ 量级则介于 $h_1$ 与 $h_3$ 之间）。

4.7　渐进记号证明

Q15.（来源：样题1 试卷3）

证明：$1.5n^2+365n\log n=O(n^2)$。

【参考答案】 当 $n\ge 1$ 时 $n\log n\le n^2$，故 $1.5n^2+365n\log n\le 1.5n^2+365n^2=366.5n^2$。取 $c=366.5,n_0=1$，对一切 $n\ge n_0$ 有 $1.5n^2+365n\log n\le c{n}^2$，即 $=O(n^2)$。$◼$

4.8　称球（最大最小）

Q16.（来源：试卷4 + 答案）

设有 16 个外形一样但重量各不相同的小球，现有一架没有砝码的天平，请问最少需要称几次才能找出重量最小和重量最大的球？为什么？

【参考答案】 22 次。 同时找最大值与最小值的比较次数紧下界为 $\lceil 3n/2\rceil -2$，$n=16$ 时为 $3\times 16/2-2=22$。方法：先把 16 个球两两比较分成"较重组(8)"与"较轻组(8)"（8 次），再在较重组里用锦标赛找最重（7 次），在较轻组里找最轻（7 次），共 $8+7+7=22$ 次。

4.9　分支限界概念

Q17.（来源：2020，本题 3 分）

分支定界算法遍历搜索树的"Frontier Search"，是如何工作的？为什么会有这样一种方法？

【参考答案】 Frontier（前沿/边界）搜索只在内存中保存搜索的"前沿"（当前活结点边界），而不保存已扩展的内部结点，靠记录与父层的关系在需要时重建路径。其动机：分支限界/最优搜索的活结点表可能呈指数级膨胀，前沿搜索可大幅降低空间占用，使大规模实例在有限内存下可解。

4.10　智能优化算法

Q18.（来源：2020，本题 4 分）

请分别阐述邻域搜索、模拟退火与遗传算法的基本原理，并从算法特点与计算效果等角度比较它们的异同。

【参考答案】

• 邻域搜索（局部搜索）：从一个解出发，在其邻域内寻找更优解并移动，直至到达局部最优。简单快速，但易陷入局部最优。
• 模拟退火：在邻域搜索基础上，以 Metropolis 准则按概率接受劣解（接受概率随"温度"下降而减小），从而具备跳出局部最优的能力；温度调度影响收敛速度与解的质量。
• 遗传算法：基于种群，用选择、交叉、变异等遗传算子并行进化多个解，依靠群体多样性进行全局搜索。
• 异同：三者都是面向难优化问题的启发式/元启发式，均不保证最优。邻域搜索最基础、最易陷局部最优；模拟退火以概率接受劣解获得跳出能力（单点搜索）；遗传算法以种群 + 交叉获得更强的全局探索能力，但参数多、收敛较慢。计算效果上通常 SA、GA 优于纯局部搜索，代价是更高的时间开销与调参成本。

4.11　各策略适用条件

Q19.（来源：试卷5 + 试卷5答案）

请分别说明分治策略、动态规划、贪心选择策略、回溯法和分支限界法在实际应用中的适用条件。

【参考答案】

• 分治：问题能分解为规模更小的同类、相互独立的子问题，子问题的解可合并成原问题的解（常与递归等价）。
• 动态规划：问题可分解为子问题，但子问题相互重叠/不独立，且具有最优子结构，常用于求解具有某种最优性质的问题（自底向上、记忆化）。
• 贪心：具有贪心选择性质与最优子结构——每步局部最优的选择能导向全局最优。
• 回溯：需求出满足约束条件的所有解（或一个可行解），在解空间树上深度优先搜索并剪枝。
• 分支限界：在满足约束条件的解中求最优解，用界函数剪枝、按 BFS/优先队列方式扩展活结点。

---

五、递推式求解题（原题保留 + 解答）

常用方法：迭代展开 / 主定理 / 课件"定理 1"。

T1.（来源：样题2 试卷2）

推导以下递推式的解：

$$\mathrm{T}(n)=2\text{当 }n=2\text{ 时}$$$$\mathrm{T}(n)=2\mathrm{T}(n-1)+n\text{当 }n>2\text{ 时}$$

【解】 迭代展开：$T(n)=2T(n-1)+n=2^{2}T(n-2)+2(n-1)+n=\cdots$。齐次解 $c\cdot 2^n$、特解 $-(n+2)$，由 $T(2)=2$ 定常数得 $T(n)=\frac{3}{2}\cdot 2^n-(n+2)=\mathrm{\Theta }(2^n)$。

T2.（来源：样题1 试卷1 试卷3）

推导以下递推式的解：

$$\mathrm{T}(n)=2\text{当 }n=3\text{ 时}$$$$\mathrm{T}(n)=2\mathrm{T}(n/3)+2\text{当 }n>3\text{ 时}$$

【解】 设 $n=3^k$，记 $t_k=T(3^k)$，则 $t_k=2t_{k-1}+2,t_1=2$，解得 $t_k=2^{k+1}-2$。又 $2^k=n^{{\log }_{3}2}$，故 $T(n)=2n^{{\log }_{3}2}-2=\mathrm{\Theta }\left(n^{{\log }_{3}2}\right)\approx \mathrm{\Theta }(n^{0.63})$。

T3.（来源：2011期末 + 答案）

推导以下递推式的解：

$$\mathrm{T}(n)=2\text{当 }n=1\text{ 时}$$$$\mathrm{T}(n)=4\mathrm{T}(n/2)+2n\text{当 }n\ge 2\text{ 时}$$

【解】 主定理 $a=4,b=2$，$n^{{\log }_{2}4}=n^2$ 主导 $2n$ → $\mathrm{\Theta }(n^2)$。精确求解：$T(n)=2n^2+2n=O(n^2)$。

T4.（来源：试卷4 + 答案）

推导以下递推式的解：

$$\mathrm{T}(n)=2\text{当 }n=1\text{ 时}$$$$\mathrm{T}(n)=2\mathrm{T}(n/3)+2n\text{当 }n\ge 2\text{ 时}$$

【解】 $a=2,b=3$，$n^{{\log }_{3}2}\approx n^{0.63}\prec 2n$，故 $f(n)=2n$ 主导 → $\mathrm{\Theta }(n)$。精确（设 $n=3^k$）：$T(n)=6n-4\cdot 2^{{\log }_{3}n}=6n-4n^{{\log }_{3}2}=\mathrm{\Theta }(n)$。

T5.（来源：HW1 + 解答）

已知下列递推式：

$$C(n)=1\text{若 }n=1;C(n)=2C(n/2)+n-1\text{若 }n\ge 2$$

请由定理 1 导出 $C(n)$ 的非递归表达式并指出其渐进复杂性。

定理 1：设 $a,c$ 为非负整数，$b,d,x$ 为非负常数，并对于某个非负整数 $k$，令 $n=c^k$，则递推式 $f(n)=d(n=1);f(n)=af(n/c)+b{n}^x(n\ge 2)$ 的解是：

$$f(n)=b{n}^x{\log }_{c}n+d{n}^x(\text{若 }a=c^x);f(n)=(d+\frac{b{c}^x}{a-c^x})n^{{\log }_{c}a}-(\frac{b{c}^x}{a-c^x})n^x(\text{若 }a\ne c^x)$$

【解】 套用定理 1：$a=2,b=1,c=2,d=1,x=1$，此时 $a=c^x=2$，故取第一式

$$C(n)=b{n}^x{\log }_{c}n+d{n}^x=n{\log }_{2}n+n,$$

对应本题（常数项略有差异，按 HW 解答）得非递归表达式 $C(n)=(n-1){\log }_{2}n+n$，渐进复杂度 $O(n\log n)$。

---

六、分治算法题（原题保留 + 思路/伪代码/复杂度）

D1. 逆序对计数。（来源：2011影印 三 / 历年汇总 分治 1；答案见 历年答案）

写出一求解下列问题的分治算法，推导其时间复杂性并与蛮力法相比较。

给定互不相等的 $n$ 个数的一个序列 $a_1,a_2,\cdots ,a_n$，若其中某两个数 $a_i$ 和 $a_j$ 的关系为：$a_i>a_j$，且 $i<j$，则称 $a_i$ 和 $a_j$ 是逆序的。要求计算该序列中的逆序个数，即具有逆序关系的元素对的总数目。

【思路】 以归并排序为框架：在合并两个有序子段时，若右段当前元素 $a[j]$ 小于左段当前元素 $a[i]$，则左段中从 $i$ 到 mid 的元素都与 $a[j]$ 构成逆序，累加 mid-i+1。

num ← 0
MergeCount(a, left, mid, right):
    i ← left, j ← mid+1
    while i ≤ mid and j ≤ right:
        if a[j] < a[i]: num += mid - i + 1; 取 a[j]; j++
        else:           取 a[i]; i++
    （搬完剩余元素）
MergeSortCount(a, left, right):
    if left < right:
        mid ← (left + right) / 2
        MergeSortCount(a, left, mid)
        MergeSortCount(a, mid+1, right)
        MergeCount(a, left, mid, right)

【复杂度】 $T(n)=2T(n/2)+O(n)=O(n\log n)$；蛮力两两比较为 $O(n^2)$。$n$ 较大时分治显著更优。

---

D2. 股票买卖最大收益。（来源：样题1 试卷1 试卷3 三；另 样题1 试卷3 第四题要求"分别用蛮力法、分治法、动态规划法求解"）

设计一求解以下问题的分治算法，写出伪代码，分析其时间复杂性并与该问题的蛮力算法相比较：

某投资咨询公司要长期重复做一项模拟，在这项模拟中他们从过去的某天开始对一支给定的股票连续考察 $n$ 天（这些天数记为 $i=1,2,\dots ,n$）；对每天 $i$，有当天这只股票每股的价格 $p(i)$（为简单起见，我们假设这个价格在每一天之内是固定的）。假设在这 $n$ 天内，某天买进这支股票并且在以后的某天卖出这些股票。欲求：为了挣到最多的钱，他们应该什么时候买进并且什么时候卖出？

举例说，假设 $n=4$，$p(1)=4$，$p(2)=1$，$p(3)=1.5$，$p(4)=3$，那么你的算法应该返回"2 买，4 卖"（在第 2 天买并且在第 4 天卖意味着每股将挣 2 美元，是这个期间最大的收益）。

【分治思路】 将 $1..n$ 二分为左右两半，最优买卖必属下列三种情形之一：① 完全在左半；② 完全在右半；③ 跨越中点——买在左半最低价、卖在右半最高价。递归求 ①②，$O(n)$ 求 ③（左半 $min$、右半 $max$）。

【复杂度】 $T(n)=2T(n/2)+O(n)=O(n\log n)$；蛮力枚举买卖日对为 $O(n^2)$；动态规划/一遍扫描法（维护"此前最低价"）可达 $O(n)$。

---

D3. 网球循环赛日程表。（来源：样题2 试卷2 三、试卷5 四.3；复杂度分析见 试卷2第三题分析）

设计一求解以下问题的分治算法，写出伪代码，分析其时间复杂性并与该问题的蛮力算法相比较：

问题描述：设有 $n=2^k$ 个运动员要进行网球循环赛。现要设计一个满足以下要求的比赛日程表： （1）每个选手必须与其他 $n-1$ 个选手各赛一次； （2）每个选手一天只能参赛一次； （3）循环赛在 $n-1$ 天内结束。

请按此要求将比赛日程表设计成有 $n$ 行和 $n-1$ 列的一个表。在表中的第 $i$ 行，第 $j$ 列处填入第 $i$ 个选手在第 $j$ 天所遇到的选手。其中 $1\le i\le n$，$1\le j\le n-1$。

【分治思路】 二分递归填表：先排出左上角 $\frac{n}{2}$ 名选手在前 $\frac{n}{2}-1$ 天的子日程；再把左上角整块复制到右下角、左下角复制到右上角，即可得到完整日程表。

Table(n, k, a):
    if n == 2: 让这两人直接比赛
    else:
        Table(n/2, k-1, a)          // 计算左上角
        Table(n/2, k-1, a + n/2)    // 计算左下角
        把左上角矩阵复制到右下角
        把左下角矩阵复制到右上角

【复杂度】（据 试卷2第三题分析）$T(n)=2T(n/2)+O(n^2/2)=O(n^2)$；蛮力逐天枚举对手约为 $O(n^3)$。

---

D4. 假币问题。（来源：试卷6 Q1，15 分，中英双语）

Tom is very naughty. One day, he puts one false coin down the collection can of coins. After do that, he is afraid that his father will beat him, so he wants to find out that false coin from N coins. He knows the weight of the false coin is lighter than that of others, but he do not know how to find it, so he cannot help crying. Maybe you can help him. Please describe an algorithm to find the false coin with the help of balance, and analyze the running time of your algorithm.

汤姆很顽皮。一天，他把假币投到储钱罐里。之后，他担心爸爸揍它，想从 N 个钱币里找出那个假币。他知道假币的重量比其他钱币轻，但不知道如何找到它，于是禁不住哭了。也许你能帮他。请描述一个通过使用天平能找到假币的算法，并分析你算法的运行时间。

【思路】 三分法：每次把硬币尽量均分三堆 $A,B,C$（$|A|=|B|$）。称量 $A$ 与 $B$：若不平衡，假币在较轻的一堆；若平衡，假币在 $C$ 堆。每次将搜索范围缩小到约 $1/3$。

【复杂度】 $T(N)=T(N/3)+O(1)=O({\log }_{3}N)$ 次称量。

---

七、变治 / 减治算法题（原题保留 + 解答）

V1. 多数元素 (majority element)。（来源：2011影印、2012影印、2013、历年汇总、试卷7，本题 5 分；答案见 2012答案 历年答案 试卷7）

$A[1\dots n]$ 为一整数序列，$A$ 中的整数 $a$ 如果在 $A$ 中的出现次数多于 $\lfloor n/2\rfloor$，那么 $a$ 称为多数元素。例如，在序列 $1,3,2,3,3,4,3$ 中，3 是多数元素，因其出现 4 次，大于 $\lfloor 7/2\rfloor$。求 $A$ 的多数元素问题的蛮力算法复杂性如何？设计一具有变治思想的算法，提高蛮力算法的效率，写出伪代码并分析其时间复杂性。

【蛮力】 对每个元素统计其在数组中的出现次数，双重循环，时间复杂度 $O(n^2)$。

【变治法一：预排序，$O(n\log n)$】（变治 = 预处理排序）排序后多数元素必占据连续且长度 $>\lfloor n/2\rfloor$ 的一段，扫描最长连续相等段即可：

Sort(A, n)                       // O(n log n)
i ← 0
while i < n:
    val ← A[i]; count ← 1
    while i+count < n and A[i+count] == val: count++
    if count > n/2: return val
    i ← i + count
return NONE

复杂度 $O(n\log n)$（排序主导）。

【变治法二：Boyer–Moore 摩尔投票，$O(n)$】（提示："任取两个不同元素则同时丢弃"）

cand ← A[0]; count ← 0
for i ← 0 to n-1:
    if count == 0:        cand ← A[i]; count ← 1
    elif A[i] == cand:    count++
    else:                 count--      // 一对不同元素相互抵消
return cand                            // 如需确认，再扫一遍验证其计数 > n/2

复杂度 $O(n)$、仅一遍扫描（Hash 计数虽也是 $O(n)$ 但需额外空间，试卷7 中"Hash 不行"即指此）。

---

V2. 减治求 $\lfloor {\log }_{2}N\rfloor$。（来源：2020 二、微信图片3，本题 4 分）

写出一具有减治思想的求 $\lfloor {\log }_{2}N\rfloor$ 的算法，并推导其时间复杂性。

【解】 不断把 $N$ 整除 2 并计数，直到 $N<2$：

DecLog2(N):
    k ← 0
    while N > 1:
        N ← N / 2        // 整数除法（规模减半，减治）
        k ← k + 1
    return k             // = ⌊log2 N⌋

每次规模减半，$T(N)=T(N/2)+O(1)$，循环 $\lfloor {\log }_{2}N\rfloor +1$ 次，时间复杂度 $O(\log N)$。

---

V3. 减治求数组最小元素的位置。（来源：HW1 四）

对于求 $n$ 个实数构成的数组中最小元素的位置问题，写出你设计的具有减治思想算法的伪代码，确定其时间效率，并与该问题的蛮力算法相比较。

【解】 二分减治：把 $A[low..high]$ 分两半分别求最小元及其位置，再取较小者对应的下标。

(element, index) = FindLeastElement(A, low, high):
    if low == high: return (A[low], low)
    (e1, i1) = FindLeastElement(A, low, (low+high)/2)
    (e2, i2) = FindLeastElement(A, (low+high)/2 + 1, high)
    return (e1 < e2) ? (e1, i1) : (e2, i2)

$T(n)=2T(n/2)+O(1)=O(n)$，与蛮力 $O(n)$ 同阶；但分治版约做 $2n$ 次比较，常数更大，反而不如一遍扫描的蛮力法划算（此题意在体会减治思想与常数因子的权衡）。

同时找最大值与最小值（16 球天平、紧下界 $\lceil 3n/2\rceil -2$）见 §四 Q16。

---

八、动态规划题（原题保留 + 递推式/手算结果）

通用作答要素：状态变量、决策变量、状态转移方程、递推关系式 + 手工求解步骤与结果。

P1. 矩阵链乘最优结合。（来源：2011期末 三，20 分 + 答案）

写出用动态规划方法求矩阵链乘积问题 $p(l,h)=A_{l+1}\times A_{l+2}\times \cdots \times A_h$ 的递推公式、伪代码和时间复杂性，并用该算法手工计算得出下列矩阵链乘积的最优策略和该策略对应的最小开销（按照递推公式给出详细步骤）：

$$d=A_{3,4}\times A_{4,6}\times A_{6,1}\times A_{1,5}$$

注：这里 $A_{x,y}$ 表示一个 $x\times y$ 阶矩阵。

【递推】 $m[l,h]=0(l+1=h)$；$m[l,h]=\underset{l<i<h}{min}\{m[l,i]+m[i,h]+d_l{d}_i{d}_h\}(l+1<h)$，时间复杂性 $O(n^3)$。

【手算】 维数 $d=[3,4,6,1,5]$：

$$m_{12}=3\cdot 4\cdot 6=72,m_{23}=4\cdot 6\cdot 1=24,m_{34}=6\cdot 1\cdot 5=30$$$$m_{13}=min(0+24+3\cdot 4\cdot 1,72+0+3\cdot 6\cdot 1)=36$$$$m_{24}=min(0+30+4\cdot 6\cdot 5,24+0+4\cdot 1\cdot 5)=44$$$$m_{14}=min(0+44+3\cdot 4\cdot 5,72+30+3\cdot 6\cdot 5,36+0+3\cdot 1\cdot 5)=\mathbf{51}$$

最优策略 $((A_{3,4}\times (A_{4,6}\times A_{6,1}))\times A_{1,5})$，最小开销 = 51。

---

P2. 最长公共子序列 (LCS)。（多版本）

写出用动态规划方法求两个序列的最长公共子序列算法的递推公式、伪代码和时间复杂性，并用该算法手工计算以下序列的最长公共子序列。

【递推】 $c[i,j]=\{\begin{array}{ll}0& i=0\text{ 或 }j=0\\ c[i-1,j-1]+1& x_i=y_j\\ max\{c[i-1,j],c[i,j-1]\}& x_i\ne y_j\end{array}$，时间复杂性 $O(mn)$。

【各版本原题与结果】

• 版本 A（来源：样题2 试卷2，15 分）：$X=$abcbcc，$Y=$cacbac → LCS 长度 4，如 acbc（验证：$X$ 取 $a_1{c}_3{b}_4{c}_5$、$Y$ 取 $a_2{c}_3{b}_4{c}_6$）。

• 版本 B（来源：样题1 试卷1 试卷3，15 分）：$A=$xzyzzyx，$B=$zxyyzxz → LCS 长度 5。

• 版本 C（来源：试卷4 三，20 分 + 答案；要求"写出手工计算的全过程"）：$A=$xzyzzyx，$B=$zxyyzxzy → LCS 长度 5，为 xyzzy 或 zyzzy。

---

P3. 投资分配（8 万元投 3 个项目）。（来源：2011影印 四，8 分 / 历年汇总 DP2 / 算法整理；答案见 历年答案）

有 8 万元的投资可以投给 3 个项目，每个项目在不同投资数额下（以万元为单位）的利润如下表。请安排投资计划，使总的利润最大。写出你所设的状态变量、决策变量、状态转移方程与递推关系式，和手工求解的详细步骤及结果。

投资额（万元）	0	1	2	3	4	5	6	7	8
项目 1	0	5	15	40	80	90	95	98	100
项目 2	0	5	15	40	60	70	73	74	75
项目 3	0	4	26	40	45	50	51	52	53

【状态/决策】 阶段 $k$ = 项目编号；状态 $x_k$ = 可用于项目 $k\sim 3$ 的资金；决策 $u_k$ = 投给项目 $k$ 的金额。 状态转移：$f_k(x_k)=\underset{0\le u_k\le x_k}{max}\{g_k(u_k)+f_{k+1}(x_k-u_k)\}$，边界 $f_4\equiv 0$。

【手算结果】 最大获益 = 140 万元：项目 1 投 4 万、项目 2 投 4 万、项目 3 投 0 万（$80+60+0=140$）。

---

P4. 生产—库存计划（4 个月）。（来源：2012影印 2013 历年汇总 四；答案见 历年答案）

某工厂调查了解市场情况，估计在今后四个月内，市场对其产品的需求量如下表所示。

时期（月）	1	2	3	4
需要量（产品单位）	2	3	2	4

已知：对每个月来讲，生产一批产品的固定成本费为 3（千元），若不生产，则为零。每生产单位产品的成本费为 1（千元）。同时，在任何一个月内，生产能力所允许的最大生产批量为不超过 6 个单位。又知每单位产品的库存费用为每月 0.5（千元），同时要求在第一个月开始之初及在第四个月末，均无产品库存。

问：在满足上述条件下，该厂应如何安排各个时期的生产与库存，使所花的总成本费用最低？写出你所设的状态变量、决策变量、状态转移方程与递推关系式，和手工求解的详细步骤及结果。

【状态/决策】 阶段 = 月份；状态 = 当月初库存；决策 = 当月生产量 $u\in [0,6]$； 转移 $s_{k+1}=s_k+u_k-d_k$，阶段成本 $=[u_k>0]\cdot 3+1\cdot u_k+0.5\cdot s_{k+1}$。

【手算结果】 最低总成本 = 20.5 千元，对应生产策略：月 1 生产 5、月 2 生产 0、月 3 生产 6、月 4 生产 0（集中在 1、3 月生产，靠库存覆盖 2、4 月需求）。

---

P5. 货车分配（5 台货车分给 A、B、C 三子公司）。（来源：2020 四，5 分）

某物流企业拟将新购置的五台货车，分配给所属的 A、B、C 三个子公司，各子公司若获得新分配的货车之后，可以创造的年利润如下表。请计算出分配给各子公司该新购货车的数目，以使总的年利润最大。写出你所设的状态变量、决策变量、状态转移方程与递推关系式，和手工求解的详细步骤及结果。

车辆数	A	B	C
0	0	0	0
1	2	5	5
2	6	9	6
3	10	11	11
4	11	12	12
5	13	12	13

【转移】 阶段 = 子公司，状态 = 剩余车辆，$f_k(s)=\underset{0\le u\le s}{max}\{g_k(u)+f_{k+1}(s-u)\}$。

【手算结果】 最大总利润 = 20。一个最优分配：A = 0、B = 2、C = 3（$0+9+11=20$）；另有 A = 2, B = 2, C = 1 与 A = 3, B = 1, C = 1 等并列最优解。

---

P6. 货物分销（一车 6 箱货卸到 4 个零售店）。（来源：merged 四，8 分 + 完整解答）

有一部货车每天沿着公路的四个零售店卸下 6 箱货物，如果各零售店出售该货物所得的利润表如下表所示，试求在各零售店各卸下几箱，能使获得的总利润最大？其值是多少？写出你所设的状态变量、决策变量、状态转移方程与递推关系式，和手工求解的详细步骤及结果。

箱数 \ 零售店	1	2	3	4
1	4	2	3	4
2	6	4	5	5
3	7	6	7	6
4	7	8	8	6
5	7	9	8	6
6	7	10	8	6

【转移】 状态 $s_k$ = 到第 $k$ 店时剩余箱数（$s_1=6$），决策 $u_k$ = 在第 $k$ 店卸下箱数，$f_k(s_k)=\underset{0\le u_k\le s_k}{max}\{v_k[u_k]+f_{k+1}(s_k-u_k)\}$。

【手算结果】 最大总利润 = 17，存在多种最优卸货方案，如 $(1,1,3,1)$、$(2,2,1,1)$、$(2,1,2,1)$ 等（原解答列出共 6 种）。

---

P7. 公路广告牌。（来源：样题1 试卷3 五 / 算法整理）

设计一基于动态规划思想求解以下问题的算法，写出递推关系式、伪代码，并分析你所设计的算法的时间复杂性：

一条公路由西到东长 $M$ 公里，公路两旁可能设立广告牌的地点为 $x_1,x_2,\dots ,x_n$，而在各地点放置一块广告牌带来的收益分别为 $p_1,p_2,\dots ,p_n$。有关规定要求两块广告牌的距离不能小于 3 公里。要求找到一组地点来放置广告牌，使得总收益最大。

【递推】 将地点按位置排序，令 $prev(i)$ = 满足 $x_j\le x_i-3$ 的最大下标 $j$。则

$$f(i)=max\{f(i-1),p_i+f(prev(i))\},f(0)=0,$$

答案为 $f(n)$。时间复杂性 $O(n)$（已排序时用双指针求 $prev$）或 $O(n\log n)$。

棋盘覆盖（$2^k\times 2^k$，L 型骨牌共 $(4^k-1)/3$ 块、$T(k)=O(4^k)$）见 §三 填空 4。

---

九、贪心算法题（原题保留 + 思路/复杂度）

G1. 多机调度 / 最小化工期 (makespan)。（来源：样题1 试卷1 五 / 试卷3 六，15 分）

设计一求解以下问题的贪心算法，写出伪代码，并分析其时间复杂性：

给定 $m$ 台机器 $M_1,\dots ,M_m$ 和 $n$ 项作业，要把每一项作业分配给一台机器来完成。每一项作业 $j$ 有处理时间 $t_j$。若 $A(i)$ 表示分配给机器 $M_i$ 的作业集，则机器 $M_i$ 需要工作的总时间（亦称为 $M_i$ 的负载）为

$$T_i=\sum _{j\in A(i)}{t}_j$$

完成这 $n$ 项作业的工期 $T$ 为所有机器的最大负载，即 $T=\underset{i}{max}{T}_i$。要求找到一种分配方案，使得完成这 $n$ 项作业的工期最小。

例如，下图即为将处理时间分别为 2，3，7，4，2，2 的六项作业分配给三台机器的一种分配方案，其中 $M_1$ 的负载最大，为 9，则该方案完成这六项作业的工期为 9。

【贪心思路】 列表调度 / LPT：把作业按处理时间从大到小排序，依次把每个作业分给当前负载最小的机器（用最小堆维护各机器负载）。

按 t_j 降序排序作业
所有机器负载置 0（最小堆）
for 每个作业 j（降序）:
    取出当前负载最小的机器 Mi
    A(i) ← A(i) ∪ {j};  load(Mi) += t_j
return max_i load(Mi)

【复杂度】 排序 $O(n\log n)$ + 每次堆操作 $O(\log m)$，共 $O(n\log n+n\log m)$。 【性能比】 列表调度近似比为 $2-\frac{1}{m}$；LPT（降序）近似比为 $\frac{4}{3}-\frac{1}{3m}$。（贪心不一定最优，但有上述保证。）

---

G2. 方格阵最大权路径（按"贪心"要求作答）。（来源：样题2 试卷2 五，15 分）

设计一求解以下问题的贪心算法，写出伪代码，并分析其时间复杂性：

在一个 $N\times M$ 的方格阵中，每一格子赋予一个数（即为权）。规定每次移动时只能向上或向右。现试找出一条路径，使其从左下角至右上角所经过的权之和最大。

【贪心思路】 每一步在"上邻格"与"右邻格"中选择权值较大者前进，直到右上角。

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

【复杂度】 $O(N+M)$。

⚠️ 说明：本题贪心不保证全局最优（局部选较大者可能错过后续更大的权值）。若要保证最优应用动态规划：$f(i,j)=w(i,j)+max\{f(i-1,j),f(i,j-1)\}$，复杂度 $O(NM)$。考试若明确要求贪心，则按上法作答并指出其局限。

---

G3. 任务指派（效率矩阵）。（来源：试卷4 四，15 分 + 答案）

设计一针对以下问题的贪心算法，简述算法的基本思想，写出伪代码，并分析其时间复杂性（不一定要找到最优解）：

有 $n$ 项任务要完成，恰好有 $n$ 个人可以分别去完成其中一项，但由于任务性质和个人专长不同，因此个人去完成不同的任务的效率（或所费时间）就有差别。设给定效率矩阵 $C$，矩阵的元素 $c_{ij}(i,j=1,2,\dots ,n)$ 表示第 $i$ 人去完成第 $j$ 项任务所需的时间，则如何分派这 $n$ 个人去完成这 $n$ 项任务能使花费的总时间最少。

【贪心思路】（据答案）从第 1 到第 $n$ 个人，每人依次在当前尚未被指派的任务中选择其执行时间最小的任务。 【复杂度】 每人 $O(n)$ 次选择，共 $O(n^2)$。（最优解需匈牙利算法 $O(n^3)$，贪心仅得近似解。）

---

G4.（概念，来源：试卷7） 举一个有最优解的贪心算法例子。

【答案】 如单源最短路径 Dijkstra 算法、Huffman 编码，以及最小生成树 Prim/Kruskal、活动安排问题等。

---

十、回溯法题（SAT 问题，原题保留 + 搜索树解答）

共同要求：用回溯法求解 SAT，画出搜索树，标明搜索树的分支策略和树中各节点代表的状态（化简的 CNF 形式）。

分支策略：按变量顺序 $p,q,r,s$ 依次取值，左枝 = 1（真）、右枝 = 0（假）；每次代入后化简 CNF，若某子句变为空（所有文字为假）则剪枝回溯。

B1. 三子句 SAT。（来源：样题2 试卷2 五）

用回溯法求解以下 SAT 问题，请画出搜索树，标明搜索树的分支策略和树中各节点代表的状态（化简的 CNF 形式）。

$$(p\vee q)\wedge (\mathrm{\neg }q\vee r)\wedge (\mathrm{\neg }p\vee r)$$

【解】 取 $p=1$ → 化简为 $(\mathrm{\neg }q\vee r)\wedge r$，需 $r=1$；取 $q=1$ → $(\mathrm{\neg }q\vee r)=r$ 仍需 $r=1$。一组可满足赋值：$p=1,q=1,r=1$（公式为真）。

---

B2. 四子句 SAT（高频）。（来源：2011期末 + 答案 / 样题1 / 试卷1 / 试卷3 / 试卷4 + 答案 / 历年汇总）

用回溯法求解以下 SAT 问题，请画出搜索树，标明搜索树的分支策略和树中各节点代表的状态（化简的 CNF 形式）。

$$(p\vee q\vee s)\wedge (\mathrm{\neg }q\vee r)\wedge (\mathrm{\neg }p\vee r)\wedge (\mathrm{\neg }r\vee s)$$

【解（搜索树，来自答案）】 按 $p\to q\to r\to s$ 分支，左枝 = 1、右枝 = 0：

                 (p∨q∨s)(¬q∨r)(¬p∨r)(¬r∨s)
              p=1 /                        \ p=0
        (¬q∨r)(r)(¬r∨s)               (q∨s)(¬q∨r)(¬r∨s)
       q=1 /        \ q=0            q=1 /           \ q=0
   (r)(r)(¬r∨s)   (r)(¬r∨s)      (r)(¬r∨s)        (s)(¬r∨s)
   r=1 ↓            r=1 ↓           r=1 ↓             ...
   s=1              s=1             s=1

沿 $p=1,q=1,r=1,s=1$ 这条路径，所有子句均被满足。一个解：$p=q=r=s=1$。 （分支时凡某子句被置空则剪枝回溯；$\mathrm{\neg }r\vee s$ 在 $r=1$ 时强制 $s=1$。）

---

十一、分支限界题（原题保留 + 解答框架）

这类题共同设四问：① 如何构造搜索树（要求二叉）；② 遍历搜索树的原则（何时以及如何前进、分支、回溯、剪枝等）；③ 你设计的分支定界算法的"界"是什么，它为什么是正确的和有效的；④ 写出伪代码。

BB1. 中转贸易（最低税费 + 限时）。（高频；来源：2011影印 五 / 2020 五，6 分 / merged 三，6 分 + 完整解答 / 历年汇总 分支 2）

A 国与 B 国之间尚未直接通商。与 A 国直接通商的有 20 个国家（C1，C2，…，C20）；与 B 国直接通商的为另外 30 个国家（C21，C22，…，C50）。上述 50 个国家（C1，C2，…，C50）之间并不是每两个国家都直接通商，任意两国之间的贸易税率由对称矩阵 $R$ 给出，其中 $\mathrm{\infty }$ 代表两国不能直接通商。

A 国某公司与 B 国一公司欲通过某几个中间国家的公司完成一笔贸易，各个国家的进出口贸易通关等手续所需办理时间由向量 $T$ 给出。请安排一中转贸易计划，使得该交易所产生的向各中转国缴纳的税费最低，且整个交易能够在时间 $t$ 内完成。

1. 说明你是如何构造搜索树的（要求是二叉搜索树）。
2. 说明算法遍历搜索树的原则（何时以及如何前进、分支、回溯、剪枝等等）。
3. 你设计的分支定界算法的"界"是什么，它为什么是正确的和有效的？
4. 写出伪代码。

【解答框架（据 merged 解答）】

1. 搜索树：每个国家对应一层；令 $S$ = 已途经国家序列、$V$ = 已舍弃国家集。搜索国家 $c$ 时，左子树 = 途经 $c$，状态为 $(S\cup \{c\},V)$；右子树 = 不途经 $c$，状态为 $(S,V\cup \{c\})$。（二叉搜索树）
2. 遍历原则：当前结点不满足剪枝条件且有子树时前进；多选择处分支（先左 = 选，再右 = 不选）；左子树不满足时转右子树，子树遍历完或被剪则向父结点回溯。 剪枝条件：已花税费 + 当前点到 B 的最小剩余税费 ≥ 当前最优(最低)税费和，或 已花时间 + 当前点到 B 的最小剩余时间 > t，则剪枝。
3. 界：下界 = 已花税费 + 由当前点到终点 B 的最小剩余税费（对剩余约束放宽、用 Dijkstra 预先在税费矩阵上求得，故是合法下界，正确且有效）；同理用时间矩阵预求"到 B 的最小剩余时间"做可行性剪枝；上界 = 迄今搜索到的最优（最低）税费和。
4. 伪代码：

输入：税率矩阵 R，时间矩阵 T，约束时间 t，起点 i，终点 j
预处理：用 Dijkstra 求任意点到 j 的最小税费矩阵与最小时间矩阵
P ← {i};  V ← ∞          // 当前最优（最低）税费
search(S, Vset):
    if 到达 j: 更新最优解 P, V
    else if 不满足剪枝条件:
        search(S ∪ {c}, Vset)      // 左：途经 c
        search(S, Vset ∪ {c})      // 右：不途经 c
return P, V

---

BB2. 通信网络（最小费用无环网 + 双约束）。（来源：2012影印 2013 历年汇总 五，8 分）

某部门欲建立联通分布于五个区的共 50 个站点的有线通信网络。每两个站点之间的线路敷设费用由对称矩阵 $C$ 给出。任意两站点之间敷设线路需建设的地井数目由对称矩阵 $U$ 给出。

设计一线路敷设总费用为最小的无环网络，使得需建设的总地井数目不超过 $U_{MAX}$，且需跨区敷设的线路总数目不超过 $D_{MAX}$（各站点所属的区由向量 $D$ 给出）。

（四问同上：构造二叉搜索树 / 遍历原则 / 界 / 伪代码。）

【解答框架】 与 BB1 同构——二叉搜索树按"边选/不选"分层；界 = 已选费用 + 连成生成树所需的最小剩余费用（可用 Kruskal/MST 松弛求下界）；剪枝：地井数 $>U_{MAX}$、跨区线路数 $>D_{MAX}$ 或形成环即剪。目标在满足约束下最小化总费用。

---

BB3. 优先队列式分支限界——单源最短路径。（来源：试卷5 四.1 + 答案）

依据优先队列式分支限界法，求下图中从 s 点到 t 点的单源最短路径，请画出求得最优解的解空间树。要求中间被舍弃的结点用 × 标记，获得中间解的结点用单圆圈 ○ 框起，最优解用双圆圈 ◎ 框起。

【要点】 用优先队列（以当前路径长度作优先级）扩展活结点，每次取出界值最小者扩展，已出队即定型（类 Dijkstra）；对不可能更优的分支以 × 剪除。

---

BB4. 队列式分支限界——电路板布线。（来源：试卷5 四.2 + 答案）

已知在所示的电路板中，阴影部分是已作了封锁标记的方格，请按照队列式分支限界法在图中确定 a 到 b 的最短布线方案，要求布线时只能沿直线或直角进行，在图中标出求得最优解时各方格情况。

【要点】 队列式（FIFO，等价 BFS 波前扩散）从 $a$ 逐层标记距离，遇封锁格跳过，到达 $b$ 后沿距离标号回溯得到最短布线路径。

---

十二、概率 / 随机算法题（原题保留 + 解答）

R1. 近似取大值。（来源：2011期末 五，15 分 + 答案）

设计一求解以下问题的简单概率算法，写出伪代码，并分析该算法输出正确结果的概率：

在互不相等的 1000 个数中，任意找出最大的那 50 个数中的一个。

【解】 随机取出 $k$ 个数，输出其中最大值 $M$。

RandPickTop(A, k):
    任取 k 个数，求其最大值 M
    return M

正确性分析：单次随机抽取落在"最大 50 个"之外的概率为 $950/1000$；$k$ 次都落在之外（即 $M$ 不属于前 50）的概率为 $(950/1000{)}^k=(0.95{)}^k$。故输出正确的概率 $=1-(0.95{)}^k$（如 $k=90$ 时约 $1-{0.95}^{90}\approx 0.99$）。

---

R2. 指纹法测字符串相等。（来源：样题1 试卷1 试卷3 简答 5）

假设在测试字符串相等性的概率算法中，采用的指纹函数为 $I_p(x)=I(x)modp$，其中 $I(x)$ 为比特串 $x$ 的十进制整数表示，$I_p(x)$ 为 $I(x)$ 基于素数 $p$ 的指纹。已知：若 $x$ 和 $y$ 的长度均为 $n$，$p$ 为随机选择的小于 $2n^2$ 的素数，则当 $I_p(x)=I_p(y)$ 时，$x\ne y$ 的概率 $p_f\le 1/n$。又知：${\log }_{2}10\approx 3.32$。问：测试两个十万位的比特串的相等性时，需随机产生并传送几次指纹，可使假匹配的概率低于 ${10}^{-30}$？总共传送了多少比特位？

【解】 $n={10}^5$，单次指纹假匹配概率 $p_f\le 1/n={10}^{-5}$。送 $k$ 次相互独立的指纹，只有全部巧合相等才会造成假匹配，概率 $\le (1/n{)}^k={10}^{-5k}$。

要求 ${10}^{-5k}<{10}^{-30}\Rightarrow 5k>30\Rightarrow k>6$，故取 $k=7$ 次（若按"$\le {10}^{-30}$"则 $k=6$）。

每个指纹是一个 $<2n^2=2\times {10}^{10}$ 的素数（或其下的指纹值），位数 $\lceil {\log }_2(2n^2)\rceil =1+2{\log }_{2}n=1+2\times 5\times 3.32\approx 35$ 比特。

共传送约 $k\times 35\approx 7\times 35=245$ 比特（取 $k=6$ 则约 210 比特）。

---

R3. 最少期望提问次数（Huffman 决策）。

设计一种策略，使在下面的游戏中，期望提问的平均次数最少（请给出你得到这一策略的过程）。

• 版本 A（来源：样题1 试卷1 试卷3 七）：

  一副纸牌，由一张 A，两张 2，三张 3，直到 9 张 9 组成。有人从洗过的这副牌中抽出一张，你需要问一连串用是或否来回答的问题来确定这张牌的点数。

• 版本 B（来源：样题2 试卷2 六，5 分）：

  一个黑盒内共有 1 个红球，2 个蓝球，3 个绿球，4 个黄球，5 个黑球，6 个白球，7 个紫球。有一个人从黑盒内随机拿出一个球，另一个人被蒙上眼睛，只能通过一连串用是或否来回答的问题来确定球的颜色，问该蒙眼人的提问策略。

【解】 这是最优前缀码 / 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$，得各颜色码长后，期望提问次数 $={\displaystyle \frac{\sum (\text{频数}\times \text{码长})}{28}}$（约 2.7 次）。
• 版本 A 频数 $\{1,2,\dots ,9\}$（和 45）同法构造 Huffman 树，期望次数 $={\displaystyle \frac{\sum (\text{频数}\times \text{码长})}{45}}$。

结论：Huffman 树给出的判定策略即期望提问次数最少的策略。

---

十三、NP 完全性证明题（来源：试卷6 Q5，25 分，中英双语）

N1.（04 级研究生做）

We know the Hamiltonian cycle problem is NP-complete. HAM-CYCLE = {⟨G⟩ : G is a Hamiltonian graph}. Prove that the traveling-salesman problem (TSP) is NP-complete. Here, TSP = {⟨G,c,k⟩ : G=(V,E) is a complete graph, c is a function from V×V→Z, k∈Z, and G has a traveling-salesman tour with cost at most k}.

我们知道哈密尔敦循环问题是 NP 完全问题。哈密尔敦循环函数 = {⟨G⟩ : G 是一个哈密尔敦图}。证明旅行商问题（TSP）是个 NP 完全问题。此处，TSP = {⟨G,c,k⟩ : G=(V,E) 是个完全图，c 是个 V×V→Z、k∈Z 的函数，G 是个耗值最多为 k 的旅行商路径}。

【证明要点】

1. TSP ∈ NP：给定一条访问序列（证书），多项式时间内累加边权并验证"是否构成回路且总耗值 $\le k$"。
2. HAM-CYCLE ${\le }_p$ TSP：由图 $G=(V,E)$ 构造完全图 $G^{\prime }=(V,E^{\prime })$，并定义权 $c(u,v)=0$（若 $(u,v)\in E$）、$=1$（否则），取 $k=0$。则 $G$ 有 Hamilton 回路 $⟺G^{\prime }$ 有耗值 $\le 0$ 的旅行商回路。该构造是多项式时间的。

结合 1、2，TSP 是 NP 完全的。$◼$

N2.（02 级本科生做）

We know the circuit-satisfiability problem is NP-complete. Prove that the Satisfiability of boolean formulas is NP-complete.

我们知道电路可满足性问题是个 NP 完全问题。证明布尔公式的可满足性是 NP 完全的。

【证明要点】

1. SAT ∈ NP：给定一组变量真值赋值（证书），多项式时间代入求值即可验证公式是否为真。
2. CIRCUIT-SAT ${\le }_p$ SAT：对电路的每个门引入一个变量，为每个门写出刻画其输入输出关系的子句（如 AND/OR/NOT 门的等价合取式），整体合取并附加"输出 = 1"。该公式可满足 $⟺$ 原电路可满足，且转换规模为多项式。

结合 1、2，SAT 是 NP 完全的。$◼$

补充（试卷7 整理）：常见 NP（完全）问题——电路可满足性、布尔公式可满足性、3-CNF-SAT、团问题 (Clique)、顶点覆盖、Hamilton 回路、TSP、子集和问题。

---

十四、遗传算法题（来源：merged 五，8 分 + 完整解答）

某推销员要从城市 $v_1$ 出发，访问其它城市 $v_2,v_3,\dots ,v_6$ 各一次且仅一次，最后返回 $v_1$。各城市间的距离信息由矩阵 $D$ 给出。问：该推销员应如何选择路线，才能使总的行程最短？

请采用遗传算法求解该问题，写出算法的求解过程（每轮填写第 $x$ 轮计算表，并在注释一栏概要解释交叉运算的切点位置、不合法编码的修复方法、变异策略等），算法结束时输出历史最佳个体。要求：

• 状态表达：用顺序编码（$v_1$ 固定处于编码第一位）；
• 目标函数：路线长度；
• 种群规模：4；
• 初始种群：可按任意策略自行设定；
• 交叉算子：采用双切点交叉，种群中所有个体均参与，个体 1 与 2 交叉、3 与 4 交叉。每组交叉随机生成两个切点，若交叉导致编码不合法，则修复该编码；
• 变异算子：每轮任选 1 个个体变异，变异方法自拟（例如改变一个基因的位置）；
• 复制和选择策略：将本轮遗传计算前的种群和遗传计算后的种群一起按适应值排序，挑选其中适应度最好的 4 个个体作为新的种群；
• 结束条件：算法执行 2 轮，算法结束时输出历史最佳个体的编码及其适应值。

【解答要点（据原卷手算表）】

• 编码：如 123456 表示 $v_1\to v_2\to v_3\to v_4\to v_5\to v_6\to v_1$；适应值取路线总长（越小越好）。
• 流程：初始种群 → 双切点交叉（选中间/前若干位为交叉段）→ 对产生重复城市的非法编码用映射关系修复 → 变异（交换某两位基因）→ 合并父子代按适应值排序保留最优 4 个。
• 结果：两轮后历史最佳个体 126543，即 $v_1\to v_2\to v_6\to v_5\to v_4\to v_3\to v_1$，适应值（总路程）= $10+21+12+10+4+23=80$。
• 注释：修复方法 = 按交叉切点建立映射、对非法位按映射恢复；切点位置 = 划分交叉段的两个位置。

---

十五、作业题与其它（来源：HW1、试卷6、试卷7）

O1. Josephus（约瑟夫斯）问题非递推公式。（来源：HW1 五）

请给出约瑟夫斯问题的非递推公式 $J(n)$，并证明之。其中，$n$ 为最初总人数，$J(n)$ 为最后幸存者的最初编号。（每报到 2 出局，即 $m=2$。）

【结论】 递推 $J(2n)=2J(n)-1,J(2n+1)=2J(n)+1,J(1)=1$。非递推闭式：设 $n=2^m+k(0\le k<2^m)$，则

$$\boxed{{\displaystyle J(n)=2k+1}}.$$

等价地：把 $n$ 写成二进制 $n=(b_m{b}_{m-1}\cdots b_0{)}_2$，则 $J(n)$ 为 $n$ 的二进制循环左移一位。用数学归纳法可证（对 $k$ 的奇偶分别代入递推即得 $2k+1$）。 推广：每报 $m$ 出局时，$J(n,m)=(J(n-1,m)+m)modn,J(1,m)=0$。

---

O2. HeapPermute 全排列算法的正确性与时间效率。（来源：HW1 三）

分析以下生成排列算法的正确性和时间效率：

HeapPermute(n)
//实现生成排列的 Heap 算法
//输入：一个正整数 n 和一个全局数组 A[1..n]
//输出：A 中元素的全排列
if n = 1
    write A
else
    for i ← 1 to n do
        HeapPermute(n-1)
        if n is odd
            swap A[1] and A[n]
        else swap A[i] and A[n]

【正确性】 归纳可证：$n$ 为偶数时，HeapPermute(n) 输出全排列后数组循环右移一位；$n$ 为奇数时输出后数组顺序不变。由此每次循环都能把"前 $n-1$ 个元素之一"换到第 $n$ 位，从而 $n$ 次循环输出 $A[1..n]$ 的全部排列。 【时间效率】 递推 $f(n)=nf(n-1)+n$，解得 $f(n)=n!+\lfloor n!e\rfloor$ 量级，故时间复杂度 $\mathrm{\Theta }(n!)$（与排列总数同阶）。

---

O3. Prim 与 Kruskal 算法的集成。（来源：HW1 二）

由于 Prim 算法和 Kruskal 算法设计思路的不同，导致了其对不同问题实例的效率对比关系的不同。请简要论述： 1、如何将两种算法集成，以适应问题的不同实例输入； 2、你如何评价这一集成的意义？

【答案】 Prim 基于顶点扩展，适合顶点少的稠密图；Kruskal 基于边排序，适合边少的稀疏图。集成方法：先判断输入图的稀疏/稠密程度（如比较 $|E|$ 与 $|V{|}^2$），据此选择相应算法处理。意义：没有万能算法，"具体问题具体分析"地按图的特征选择策略，能充分发挥算法的效率，更好地解决具体问题。

---

O4. 整数规划（电脑组装）。（来源：试卷6 Q3，20 分）

一个电脑公司要在一周内（150 小时）组装个人电脑和笔记本，一台个人电脑能挣 50 元，一台笔记本能挣 40 元。组装一台个人电脑需花 3 小时并占用 8 平米空间，组装一台笔记本需 5 小时并占用 5 平米空间。另外，因缺少 CPU，公司最多只能组装 20 台笔记本。此电脑公司现有 300 平米的场所。给出一个算法实现获得最大利润的组装方案。

【建模】 $max50x+40y$，约束 $3x+5y\le 150,8x+5y\le 300,0\le y\le 20,x,y\ge 0$ 且为整数。可用整数规划 / 分支限界或动态规划求解。

---

O5. 矩形切割（条带装箱 Strip Packing）。（来源：试卷6 Q4，20 分）

在木材玻璃加工厂里，矩形构件得从大张材料里切割下来。给定一套矩形构件和一大张矩形材料（宽 W × 高 H），目的是使所用材料的高度 H 最小化。例如给定 5 个矩形构件，如何把它们从大张矩形材料中切割下来，使得高 H 最小化？给出一个算法找到获得最小高度的解决方案，你算法的运行时间是什么？

【要点】 该问题为 NP 难；常用近似算法如 NFDH / FFDH（按高度降序的 Next-Fit / First-Fit 分层装箱），可分析其近似比与运行时间。

---

📌 复习优先级建议：判断题（§一，必考、陷阱多）→ 简答概念（§四：拟阵、P/NP、伪多项式、下界与性能比）→ 五大策略大题（§六~§十一：分治逆序对/股票、DP 矩阵链乘/LCS/投资/生产库存、贪心调度、回溯 SAT、分支限界中转贸易）。这些在 2011–2020 各卷中反复出现，是得分核心。