算法设计与分析
复习指南
作者：FuZY
时间：June 10, 2025
版本：V1-正式版
邮箱：[email protected]
在没有结束前，总要做很多没有意义的事，这样才可以在未来某一天，用这些无意义的事去堵住
那些讨厌的缺口
前言
资料说明
本书参考了《算法设计与分析》（第三版）的内容，方便学习和复习。本书的内容主要包括分治法、贪心
法、动态规划、回溯法、分支限界法等算法设计与分析的基本方法，以及它们在实际问题中的应用。
使用说明
本资料仅供学习和交流使用，禁止用于任何商业用途。
本资料的内容仅供参考，作者不对任何因使用本资料而产生的后果负责。
禁止将本资料用于任何不正当的用途，包括但不限于考试作弊、抄袭等行为。
资料备份
Github 连接：https://ifuzyi.github.io/NOTES/算法设计与分析.html
网站连接：https://study.fuzy.site
QQ 群：1019314204
FuZY
2025 年 6 月 1 日
目录
第 1 章 算法分析基础 1
1.1 算法复杂度 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 1
1.1.1 时间复杂度 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 1
1.1.2 空间复杂度 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 1
1.2 渐近表示法 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 2
1.2.1 大 𝑂 符号 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 2
1.2.2 Ω 符号. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 2
1.2.3 Θ 符号. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 2
1.2.4 小 𝜔 符号 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 3
1.2.5 时间复杂度分类 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 3
第 2 章 分治法 4
2.1 一般方法 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 4
2.1.1 基本思想 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 4
2.1.2 算法分析 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 4
2.2 二分搜索 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 5
2.2.1 基本思想 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 5
2.2.2 对半搜索 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 5
2.2.3 二叉判定树 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 5
2.3 排序问题 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 6
2.3.1 合并排序 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 6
2.3.2 快速排序 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 7
第 3 章 贪心法 8
3.1 一般方法 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 8
3.2 背包问题 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 8
3.3 最佳合并模式 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 9
3.3.1 𝐾 路合并 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 9
3.4 最小代价生成树 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 10
3.4.1 普里姆算法 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 10
3.4.2 克鲁斯卡尔算法 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 10
3.5 单源最短路径 * . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 10
3.5.1 迪杰特斯拉算法 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 10
第 4 章 动态规划法 11
4.1 一般方法 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 11
4.2 多段图问题 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 11
4.3 关键路径问题 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 12
4.4 弗洛伊德算法 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 13
4.5 最长公共子序列 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 15
4.6 0-1 背包问题 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 15
第 5 章 回溯法 17
5.1 一般方法 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 17
5.2 n-皇后问题. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 17
5.3 子集和数 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 18
5.3.1 子集和数算法. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 18
第 6 章 分支限界法 20
6.1 一般方法 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 20
6.2 迷问题 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 21
6.2.1 LC 分枝限界法求解 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 21
6.3 分支限界法最优解 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 22
6.4 带时限的作业排序 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 22
第 ii 页
第 1 章 算法分析基础
第 1 章 算法分析基础
1.1 算法复杂度
1.1.1 时间复杂度
时间复杂度（Time Complexity）是衡量算法执行时间随输入规模 n 增长的变化趋势的指标。
算法运行时间：
𝑇 (𝑛, 𝐼) =
𝑚
𝑖=1
𝛼
𝑖
𝛽
𝑖
(𝑛, 𝐼)
𝛼
𝑖
：第 𝑖 个基本操作的执行时间
𝛽
𝑖
(𝑛, 𝐼)：第 𝑖 个基本操作的执行次数
𝑚：基本操作的个数
𝑛：输入规模
𝐼
：输入实例
𝑇 (𝑛, 𝐼)：算法的运行时间
最好时间复杂度：𝐵(𝑛) = min 𝑇 (𝑛, 𝐼)|𝐼 ∈ 𝐼 (𝑛)
最坏时间复杂度：𝑊 (𝑛) = max 𝑇 (𝑛, 𝐼)|𝐼 ∈ 𝐼 (𝑛)
平均时间复杂度：𝐴(𝑛) =
𝐼 ∈𝐼 (𝑛)
𝑃(𝐼)𝑇 (𝑛, 𝐼)，其中 𝑃(𝐼) 为输入实例 𝐼 的概率。
1.1.2 空间复杂度
空间复杂度（Space Complexity）是衡量算法在运行过程中临时占用存储空间大小的指标。
第 1 页
第 1 章 算法分析基础 1.2 渐近表示法
1.2 渐近表示法
1.2.1 大 𝑂 符号
定义 1.2.1
♣
设有非负函数 𝑓 (𝑛) 和 𝑔(𝑛)，如果存在正的常数 𝑐 > 0 和 𝑛
0
，使得当 𝑛 ≥ 𝑛
0
时，有 𝑓 (𝑛) ≤ 𝑐𝑔(𝑛)，则记为
𝑓 (𝑛) = 𝑂(𝑔(𝑛))，称为大 𝑂 记号。
定理 1.2.1
♡
如果 𝑓 (𝑛) = 𝑎
𝑚
𝑛
𝑚
+ 𝑎
𝑚−1
𝑛
𝑚−1
+ · · · + 𝑎
1
𝑛 + 𝑎
0
，其中 𝑎
𝑚
≠ 0，则 𝑓 (𝑛) = 𝑂(𝑛
𝑚
)。
例题 1.1.
证明 𝑓 (𝑛) = 𝑎𝑛 + 𝑏 = 𝑂(𝑛)
取 𝑐 = 𝑎 + 1，𝑛
0
= 𝑏，当 𝑛 ≥ 𝑛
0
时，有 𝑓 (𝑛) = 𝑎𝑛 + 𝑏 ≤ (𝑎 + 1)𝑛，所以 𝑓 (𝑛) = 𝑂(𝑛)。
例题 1.2.
证明 𝑓 (𝑛) = 𝑎𝑛
2
+ 𝑏 ≠ 𝑂(𝑛)
使用反证法，假定存在 𝑐 > 0 和 𝑛
0
，使得当 𝑛 ≥ 𝑛
0
时，𝑎𝑛
2
+ 𝑏 ≤ 𝑐𝑛 始终成立。
则有 𝑎𝑛 + 𝑏/𝑛 ≤ 𝑐，即 𝑛 ≤ 𝑐/𝑎 − 𝑏/(𝑎𝑛) 总成立。
取 𝑛 = 𝑐/𝑎 + 1 时，该不等式不成立。
1.2.2 Ω 符号
定义 1.2.2
♣
设有非负函数 𝑓 (𝑛) 和 𝑔(𝑛)，如果存在正的常数 𝑐 > 0 和 𝑛
0
，使得当 𝑛 ≥ 𝑛
0
时，有 𝑓 (𝑛) ≥ 𝑐𝑔(𝑛)，则记为
𝑓 (𝑛) = Ω(𝑔(𝑛))，称为 Σ 记号。
定理 1.2.2
♡
如果 𝑓 (𝑛) = 𝑎
𝑚
𝑛
𝑚
+ 𝑎
𝑚−1
𝑛
𝑚−1
+ · · · + 𝑎
1
𝑛 + 𝑎
0
，其中 𝑎
𝑚
≠ 0，则 𝑓 (𝑛) = Ω(𝑛
𝑚
)。
1.2.3 Θ 符号
定义 1.2.3
♣
设有非负函数 𝑓 (𝑛) 和 𝑔(𝑛)，如果存在正的常数 𝑐
1
, 𝑐
2
> 0 和 𝑛
0
，使得当 𝑛 ≥ 𝑛
0
时，有 𝑐
1
𝑔(𝑛) ≤ 𝑓 (𝑛) ≤ 𝑐
2
𝑔(𝑛)，
则记为 𝑓 (𝑛) = Θ(𝑔(𝑛))，称为 Θ 记号。
定理 1.2.3
♡
如果 𝑓 (𝑛) = 𝑎
𝑚
𝑛
𝑚
+ 𝑎
𝑚−1
𝑛
𝑚−1
+ · · · + 𝑎
1
𝑛 + 𝑎
0
，其中 𝑎
𝑚
≠ 0，则 𝑓 (𝑛) = Θ(𝑛
𝑚
)。
第 2 页
第 1 章 算法分析基础 1.2 渐近表示法
1.2.4 小 𝜔 符号
定义 1.2.4
♣
𝑓 (𝑛) = 𝑜(𝑔(𝑛)) 当且仅当 𝑓 (𝑛) = 𝑂(𝑔(𝑛))，且 𝑓 (𝑛) ≠ Σ(𝑔(𝑛))。
1.2.5 时间复杂度分类
多项式时间复杂度：
𝑂(1) < 𝑂(log 𝑛) < 𝑂(𝑛) < 𝑂(𝑛 log 𝑛) < 𝑂(𝑛
2
) < 𝑂 (𝑛
3
)
指数时间复杂度：
𝑂(2
𝑛
) < 𝑂 (𝑛!) < 𝑂 (𝑛
𝑛
)
练习
解
练习 1
设 𝑓
1
(𝑛) = 𝑂(𝑔
1
(𝑛))， 𝑓
2
(𝑛) = 𝑂(𝑔
2
(𝑛))，证明以下结论成立。
1. 𝑓
1
(𝑛) + 𝑓
2
(𝑛) = 𝑂(𝑔
1
(𝑛) + 𝑔
2
(𝑛))
2. 𝑓
1
(𝑛) + 𝑓
2
(𝑛) = 𝑂(max(𝑔
1
(𝑛), 𝑔
2
(𝑛)))
1. 𝑓
1
(𝑛) = 𝑂(𝑔
1
(𝑛)) =⇒ 当 𝑛 > 𝑛
1
时， 𝑓
1
(𝑛) ≤ 𝑐
1
𝑔
1
(𝑛)，
𝑓
2
(𝑛) = 𝑂(𝑔
2
(𝑛)) =⇒ 当 𝑛 > 𝑛
2
时， 𝑓
2
(𝑛) ≤ 𝑐
2
𝑔
2
(𝑛)
取 𝑐 = max(𝑐
1
, 𝑐
2
)，𝑛
0
= max(𝑛
1
, 𝑛
2
)，
当 𝑛 > 𝑛
0
时， 𝑓
1
(𝑛) + 𝑓
2
(𝑛) ≤ 𝑐
1
𝑔
1
(𝑛) + 𝑐
2
𝑔
2
(𝑛) ≤ 𝑐(𝑔
1
(𝑛) + 𝑔
2
(𝑛))
命题得证
2. 𝑓
1
(𝑛) = 𝑂(𝑔
1
(𝑛)) =⇒ 当 𝑛 > 𝑛
1
时， 𝑓
1
(𝑛) ≤ 𝑐
1
𝑔
1
(𝑛)，
𝑓
2
(𝑛) = 𝑂(𝑔
2
(𝑛)) =⇒ 当 𝑛 > 𝑛
2
时， 𝑓
2
(𝑛) ≤ 𝑐
2
𝑔
2
(𝑛)
取 𝑐 = max(𝑐
1
, 𝑐
2
)，𝑛
0
= max(𝑛
1
, 𝑛
2
)，
当
𝑛 > 𝑛
0
时，
𝑓
1
(
𝑛
) +
𝑓
2
(
𝑛
) ≤
𝑐
1
𝑔
1
(
𝑛
) +
𝑐
2
𝑔
2
(
𝑛
) ≤
𝑐
(
𝑔
1
(
𝑛
) +
𝑔
2
(
𝑛
)) ≤
2
𝑐
(
max
(
𝑔
1
(
𝑛
)
, 𝑔
2
(
𝑛
)))
命题得证
第 3 页
第 2 章 分治法
第 2 章 分治法
2.1 一般方法
2.1.1 基本思想
分治法（Divide and Conquer）是一种算法设计范式，可以将一个复杂的问题分解成若干个规模较小、相互
独立、类型相同的子问题。
分治法求解的要素：
问题能够按照某种方式分解成若干个子问题。
子问题足够小时可以直接求解。
能够将子问题的解合并成原问题的解。
2.1.2 算法分析
定理 2.1.1
♡
设 𝑎，𝑏，𝑐 和 𝑘 为常数，𝑇 (𝑛) = 𝑎𝑇 (𝑛/𝑏) + 𝑐𝑛
𝑘
，𝑇 (1) = 𝑐，则
𝑇 (𝑛) =
Θ(𝑛
log
𝑏
𝑎
) 𝑎 > 𝑏
𝑘
即 log
𝑏
𝑎 > 𝑘
Θ(𝑛
𝑘
log 𝑛) 𝑎 = 𝑏
𝑘
即 log
𝑏
𝑎 = 𝑘
Θ(𝑛
𝑘
) 𝑎 < 𝑏
𝑘
即 log
𝑏
𝑎 < 𝑘
第 4 页
第 2 章 分治法 2.2 二分搜索
2.2 二分搜索
2.2.1 基本思想
对于一个有序表 (𝑎
0
, 𝑎
1
. . . . , 𝑎
𝑛−1
)，假定以元素 𝑎
𝑚
为划分点，将原表分成 𝑎
1
, 𝑎
2
, . . . , 𝑎
𝑚−1
和 𝑎
𝑚+1
, . . . , 𝑎
𝑛
两部分。将 𝑎
𝑚
与指定元素 𝑥 进行比较：
1. 当 𝑥 < 𝑎
𝑚
时，若 𝑥 在表中，则 𝑥 在 𝑎
1
, 𝑎
2
, . . . , 𝑎
𝑚−1
中。
2. 当 𝑥 = 𝑎
𝑚
时，查找成功。
3. 当 𝑥 > 𝑎
𝑚
时，若 𝑥 在表中，则 𝑥 在 𝑎
𝑚
+
1
, . . . , 𝑎
𝑛
中。
2.2.2 对半搜索
对半搜索是一种二分搜索，设当前搜索的子表为 (𝑎
𝑙𝑒 𝑓 𝑡,𝑎𝑙𝑒 𝑓 𝑡+1,...,𝑎
𝑟𝑖𝑔ℎ𝑡
)，令 𝑚 = (𝑙𝑒 𝑓 𝑡 + 𝑟𝑖𝑔ℎ𝑡)/2，这种二分
搜索被称为对半搜索。
2.2.3 二叉判定树
二叉判定树模型：
1. 指定元素 𝑥 与表中元素 𝑙 [𝑚] 进行比较，表现为二叉判定树中的一个内节点，用一个圆形节点表示，并用 𝑚
标识。如果 𝑥 = 𝑙 [𝑚]，则算法在该节点处在、成功终止。
2. 二叉判定树的根节点，代表算法中首次比较的元素 𝑙 [𝑚]，用 𝑚 标识。
3. 若 𝑥 < 𝑙 [𝑚]，算法在左子树中继续搜索。若 𝑥 > 𝑙[𝑚]，算法在右子树中继续搜索。
4. 若 𝑥 < 𝑙[𝑚] 且算法终止，节点 𝑚 的左孩子以标号 𝑚 − 1 的方形节点表示；若 𝑥 > 𝑙 [𝑚] 且算法终止，节点 𝑚
的右孩子以标号 𝑚 的方形节点表示。方形节点称为外节点。
5. 如果搜索成功，在内节点处终止，否则在外节点处终止。
4
1
0
-1
0
2
1
3
2
3
7
5
4
6
5
6
8
7 9
8
9
图 2.1: 对半搜索二叉判定树 (n=10)
性质 1.
具有 𝑛(𝑛 > 0) 个内节点的对半搜索二叉判定树的左子树上有 ⌈(𝑛 − 1)/2⌉ 个内节点，右子树上有 ⌊𝑛/2⌋ 个
内节点。
性质 2.
具有 𝑛(𝑛 > 0) 个内节点的对半搜索二叉判定树的高度为 ℎ = ⌊log
2
𝑛⌋ + 1 或⌈log
2
(𝑛 + 1)⌉（不记外节点）。
第 5 页
第 2 章 分治法 2.3 排序问题
性质 3.
若 𝑛 = 2
𝑘
− 1，则对半搜索二叉判定树是满二叉树。
性质 4.
若 𝑛 = 2
ℎ
− 1，则对半搜索二叉判定树的外节点均在 ℎ + 1 层上，否则，在 ℎ 层或 ℎ + 1 层上，ℎ = ⌊log 𝑛⌋ + 1。
定理 2.2.1
♡
对半搜索算法在搜索成功的平均时间复杂度为 Θ(log 𝑛)。
2.3 排序问题
2.3.1 合并排序
初始时将待排序的
𝑛
个数据元素看作
𝑛
个待合并有序序列，每个序列中只包含一个数据元素；将每
𝑚
个待
合并序列合并成一个大的有序序列（在最后一次合并中，序列个数可能少于 𝑚）；重复合并过程，直到所有的数
据元素都属于同一个有序序列为止。当 𝑚 = 2 时，上述合并排序过程称为两路合并排序算法。
第 1 趟排序：对 𝑛 个有序序列 (𝐷[0]), (𝐷 [1]), . . . , (𝐷[𝑛 − 1]) 进行：
合并 (𝐷 [0]) 和 (𝐷 [1])，得到 (𝐷 [0], 𝐷 [1])
合并 (𝐷 [2]) 和 (𝐷 [3])，得到 (𝐷 [2], 𝐷 [3])
· · ·
如果 𝑛 是偶数，合并最后两个序列；否则保留最后一个序列
第 2 趟排序：对 ⌈𝑛/2⌉ 个有序序列 (𝐷 [0], 𝐷 [1]), (𝐷 [2], 𝐷 [3]), . . . 进行：
合并 (𝐷 [0], 𝐷 [1]) 和 (𝐷 [2], 𝐷 [3])，得到 (𝐷 [0], . . . , 𝐷 [3])
合并 (𝐷 [4], 𝐷 [5]) 和 (𝐷 [6], 𝐷 [7])，得到 (𝐷 [4], . . . , 𝐷 [7])
· · ·
如果 ⌈𝑛/2⌉ 是偶数，合并最后两个序列；否则保留最后一个序列
· · · · · ·
第 𝑖 趟排序：对
⌈
𝑛
2
𝑖−1
⌉
个有序序列进行：
合并 (𝐷 [0], . . . , 𝐷 [2
𝑖−1
− 1]) 和 (𝐷 [2
𝑖−1
], . . . , 𝐷 [2
𝑖
− 1])，得到 (𝐷 [0], . . . , 𝐷 [2
𝑖
− 1])
· · ·
如果
⌈
𝑛
2
𝑖−1
⌉
是偶数，合并最后两个序列；否则保留最后一个序列
0 1 2 3 4 5 6 7
[ 8 7 6 5 4 3 2 1 ]
↙ ↘
[ 8 7 6 5 ] [ 4 3 2 1 ]
↙ ↘ ↙ ↘
[ 8 7 ] [ 6 5 ] [ 4 3 ] [ 2 1 ]
↙ ↘ ↙ ↘ ↙ ↘ ↙ ↘
[ 8 ] [ 7 ] [ 6 ] [ 5 ] [ 4 ] [ 3 ] [ 2 ] [ 1 ]
表 2.1: 分解过程
0 1 2 3 4 5 6 7
[ 1 2 3 4 5 6 7 8 ]
↗ ↖
[ 5 6 7 8 ] [ 1 2 3 4 ]
↗ ↖ ↗ ↖
[ 7 8 ] [ 5 6 ] [ 3 4 ] [ 1 2 ]
↗ ↖ ↗ ↖ ↗ ↖ ↗ ↖
[ 8 ] [ 7 ] [ 6 ] [ 5 ] [ 4 ] [ 3 ] [ 2 ] [ 1 ]
表 2.2: 合并过程
合并排序时间复杂度：𝑇 (𝑛) = 𝑂(𝑛 log 𝑛)。
第 6 页
第 2 章 分治法 2.3 排序问题
2.3.2 快速排序
在待排序序列中选择一个分割元素，将待排序序列中所有比分割元素关键字小或相等的元素移动到分割元
素左侧位置，将待排序序列中所有比分割元素大的元素移动到分割元素右侧位置，然后将分割元素左侧所有元
素都看作一个待排序子序列，重复上述过程，直到这些元素完全有序，最后将分割元素右侧所有元素看作一个
待排序子序列，重复上述过程，直到这些元素完全有序。
设待排序序列（或子序列）包含数据元素 𝐷 [low], 𝐷 [low + 1], . . . , 𝐷 [high]，low 和 high 标识待排序序列元
素下标范围。选择 𝐷 [low] 为分割元素，设置 2 个游动标识 𝑖 和 𝑗。初始时令 𝑖 = low, 𝑗 = high + 1。约定标识 𝑖 前
进方式是只能向序列右侧移动；标识 𝑗 前进方式是只能向序列左侧移动。
i 标识 𝑖 开始前进，每前进一步，将当前 𝐷 [𝑖] 关键字与 𝐷 [low] 关键字进行比较，如果 𝐷 [𝑖] 关键字小于 𝐷 [low]
关键字，则 𝑖 继续前进，否则停止前进；
ii 标识 𝑗 开始前进，每前进一步，将当前 𝐷 [ 𝑗 ] 关键字与 𝐷 [low] 关键字进行比较，如果 𝐷[ 𝑗] 关键字大于
𝐷 [low] 关键字，则 𝑗 继续前进，否则停止前进；
iii 如果 𝑖 ≥ 𝑗，交换 𝐷 [low] 与 𝐷 [ 𝑗]，退出；否则，交换 𝐷 [𝑖] 与 𝐷 [ 𝑗]，回到步骤 1。
交换次数 0 1 2 3 4 5 6 7 ∞
初始 4 4 3 3 2 2 1 1 ∞
𝑖 → ← 𝑗
1 4 1 3 3 2 2 1 4 ∞
𝑖 → ← 𝑗
2 1 1 3 3 2 2 4 4 ∞
𝑗 𝑖
表 2.3: 分划操作
排序次数 0 1 2 3 4 5 6 7
初始 [ 4 4 3 3 2 2 1 1 ]
1 [ 1 1 3 3 2 2 ] 4 [ 4 ]
2 [ 1 ] 1 [ 3 3 2 2 ] 4 [ 4 ]
3 1 1 [ 3 3 2 2 ] 4 [ 4 ]
4 1 1 [ 2 2 ] 3 [ 3 ] 4 [ 4 ]
5 1 1 [ 2 ] 2 3 [ 3 ] 4 [ 4 ]
6 1 1 2 2 3 [ 3 ] 4 [ 4 ]
7 1 1 2 2 3 3 4 [ 4 ]
8 1 1 2 2 3 3 4 4
表 2.4: 快速排序
快速排序时间复杂度：
𝑂(𝑛
2
) 最坏情况
𝑂(𝑛 log 𝑛) 平均情况
𝑂(𝑛 log 𝑛) 最好情况
第 7 页
第 3 章 贪心法
第 3 章 贪心法
3.1 一般方法
贪心法（Greedy Algorithm）是一种通过 局部最优选择的累积 来逼近全局最优解的算法设计范式。其核心
在于每一步选择当前状态下 最有利的决策 （即局部最优解），并期望通过迭代最终得到全局最优解。
贪心法求解的要素：
贪心选择性质 ：问题的全局最优解可通过一系列局部最优选择得到。
最优子结构性质 ：问题的最优解包含其子问题的最优解。子问题的局部最优解能组合为原问题的
解。
3.2 背包问题
已知一个载重为
𝑀
的背包和
𝑛
件物品，物品重量
𝑤
𝑖
价值
𝑝
𝑖
，物品可以分割，背包问题的解用一个
𝑛
−
1
元
组：𝑋 = (𝑥
0
, 𝑥
1
, . . . , 𝑥
𝑛−1
), 0 ≤ 𝑥
𝑖
≤ 1, 0 ≤ 𝑖 < 𝑛，每个 𝑥
𝑖
是第 𝑖 件物品装入背包的部分。
可行解的约束条件是：
𝑛−1
𝑖=0
𝑤
𝑖
𝑥
𝑖
≤ 𝑀 𝑤
𝑖
> 0, 0 ≤ 𝑥
𝑖
≤ 1, 0 ≤ 𝑖 < 𝑛
最优解的目标函数是：
max
𝑛−1
𝑖=0
𝑝
𝑖
𝑥
𝑖
𝑝
𝑖
> 0, 0 ≤ 𝑥
𝑖
≤ 1, 0 ≤ 𝑖 < 𝑛
例题 3.1.
设有物品 (𝑤
0
, 𝑝
0
), (𝑤
1
, 𝑝
1
), . . . , (𝑤
𝑛−1
, 𝑝
𝑛−1
)，其中 𝑤
𝑖
为物品的重量，𝑝
𝑖
为物品的价值。现有一个载重为
𝑀 的背包，求装入背包的物品的最优解。
将物品按照单位重量价值 𝑝
𝑖
/𝑤
𝑖
从大到小排序，设 𝑋 = (𝑥
0
, 𝑥
1
, . . . , 𝑥
𝑛−1
) 为背包中物品的装入情况，其中
𝑥
𝑖
为第 𝑖 件物品装入背包的部分，0 ≤ 𝑥
𝑖
≤ 1。依次将物品装入背包，直到背包满为止。设最后装入的物品
下标为 𝑘，装入部分为 𝑥
𝑘
，最优解 𝑋 = (1, . . . , 1, 𝑥
𝑘
, 0, . . . , 0)。
第 8 页
第 3 章 贪心法 3.3 最佳合并模式
3.3 最佳合并模式
最佳合并模式下，扩充二叉树的带权外路径长度最小。𝑊 𝑃𝐿 =
𝑛
𝑖=1
𝑤
𝑖
𝑙
𝑖
，其中 𝑛 为外节点数，𝑤
𝑖
是第 𝑖 个
外节点的权值，𝑙
𝑖
是从根节点到该节点的路径长度。
两路合并的最佳合并模式：
1. 设 𝑊 = {𝑤
1
, 𝑤
2
, . . . , 𝑤
𝑛
} 为权值集合，以每个权值为根节点值，构造 𝑛 棵只有根节点的二叉树。
2. 取出权值最小的两棵树，作为左右子树构造新二叉树，新二叉树的根节点值为子树的根节点值之和。
3. 重复步骤 2，直到只剩下最后一棵树。
3.3.1 𝐾 路合并
令 𝑛 为权值个数，当 𝑛 − 1 不是 𝐾 − 1 的倍数时，即 (𝑛 − 1) mod (𝐾 − 1) ≠ 0，需要补充 (𝐾 − 1) − (𝑛 − 1)
mod (𝐾 − 1) 个权值为零的“虚节点”。
1. 设 𝑊 = {𝑤
1
, 𝑤
2
, . . . , 𝑤
𝑛
} 为权值集合，补充虚节点。
2. 以每个权值为根节点值，构造 𝑛 棵只有根节点的 K 叉树。
3. 取出权值最小的 K 棵树，构造新 K 叉树，新 K 叉树的根节点值为子树的根节点值之和。
4. 重复步骤 3，直到只剩下最后一棵树。
5. 将虚节点删除，得到最终的 K 路合并树。
例题 3.2.
设有权值集合 𝑊 = {1, 2, 3, 4, 5, 6}，构造最优 3 路合并树。
𝑛 = 6，𝐾 = 3，𝑛 − 1 mod (𝐾 − 1) = 5 mod 2 = 1，需补充 1 个虚节点 0，权值集合为 𝑊 = {0, 1, 2, 3, 4, 5, 6}。
21
5
6
10
3
1 2
3
4
第 9 页
第 3 章 贪心法 3.4 最小代价生成树
3.4 最小代价生成树
3.4.1 普里姆算法
设 𝐺 = (𝑉, 𝐸) 为带权无向图，𝑉 为顶点集合，𝐸 为边集合。𝐹 = (𝑈, 𝑆) 是图 𝐺 的子图，是正在构造中的生
成树。普里姆算法从 𝑈 = {𝑣
0
}, 𝑆 = ∅ 开始，其中 𝑣
0
, 𝑣
0
∈ 𝑉 是任意选定的结点。每次寻找一条边 (𝑢, 𝑣)，使得
𝑢 ∈ 𝑈, 𝑣 ∈ 𝑉 − 𝑈，并且 (𝑢, 𝑣) 的权值最小。将边 (𝑢, 𝑣) 加入 𝑆，并将 𝑣 加入 𝑈。重复上述过程，直到 𝑈 = 𝑉。这时
𝑇 = (𝑉, 𝑆) 就是图 𝐺 的一颗最小代价生成树。
设无向图中结点数为 𝑛，普里姆算法的时间复杂度为 𝑂 (𝑛
2
)。
3.4.2 克鲁斯卡尔算法
设 𝐺 = (𝑉, 𝐸) 为带权无向图，𝑉 为顶点集合，𝐸 为边集合。𝐹 = (𝑈, 𝑆) 是图 𝐺 的子图，是正在构造中的生
成树。克鲁斯卡尔算法从 𝑆 = ∅ 开始, 在 𝐸 中选取权值最小的边 (𝑢, 𝑣)，并将其从 𝐸 中删除。如果 (𝑢, 𝑣) 的两个
端点不在同一连通分量中，则将 (𝑢, 𝑣) 加入 𝑆，并将 𝑢, 𝑣 所在的连通分量合并。重复上述过程，直到 𝑆 中有 𝑛 − 1
条边。这时 𝑇 = (𝑉, 𝑆) 就是图 𝐺 的一颗最小代价生成树。
设无向图中边数为 𝑒，克鲁斯卡尔算法的时间复杂度为 𝑂 (𝑒 log 𝑒)。
3.5 单源最短路径 *
3.5.1 迪杰特斯拉算法
设 𝑉 为图 𝐺 的顶点集合，𝐸 为图 𝐺 的边集合。集合 𝑆 存放已经求得最短路径的终点，则 𝑉 − 𝑆 为尚未求得
最短路径的终点集合。
1. 将源点 𝑠 加入 𝑆，并将源点到源点的距离设为 0，与源点相连的点到源点的距离设为边的权值。将其他点
到源点的距离设为无穷大。
2. 将 𝑉 − 𝑆 中与源点距离最小的点加入 𝑆，并更新与该点相连的点到源点的距离。
3. 重复步骤 2，直到 𝑆 = 𝑉 。
第 10 页
第 4 章 动态规划法
第 4 章 动态规划法
4.1 一般方法
动态规划（Dynamic Programming）是一种通过将问题分解为子问题并存储其解来避免重复计算的算法设计
范式。其核心在于通过 最优子结构 和 重叠子问题 来构建全局最优解。
动态规划求解的要素：
最优子结构性质：问题的最优解包含了其子问题的最优解
重叠子问题性质：递归算法求解问题时，每次产生的子问题并不总是新问题，有些子问题被反复计
算多次。
用动态规划算法求解问题的步骤：
1. 刻划最优解的结构特征；
2. 递归定义最优解值；
3. 以自底向上的方式计算最优解值；
4. 根据计算得到的信息构造一个最优解。
4.2 多段图问题
多段图问题 (multistage graph problem) 是一种特殊的有向无环图的最短路径问题.
带权有向图 G=(V,E) 具有如下特性：
1. 图中的结点被划分成 k 个互不相交的子集 𝑉𝑖 (1 ≤ 𝑖 ≤ 𝑘) 。其中 𝑉
1
只包含源点 𝑠，𝑉
𝑘
只包含汇点 𝑡。
2. 图中所有的边
< 𝑢, 𝑣 >
均满足：若
𝑢
∈
𝑉
𝑖
则
𝑣
∈
𝑉
𝑖+1
(
1
≤
𝑖
≤
𝑘
)
，每条边的权值为
𝑐
(
𝑢, 𝑣
)
。
3. 从 𝑠 到 𝑡 的路径长度是这条路径上边的权值之和。
4. 求从 𝑠 到 𝑡 的一条长度最短的路径。
多段图问题的向前递推公式为：
𝑐𝑜𝑠𝑡 (𝑘, 𝑡) = 0
𝑐𝑜𝑠𝑡 (𝑖, 𝑗) = min
𝑗 ∈𝑉
𝑖
, 𝑝∈𝑉
𝑖+1
⟨ 𝑗, 𝑝 ⟩ ∈𝐸
{
𝑐
𝑗, 𝑝
+ 𝑐𝑜𝑠𝑡 (𝑖 + 1, 𝑝)
}
, 0 ≤ 𝑖 ≤ 𝑘 − 1
第 11 页
第 4 章 动态规划法 4.3 关键路径问题
多段图问题的向后递推公式为：
𝐵𝑐𝑜𝑠𝑡 (1, 𝑠) = 0
𝐵𝑐𝑜𝑠𝑡 (𝑖, 𝑗) = min
𝑝∈𝑉
𝑖−1
, 𝑗 ∈𝑉
𝑖
⟨ 𝑝, 𝑗 ⟩ ∈ 𝐸
{
𝑐
𝑝, 𝑗
+ 𝐵𝑐𝑜𝑠𝑡 (𝑖 − 1, 𝑝)
}
, 1 < 𝑖 ≤ 𝑘
例题 4.1.
有多段图如下所示，求从源点 𝑠 到汇点 𝑡 的最短路径。
使用向前递推公式计算：
𝑐𝑜𝑠𝑡 (4, 𝐼) = 0
𝑐𝑜𝑠𝑡 (3, 𝐻) = min{𝑐
𝐻,𝐼
+ 𝑐𝑜𝑠𝑡 (4, 𝐼)} = 15 𝑑(3, 𝐻) = 𝐼
𝑐𝑜𝑠𝑡 (3, 𝐺) = min{𝑐
𝐺,𝐼
+ 𝑐𝑜𝑠𝑡 (4, 𝐼)} = 14 𝑑(3, 𝐺) = 𝐼
𝑐𝑜𝑠𝑡 (3, 𝐹) = min{𝑐
𝐹,𝐼
+ 𝑐𝑜𝑠𝑡 (4, 𝐼)} = 13 𝑑(3, 𝐹) = 𝐼
𝑐𝑜𝑠𝑡 (2, 𝐸) = min{𝑐
𝐸,𝐻
+ 𝑐𝑜𝑠𝑡 (3, 𝐻)} = 26 𝑑(2, 𝐸) = 𝐻
𝑐𝑜𝑠𝑡 (2, 𝐷) = min{𝑐
𝐷, 𝐻
+ 𝑐𝑜𝑠𝑡 (3, 𝐻), 𝑐
𝐷,𝐺
+ 𝑐𝑜𝑠𝑡 (3, 𝐺)} = 23 𝑑(2, 𝐷) = 𝐺
𝑐𝑜𝑠𝑡 (2, 𝐶) = min{𝑐
𝐶,𝐺
+ 𝑐𝑜𝑠𝑡 (3, 𝐺), 𝑐
𝐶,𝐹
+ 𝑐𝑜𝑠𝑡 (3, 𝐹)} = 20 𝑑(2, 𝐶) = 𝐹
𝑐𝑜𝑠𝑡 (2, 𝐵) = min{𝑐
𝐵,𝐹
+ 𝑐𝑜𝑠𝑡 (3, 𝐹)} = 19 𝑑(2, 𝐵) = 𝐹
𝑐𝑜𝑠𝑡 (1, 𝐴) = min{𝑐
𝐴,𝐸
+ 𝑐𝑜𝑠𝑡 (2, 𝐸), 𝑐
𝐴,𝐷
+ 𝑐𝑜𝑠𝑡 (2, 𝐷), 𝑐
𝐴,𝐶
+ 𝑐𝑜𝑠𝑡 (2, 𝐶), 𝑐
𝐴,𝐵
+ 𝑐𝑜𝑠𝑡 (2, 𝐵)} = 20 𝑑(1, 𝐴) = 𝐵
最短路径为 ( 𝐴, 𝑑(1, 𝐴) = 𝐵, 𝑑(2, 𝐵) = 𝐹, 𝑑 (3, 𝐹) = 𝐼)，
即最短路径为 𝐴 → 𝐵 → 𝐹 → 𝐼，路径长度为 20。
4.3 关键路径问题
关键路径法是求一个带权有向无环图中两节点的最长路径问题。关键路径问题是一个 AOE 网络问题。
1. AOE 网络是一个带权有向图 G=(V,E)，其中 V 是结点集，E 是边集。
2. 结点代表事件 (event)，有向边代表活动 (activity)。
3. 有向边的权代表活动持续时间 (duration)。
4. 入边代表的活动已经完成，出边代表的活动可以开始。
关键路径问题的求解步骤：
1. 事件 𝑖 的最早发生时间 𝑒𝑎𝑟𝑙𝑖𝑒𝑠𝑡 (𝑖)：从开始结点 𝑠 到结点 𝑖 的最长路径长度。
第 12 页
第 4 章 动态规划法 4.4 弗洛伊德算法
2. 事件 𝑖 的最迟发生时间 𝑙𝑎𝑡𝑒𝑠𝑡 (𝑖)：事件 𝑖 允许的最晚发生时间。等于 𝑒𝑎𝑟𝑙𝑖𝑒𝑠𝑡 (𝑛 − 1) 减去从结点 𝑖 到结点
𝑛 − 1 的最长路径长度。
3. 关键活动：若 𝑙𝑎𝑡𝑒𝑠𝑡 ( 𝑗 ) − 𝑒𝑎𝑟𝑙𝑖𝑒𝑠𝑡 (𝑖) = 𝑤(𝑖, 𝑗)，则边 < 𝑖, 𝑗 > 代表的活动是关键活动。关键活动组成的关键
路径上每个结点 (𝑖) 都有 𝑙𝑎𝑡𝑒𝑠𝑡 (𝑖) = 𝑒𝑎𝑟𝑙𝑖𝑒𝑠𝑡 (𝑖)。
递推公式：
𝑒𝑎𝑟𝑙𝑖𝑒𝑠𝑡 (0) = 0
𝑒𝑎𝑟𝑙𝑖𝑒𝑠𝑡 (𝑖) = max
𝑗 ∈ 𝑃(𝑖 )
{𝑒𝑎𝑟𝑙𝑖𝑒𝑠𝑡 ( 𝑗 ) + 𝑤(𝑖, 𝑗)} 0 < 𝑗 < 𝑛
𝑙𝑎𝑡𝑒𝑠𝑡 (𝑛 − 1) = 𝑒𝑎𝑟𝑙𝑖𝑒𝑠𝑡 (𝑛 − 1)
𝑙𝑎𝑡𝑒𝑠𝑡 (𝑖) = min
𝑗 ∈𝑆 (𝑖)
{𝑙𝑎𝑡𝑒𝑠𝑡 ( 𝑗) − 𝑤(𝑖, 𝑗)} 𝑜 ≤ 𝑖 < 𝑛 − 1
4.4 弗洛伊德算法
弗洛伊德算法（Floyd-Warshall Algorithm）是一种用于求解加权有向图中所有顶点对之间最短路径的算法。
它适用于有向图和无向图，并且可以处理负权边，但不能处理负权环。弗洛伊德算法的核心思想是通过动态规
划来逐步更新最短路径矩阵。其基本步骤如下：
递推关系:
𝑑
−1
[𝑖] [ 𝑗] =
0, 若𝑖 = 𝑗
𝑤(𝑖, 𝑗), 若(𝑖, 𝑗) ∈ 𝐸
∞, 若(𝑖, 𝑗) ∉ 𝐸
𝑑
𝑘
[𝑖] [ 𝑗] = min
{
𝑑
𝑘−1
[𝑖] [ 𝑗], 𝑑
𝑘−1
[𝑖] [𝑘] + 𝑑
𝑘−1
[𝑘] [ 𝑗]
}
, 1 ≤ 𝑘 ≤ 𝑛 − 1
𝑝𝑎𝑡ℎ
𝑘
[𝑖] [ 𝑗] =
𝑘, 若𝑑
𝑘
[𝑖] [ 𝑗] = 𝑑
𝑘−1
[𝑖] [𝑘] + 𝑑
𝑘−1
[𝑘] [ 𝑗]
𝑝𝑎𝑡ℎ
𝑘−1
[𝑖] [ 𝑗], 否则
其中 𝑑
𝑘
[𝑖] [ 𝑗] 表示从顶点 𝑖 到顶点 𝑗 经过前 𝑘 个顶点的最短路径长度，𝑝𝑎𝑡ℎ
𝑘
[𝑖] [ 𝑗] 表示从顶点 𝑖 到顶点 𝑗 的
最短路径经过的最后一个顶点。
从路径终点 𝑗 开始，其前一个节点是 𝑘 = 𝑝𝑎𝑡ℎ[𝑖] [ 𝑗]，再前一个节点为 𝑘 = 𝑝𝑎𝑡ℎ[𝑖] [𝑘],. . . ，直到起始点 𝑖 为
止，形成一条路径。
第 13 页
第 4 章 动态规划法 4.4 弗洛伊德算法
例题 4.2.
给定一个有向图，求所有顶点对之间的最短路径。
初始距离矩阵为：
𝑑 =
0 1 ∞ 4
∞ 0 8 2
3 5 0 7
∞ ∞ 6 0
𝑝𝑎𝑡ℎ =
−1 𝐴 −1 𝐴
−1 −1 𝐵 𝐵
𝐶 𝐶 −1 𝐶
−1 −1 𝐷 −1
经过顶点 𝐴 的最短路径矩阵为：
𝑑
𝐴
=
0 1 ∞ 4
∞ 0 8 2
3 4 0 7
∞ ∞ 6 0
𝑝𝑎𝑡ℎ
𝐴
=
−1 𝐴 −1 𝐴
−1 −1 𝐵 𝐵
𝐶 𝐴 −1 𝐶
−1 −1 𝐷 −1
经过顶点 𝐵 的最短路径矩阵为：
𝑑
𝐵
=
0 1 9 3
∞ 0 8 2
3 4 0 6
∞ ∞ 6 0
𝑝𝑎𝑡ℎ
𝐵
=
−1 𝐴 𝐵 𝐴
−1 −1 𝐵 𝐵
𝐶 𝐴 −1 𝐵
−1 −1 𝐷 −1
经过顶点 𝐶 的最短路径矩阵为：
𝑑
𝐶
=
0 1 9 3
11 0 8 2
3 4 0 6
9 10 6 0
𝑝𝑎𝑡ℎ
𝐶
=
−1 𝐴 𝐵 𝐵
𝐶 −1 𝐵 𝐵
𝐶 𝐴 −1 𝐵
𝐶 𝐶 𝐷 −1
经过顶点 𝐷 的最短路径矩阵为：
𝑑
𝐷
=
0 1 9 3
11 0 8 2
3 4 0 6
9 10 6 0
𝑝𝑎𝑡ℎ
𝐷
=
−1 𝐴 𝐵 𝐵
𝐶 −1 𝐵 𝐵
𝐶 𝐴 −1 𝐵
𝐶 𝐶 𝐷 −1
最终的最短路径矩阵为：
𝑃𝐴𝑇 𝐻 =
−1 𝐴 → 𝐵 𝐴 → 𝐵 → 𝐶 𝐴 → 𝐵 → 𝐷
𝐵 → 𝐶 → 𝐴 −1 𝐵 → 𝐶 𝐵 → 𝐷
𝐶 → 𝐴 𝐶 → 𝐴 → 𝐵 −1 𝐶 → 𝐴 → 𝐵 → 𝐷
𝐷 → 𝐶 → 𝐴 𝐷 → 𝐶 → 𝐵 𝐷 → 𝐶 −1
第 14 页
第 4 章 动态规划法 4.5 最长公共子序列
4.5 最长公共子序列
若给定序列 𝑋 = (𝑥
1
, 𝑥
2
, ..., 𝑥
𝑚
) 和 𝑌 = (𝑦
1
, 𝑦
2
, ..., 𝑦
𝑛
)，则另一序列 𝑍 = (𝑧
1
, 𝑧
2
, ..., 𝑧
𝑘
) 为 X 和 Y 的最长公共子
序列是指存在一个严格递增下标序列 (𝑖
1
, 𝑖
2
, ..., 𝑖
𝑘
) 和 ( 𝑗
1
, 𝑗
2
, ..., 𝑗
𝑘
) 使得对于所有 𝑡 = 1, ..., 𝑘 有 𝑧
𝑡
= 𝑥
𝑖
𝑡
= 𝑦
𝑗
𝑡
。
最长公共子序列的递推公式为：
𝑐[𝑖][ 𝑗] =
0, 若𝑖 = 0 或 𝑗 = 0
𝑐[𝑖 − 1][ 𝑗 − 1] + 1, 若𝑥
𝑖
= 𝑦
𝑗
max{𝑐[𝑖 − 1] [ 𝑗], 𝑐[𝑖] [ 𝑗 − 1]}, 若𝑥
𝑖
≠ 𝑦
𝑗
𝑠[𝑖][ 𝑗] =
1, 若𝑥
𝑖
= 𝑦
𝑗
2, 若𝑥
𝑖
≠ 𝑦
𝑗
且𝑐[𝑖 − 1] [ 𝑗 ] ≥ 𝑐[𝑖] [ 𝑗 − 1]
3, 若𝑥
𝑖
≠ 𝑦
𝑗
且𝑐[𝑖 − 1] [ 𝑗 ] < 𝑐[𝑖] [ 𝑗 − 1]
例题 4.3.
给定序列 𝑋 = (𝐴, 𝐵, 𝐶, 𝐷, 𝐸) 和 𝑌 = ( 𝐴, 𝐶, 𝐸, 𝐻)，求它们的最长公共子序列。
计算 𝑐[𝑖] [ 𝑗 ] 和 𝑠[𝑖][ 𝑗]：
𝑐[𝑖][ 𝑗] =
0 0 0 0 0
0 1 1 1 1
0 1 1 1 1
0 1 2 2 2
0 1 2 2 2
0 1 2 3 3
𝑠[𝑖][ 𝑗] =
0 0 0 0 0
0 ↖ 1 3 3 3
0 2 ↑ 2 2 2
0 2 ↖ 1 3 3
0 2 2 ↑ 2 2
0 2 2 ↖ 1 ← 3
最长公共子序列为 ( 𝐴, 𝐶, 𝐸)，长度为 3。
4.6 0-1 背包问题
已知一个载重为 𝑀 的背包和 𝑛 件物品，物品编号 0 ∼ 𝑛 − 1。第 𝑖 件物品的重量为 𝑤
𝑖
，如果将第 𝑖 件物品装入
背包将获利 𝑝
𝑖
（0 ≤ 𝑖 ≤ 𝑛 − 1, 𝑤
𝑖
> 0, 𝑝
𝑖
> 0）。在物品不能分割的情况下，求一种最佳装载方案使得总收益最大。
0-1 背包问题的递推公式为：
𝑓 (−1, 𝑋) =
∞, 𝑋 < 0
0, 𝑋 ≥ 0
𝑓 (𝑖, 𝑋) =
𝑓 (𝑖 − 1, 𝑋), 𝑋 < 𝑤
𝑖
max{ 𝑓 (𝑖 − 1, 𝑋), 𝑓 (𝑖 − 1, 𝑋 − 𝑤
𝑖
) + 𝑝
𝑖
}, 𝑋 ≥ 𝑤
𝑖
其中 𝑓 (𝑖, 𝑋) 表示在前 𝑖 件物品中选择若干件装入背包，且物品重量为 𝑋 时的最大收益。
若第一次放入重量为 𝑤
𝑖
、收益为 𝑝
𝑖
的物品，则剩余重量为 𝑋 − 𝑤
𝑖
，此时最大收益为 𝑓 (𝑖 − 1, 𝑋 − 𝑤
𝑖
) + 𝑝
𝑖
；
若不放入该物品，则最大收益为 𝑓 (𝑖 − 1, 𝑋)。
第 15 页
第 4 章 动态规划法 4.6 0-1 背包问题
𝑤
𝑖
𝑀
∞
−∞
𝑝
𝑖
𝑥
𝑓 (𝑋)
函数 𝑓 是梯形非递减曲线，可用阶跃点 (𝑤
𝑖
, 0) 和 (𝑀, 𝑝
𝑖
) 表示。
现用 𝑆
𝑗
表示函数 𝑓 ( 𝑗, 𝑋) 的全部阶跃点的集合，𝑆
𝑗
1
表示函数 𝑓 ( 𝑗 − 1, 𝑋 − 𝑤
𝑗
) + 𝑝
𝑗
的全部阶跃点的集合。
计算所有阶跃点的步骤如下：
1. 𝑆
−1
= (0, 0)，函数 𝑓 (−1, 𝑋) 的阶跃点为 (0, 0)。
2. 𝑆
𝑗
1
= {(𝑋, 𝑃)|(𝑋 − 𝑤
𝑗
, 𝑃 − 𝑝
𝑗
) ∈ 𝑆
𝑗−1
}，由集合 𝑆
𝑗−1
的阶跃点 (𝑋, 𝑃) 得到集合 𝑆
𝑗
1
的阶跃点 (𝑋 + 𝑤
𝑗
, 𝑃 + 𝑝
𝑗
)。
3. 𝑆
𝑗
= 𝑆
𝑗−1
∪ 𝑆
𝑗
1
，并舍弃所有 (𝑋 > 𝑋𝑖, 𝑃 < 𝑃𝑖) 的阶跃点与 𝑋 > 𝑀 的阶跃点。
最优解 (𝑥
0
, 𝑥
1
, . . . , 𝑥
𝑛−1
) 的构造方法：
1. 从最优解值 (𝑀, 𝑃) 开始， 𝑗 的初始值为 𝑛 − 1，判断 (𝑀, 𝑃) 是 𝑆
𝑗
1
中的阶跃点还是 𝑆
𝑗−1
中的阶跃点。
2. 若 (𝑀, 𝑃) 是 𝑆
𝑗
1
中的阶跃点，则说明第 𝑗 件物品被选中，𝑥
𝑗
= 1，将 𝑗 减 1，并将 (𝑀, 𝑃) 更新为 (𝑀 −𝑤
𝑗
, 𝑃− 𝑝
𝑗
)。
3. 若 (𝑀, 𝑃) 是 𝑆
𝑗−1
中的阶跃点，则说明第 𝑗 件物品未被选中，𝑥
𝑗
= 0，直接将 𝑗 减 1。
4. 重复上述步骤，直到 𝑗 = −1。
例题 4.4.
给定背包容量 𝑀 = 5，物品重量和收益分别为 (𝑤
0
, 𝑝
0
) = (2, 3)，(𝑤
1
, 𝑝
1
) = (3, 4)，(𝑤
2
, 𝑝
2
) = (4, 5)，求最
大收益。
计算 𝑓 (𝑖, 𝑋) 的阶跃点：
𝑆
−1
= {(0, 0)} 𝑆
0
1
= {(2, 3)}
𝑆
0
= {(0, 0), (2, 3)} 𝑆
1
1
= {(3, 4), (5, 7)}
𝑆
1
= {(0, 0), (2, 3), (3, 4), (5, 7)} 𝑆
2
1
= {(4, 5), (6, 8), (7, 9), (9, 12)}
𝑆
2
= {(0, 0), (2, 3), (3, 4), (4, 5), (5, 7)}
最大收益为 7，对应的物品为 (𝑤
0
, 𝑝
0
) 和 (𝑤
1
, 𝑝
1
)。
第 16 页
第 5 章 回溯法
第 5 章 回溯法
5.1 一般方法
回溯法（Backtracking）是一种系统地搜索所有可能的解的算法设计方法。通过搜索状态空间树来求问题的
可行解（满足约束条件）或最优解（使目标函数取最大或最小值）。使用约束函数和限界函数来压缩需要实际生
成的状态空间树的结点数。
回溯法的求解要素
显示约束：规定每个 𝑥
𝑖
取值的约束条件。
隐式约束：给出了判定一个候选解是否为可行解的条件。为满足问题的解而对不同分量之间施加的
约束。
目标函数（代价函数）：衡量每个可行解的优劣，使目标函数取最大（或最小）值的可行解为问题的
最优解。
回溯法使用使用剪枝函数（约束函数），深度优先生成状态空间树中结点。
蒙特卡罗方法
1. 在状态空间树中, 从根开始随机选择一条路径 (𝑥
0
, 𝑥
1
, ..., 𝑥
𝑛−1
)。
2. 假定搜索树中这条随机选出的路径上，代表部分向量 (𝑥
0
, 𝑥
1
, ..., 𝑥
𝑛−1
) 的结点 𝑋 处不受限制的孩子数
目, 和其他路径上与 𝑋 同层的的结点不受限制的孩子数目一样，都是 𝑚
𝑘
3. 可以估计整个状态空间树上实际生成的结点数为: 𝑚 = 1 + 𝑚
0
+ 𝑚
0
𝑚
1
+ 𝑚
0
𝑚
1
𝑚
2
+ ... + 𝑚
0
𝑚
1
...𝑚
𝑛−1
,
其中 𝑚
𝑖
为第 𝑖 层结点的孩子数目。
5.2 n-皇后问题
n-皇后问题是一个经典的回溯法问题，要求在一个 𝑛 × 𝑛 的棋盘上放置 𝑛 个皇后，使得它们互不攻击。即任
意两个皇后不能在同一行、同一列或同一对角线上。
设解向量：(𝑥
0
, 𝑥
1
, ..., 𝑥
𝑛−1
), 其中 xi 表示第 i 行的皇后所处的列号。
第 17 页
第 5 章 回溯法 5.3 子集和数
第一种约束
显式约束：𝑥
𝑖
= 0, 1, ..., 𝑛 − 1
隐式约束：
𝑥
𝑖
≠ 𝑥
𝑗
（不同列）
|𝑥
𝑖
− 𝑥
𝑗
| ≠ |𝑖 − 𝑗 |（不同对角线）
解空间大小：𝑛
𝑛
第二种约束
显式约束：
𝑥
𝑖
= 0, 1, ..., 𝑛 − 1
𝑥
𝑖
≠ 𝑥
𝑗
（不同列）
隐式约束：|𝑥
𝑖
− 𝑥
𝑗
| ≠ |𝑖 − 𝑗 |（不同对角线）
解空间大小：𝑛!
5.3 子集和数
已知 𝑛 个不同正数 𝑤
𝑖
的集合，求该集合的所有满足条件的子集，使每个子集中正数的和等于一个给定的正
数 𝑀。
子集和数的求解步骤：
1. 将所有正数 𝑤
𝑖
按非递减次序排列。
2. 设解向量为 (𝑥
0
, 𝑥
1
, ..., 𝑥
𝑛−1
)，其中 𝑥
𝑖
= 1 表示将第 𝑖 个正数 𝑤
𝑖
放入子集中，𝑥
𝑖
= 0 表示不放入。
3. 约数函数：
𝑘−1
𝑖=0
𝑤
𝑖
𝑥
𝑖
+
𝑛−1
𝑖=𝑘
𝑤
𝑖
≥ 𝑀
𝑘−1
𝑖=0
𝑤
𝑖
𝑥
𝑖
+ 𝑤
𝑘
≤ 𝑀
5.3.1 子集和数算法
前置条件：𝑤
𝑖
≤ 𝑤
𝑖+1
，𝑠 =
𝑘−1
𝑖=0
𝑤
𝑖
𝑥
𝑖
，𝑟 =
𝑛−1
𝑖=𝑘
𝑤
𝑖
，𝑠 + 𝑟 ≥ 𝑀，𝑠 + 𝑤
𝑘
≤ 𝑀。
后置条件：在以 (𝑥
0
, 𝑥
1
, ..., 𝑥
𝑛−1
) 为根的子树上搜索答案状态。
初始条件：𝑘 = 0, 𝑠 = 0, 𝑟 =
𝑛−1
𝑖=0
𝑤
𝑖
。
第 18 页
第 5 章 回溯法 5.3 子集和数
例题 5.1.
设 5 个正数的集合 𝑊 = (1, 2, 3, 5, 7) 和整数 𝑀 = 10，求满足条件的子集和数。
可行解 (1, 1, 0, 0, 1), (0, 1, 1, 1, 0), (0, 0, 1, 0, 1)。
即子集 {1, 2, 7}, {2, 3, 5}, {3, 7}。
第 19 页
第 6 章 分支限界法
第 6 章 分支限界法
6.1 一般方法
分支限界法（Branch and Bound）是一种用于求解组合优化问题的算法设计方法。通过广度优先产生状态空
间树的结点，并使用剪枝函数（限界函数）来减少需要实际生成的结点数。
队列式 (FIFO) 分枝限界法：
将活结点表组织成一个队列，按先进先出原则选取下一个结点为当前扩展结点。
堆栈式 (LIFO) 分枝限界法：
将活结点表组织成一个堆栈，按后进先出原则选取下一个结点为当前扩展结点。
优先队列式 (LC) 分枝限界法：
将活结点表组织成一个优先队列，并按优先级选取优先级最高的下一个结点为当前扩展结点。
分支限界法的求解要素
代价函数 𝑐(·)：从根结点到 𝑋 的搜索代价。
若 𝑋 是答案结点，则 𝑐(𝑋) 是从根结点到 𝑋 的搜索代价；
若 𝑋 不是答案结点且子树 𝑋 上不含任何答案结点，则 𝑐(𝑋) = ∞；
若 𝑋 不是答案结点但子树 𝑋 上包含答案结点，则 𝑐(𝑋) 等于子树 𝑋 上具有最小搜索代价的答案结点
的代价。
相对代价函数 𝑔(·)：衡量一个结点 𝑋 的相对代价。
衡量标准一：生成答案结点前，子树 𝑋 上需要生成的结点数目；
衡量标准二：子树 𝑋 上离 𝑋 最近的答案结点到 𝑋 的路径长度。
相对代价估计函数 ˆ𝑔(·)：
ˆ𝑔(𝑋) 是 𝐺 (𝑋) 的估计值，由 𝑋 到达一个答案结点所需代价的估计函数。一般的，若 𝑌 是 𝑋 的孩子，
则 ˆ𝑔(𝑌 ) = ˆ𝑔(𝑋) + 𝑐(𝑋, 𝑌)。
代价估计函数 ˆ𝑐(·)：
ˆ𝑐(𝑋) 由两个部分组成：从根到 𝑋 的代价 𝑓 ( 𝑋) 和从 𝑋 到答案结点的估计代价 ˆ𝑔(𝑋)，即： ˆ𝑐(𝑋) =
𝑓 (𝑋) + ˆ𝑔(𝑋)。一般可以令 𝑓 ( 𝑋) 为 𝑋 在树中的层次。
第 20 页
第 6 章 分支限界法 6.2 迷问题
6.2 迷问题
在一个 𝑚 × 𝑛 的方形棋盘上放置了 𝑚 × 𝑛 − 1 块编了号的牌，还剩下
一个空格。号牌的一次合法移动是指将位于空格四周（上、下、左、
右）的一块号牌移入空格位置的四种移动方式。对于任意给定的一
种初始排列，通过一系列的合法移动，将给定的初始排列转换成如
右图所示的目标排列：
1 2 3 4
5 6 7 8
9 10 11 12
13 14 15
定理 6.2.1
♡
对给定的初始状态，当且仅当
16
𝑘=1
𝐿𝑒𝑠𝑠(𝑘) + 𝑖 + 𝑗 为偶数时，可以由此初始状态到达目标状态。其中
𝐿𝑒𝑠𝑠(𝑖) 表示在初始状态中，编号小于 𝑖 的牌在号牌 𝑖 后边的牌的数目，𝑖 和 𝑗 分别表示空格所在行和列的
编号。
6.2.1 LC 分枝限界法求解
定义代价估计函数 ˆ𝑐(𝑋) = 𝑓 (𝑋) + ˆ𝑔(𝑋)，其中 𝑓 (𝑋) 是从根到结点 𝑋 的路径长度， ˆ𝑔(𝑋) 是不在其位的非空
白牌数目。LC 检索是选取具有最小 ˆ𝑐(𝑋) 值的结点成为下一个 E-结点。
例题 6.1.
棋盘初始状态如下图所示，使用 LC 分枝限界法画出状态空间树。
1 2 3 4
5 6 7 8
9 10 12
13 14 11 15
2 1 3 4
5 6 7 8
9 10 12
13 14 11 15
初始状态
2 1 3 4
5 6 8
9 10 7 12
13 14 11 15
ˆ𝑐 = 1 + 3 = 4
上
2 1 3 4
5 6 7 8
9 10 11 12
13 14 15
ˆ𝑐 = 1 + 1 = 2
下
2 1 3 4
5 6 7 8
9 10 12
13 14 11 15
ˆ𝑐 = 1 + 3 = 4
左
2 1 3 4
5 6 7 8
9 10 12
13 14 11 15
ˆ𝑐 = 1 + 3 = 4
右
2 1 3 4
5 6 7 8
9 10 11 12
13 14 15
ˆ𝑐 = 2 + 2 = 4
左
2 1 3 4
5 6 7 8
9 10 11 12
13 14 15
目标
右
第 21 页
第 6 章 分支限界法 6.3 分支限界法最优解
6.3 分支限界法最优解
定义 6.3.1
♣
函数 𝑢(·) 和 ˆ𝑐( 𝑋) 分别是代价函数 𝑐(·) 的上界和下界函数。对所有结点 𝑋，总有 ˆ𝑐(𝑋) ≤ 𝑐(𝑋) ≤ 𝑢(𝑋)。
若目标函数取最小值时为最优解，则设定一个上界变量 𝑈，记录最小代价的上界值。对任意结点 𝑋，若
ˆ𝑐(𝑋) > 𝑈，则 𝑋 子树可以剪枝。以 ˆ𝑐(𝑋) ≥ 𝑈 作为剪枝条件，为了不误剪包含最小答案结点子树，对所有节点 𝑋，
使用 𝑈 = 𝑢(𝑋) + 𝜀 作为该子树的最小代价上界值，𝜀 是一个极小量。在搜索状态空间树的过程中不断修正 𝑈 的
值。
对于某个结点 𝑋，𝑈 的值可以通过以下方式修正：
1. 若 𝑋 是答案结点，𝑐𝑜𝑠𝑡(𝑋) 是 𝑋 所代表的可行解的目标函数，则 𝑈 = min{𝑐𝑜𝑠𝑡 (𝑋), 𝑈};
2. 若 𝑋 代表部分向量，𝑢(𝑋) 是该子树上最小代价答案结点代价的上界值，则 𝑈 = min{𝑢( 𝑋) + 𝜀, 𝑈};
6.4 带时限的作业排序
设有 𝑛 个作业和一台处理机，每个作业 𝑖 处理所需时间为 𝑡
𝑖
，如果能够在时限 𝑑
𝑖
内完成将可收益 𝑝
𝑖
。将每
个作业所需的处理时间、要求时限和收益用三元组 (𝑡
𝑖
, 𝑑
𝑖
, 𝑝
𝑖
)，0 ≤ 𝑖 < 𝑛 表示。求使得总收益最大的作业子集 𝐽。
用可变大小元组 (𝑥
0
, 𝑥
1
, . . . , 𝑥
𝑘
) 表示解，其中 𝑥
𝑖
为作业编号。
显示约束：𝑥
𝑖
∈ {0, 1, . . . , 𝑛 − 1} 且 𝑥
𝑖
< 𝑥
𝑖+1
，即作业编号严格递增。
隐式约束：对入选子集 𝐽 的作业 (𝑥
0
, 𝑥
1
, . . . , 𝑥
𝑘
) 存在一种作业排列，使得 𝐽 中作业均能如期完成。
目标函数：未入选子集 𝐽 的作业所导致的损失
𝑛−1
𝑖=0
𝑝
𝑖
−
𝑖∈ 𝐽
𝑝
𝑖
=
𝑖𝑛 ∉𝐽,𝑖=0,1,...,𝑛−1
𝑝
𝑖
下界函数
ˆ
𝐶(𝑋)：迄今为止作业子集 𝐽 = (0, 1, . . . , 𝑥
𝑘
) 中，未能入选 𝐽 的作业所造成的损失。
ˆ𝑐(𝑋) =
𝑖𝑛 ∉𝐽,𝑖<𝑥
𝑘
𝑝
𝑖
上界函数 𝑢( 𝑋)：由两个部分组成。一是迄今为止作业子集 𝐽 = (𝑥
0
, 𝑥
1
, . . . , 𝑥
𝑘
) 中未入选的作业所造成的损
失，也即 ˆ𝑐(𝑋)；二是假定作业 𝑥
𝑘
后所有的作业都未入选，所造成的损失。
𝑢(𝑋) =
𝑖∉𝐽 ,𝑖=0,1,...,𝑛−1
𝑝
𝑖
=
𝑖∉𝐽 ,𝑖< 𝑥
𝑘
𝑝
𝑖
+
𝑖=𝑥
𝑘
+1,...,𝑛−1
𝑝
𝑖
求解步骤：
1. 从根节点开始，初始化 𝑈 =
𝑛−1
𝑖=0
𝑝
𝑖
。将根结点入队，
2. 当队列不为空时，重复以下步骤：
(a). 从队列中取出一个结点 𝑋，作为当前扩展结点。
(b). 检查下一个孩子结点 𝑥 的作业完成时间是否小于等于其时限 𝑑
𝑥
。
(c). 计算其 𝑐(𝑥) 和 𝑢(𝑥) 值，若 𝑐(𝑥) ≥ 𝑈，则剪枝。
(d). 若不剪枝，则生成 𝑥 并入队。
(e). 若 𝑢(𝑥) < 𝑈，则修正 𝑈 = 𝑢(𝑥)。
3. 当队列为空时，𝑈 的值即为最优解。
第 22 页
第 6 章 分支限界法 6.4 带时限的作业排序
例题 6.2.
设有四个作业，处理时间、时限和收益分别为 (1, 1, 3)、(2, 3, 5)、(3, 5, 7) 和 (4, 7, 9)。使用 FIFO/LC 分支
限界法求使得总收益最大的作业子集。
将作业按照时限非递减顺序排列：
作业编号 处理时间 𝑡
𝑖
时限 𝑑
𝑖
收益 𝑝
𝑖
0 1 1 3
1 2 3 5
2 3 5 7
3 4 7 9
FIFO 分支限界法：
1
ˆ𝑐 = 0
𝑢 = 24
2
ˆ𝑐 = 0
𝑢 = 21
𝑥
0
= 0
3
ˆ𝑐 = 3
𝑢 = 19
𝑥
0
= 1
4
ˆ𝑐 = 8
𝑢 = 17
𝑥
0
= 2
5
ˆ𝑐 = 15
𝑢 = 15
𝑥
0
= 3
6
ˆ𝑐 = 0
𝑢 = 16
𝑥
1
= 1
7
ˆ𝑐 = 5
𝑢 = 14
𝑥
1
= 2
8
ˆ𝑐 = 12
𝑢 = 12
𝑥
1
= 3
9
ˆ𝑐 = 3
𝑢 = 14
𝑥
1
= 2
10
ˆ𝑐 = 10
𝑢 = 10
𝑥
1
= 3
11
ˆ𝑐 = 8
𝑢 = 8
𝑥
1
= 3
12
𝑥
2
= 2
13
ˆ𝑐 = 7
𝑢 = 7
𝑥
2
= 3
14
𝑥
2
= 3
15
𝑥
2
= 3
LC 分枝限界法（ ˆ𝑐(𝑋) 作为结点 𝑋 的优先权）：
1
ˆ𝑐 = 0
𝑢 = 24
2
ˆ𝑐 = 0
𝑢 = 21
𝑥
0
= 0
3
ˆ𝑐 = 3
𝑢 = 19
𝑥
0
= 1
4
ˆ𝑐 = 8
𝑢 = 17
𝑥
0
= 2
5
ˆ𝑐 = 15
𝑢 = 15
𝑥
0
= 3
6
ˆ𝑐 = 0
𝑢 = 16
𝑥
1
= 1
7
ˆ𝑐 = 5
𝑢 = 14
𝑥
1
= 2
8
ˆ𝑐 = 12
𝑢 = 12
𝑥
1
= 3
11
ˆ𝑐 = 3
𝑢 = 14
𝑥
1
= 2
12
ˆ𝑐 = 10
𝑢 = 10
𝑥
1
= 3
15
ˆ𝑐 = 8
𝑢 = 8
𝑥
1
= 3
9
𝑥
2
= 2
10
ˆ𝑐 = 7
𝑢 = 7
𝑥
2
= 3
14
𝑥
2
= 3
13
𝑥
2
= 3
注释：方框为被剪枝的结点，红色是不满足时限，橙色是满足时限但 ˆ𝑐(𝑋) ≥ 𝑈 的结点。
第 23 页