前言#

本章将系统复习《算法导论》中的一些经典问题，主要包含如下内容：

• 动态规划——最优二叉搜索树
• 基本图论——BFS，DFS
• 单源最短路——Bellman-Ford 算法, Dijkstra 算法
• 最大流——Ford-Fulkerson 方法，Edmonds-Karp 算法
• 散列表——开放定址法（双散列）
• 贪心算法——哈夫曼编码
• 堆排序
• 线性时间排序

本篇主要以例题为主，不会过多介绍基础知识及其推导过程。如果对某个分类感兴趣的话，欢迎阅读其他子分篇。

点我前往归档页面：https://hoyue.fun/categories/学习笔记/算法设计与分析

PS：这里不包括分治法及其之前的内容，具体请见各自章节。

动态规划——最优二叉搜索树#

本部分对应分篇：【算法设计与分析】动态编程

普通的二叉搜索树 (BST) 的查询效率取决于树的高度。但在现实中，我们查找每个关键字 (Key) 的频率是不一样的。比如在一个字典里，查找 “the” 的频率远高于 “xylophone”。

我们希望查找频率高的节点离根节点更近，从而使 期望搜索代价 (Expected Search Cost) 最小化。

如果一棵树是最优的，那么它的左子树和右子树也必须是关于它们各自包含的关键字的最优二叉搜索树。

对于节点来说，我们有：

• 关键字 (非叶子节点) $K = \langle k_1, \dots, k_n \rangle$：有序的实际数据。对应概率 $p_i$。
• 伪关键字 (叶子节点) $D = \langle d_0, \dots, d_n \rangle$：代表落在关键字之间的区间（搜索失败的情况）。对应概率 $q_i$。

给定一个包含 n 个不同的键的集合 $K = \{k_1,k_2,\dots,k_n\}$ 以及这些键对应的 成功查找概率 $p_1,p_2, \dots, p_n$ 和 失败查找概率 $q_1,q_2, \dots, q_n$。我们要构造一个 二叉搜索树 (BST)，使得树的 加权查找成本最小。

• e table: e[i, j] 为在包含键 $k_i, \ldots, k_j$ 的最优二叉搜索树中进行一次关键字搜索的 期望代价 。
• w table: w[i, j] 为包含关键字 $k_i, \ldots, k_j$ 的子树的 总概率（即子树中 所有键的概率之和 (包含 $p$ 和 $q$)）。
• root table: root[i, j] 表示构成子树 $k_i, \ldots, k_j$ 的 根节点。

动态规划的状态转移过程如下：

1. 建议先对 $p$ 值表和 $q$ 值表 计算其概率和 $p_i+q_i$ 以便后续使用。

2. 初始化时，首先处理只有伪关键字的情况（空树）。对 $i = 1 \dots n+1$：

   • $e[i, i-1] = q_{i-1}$
   • $w[i, i-1] = q_{i-1}$

3. 迭代填表：我们要计算长度 $l = 1, 2, \dots, n$ 的所有情况。有两层循环来迭代：

   1. 外层循环：$l$ (链长) 从 1 到 $n$。
   2. 内层循环：$i$ (起始点) 从 1 到 $n-l+1$。
   3. 计算 $j$：$j = i + l - 1$ (终点)。

   对于每一个单元格 $(i, j)$，我们做以下操作：

   1. 计算 $w[i, j]$：利用公式 $w[i, j] = w[i, j-1] + p_j + q_j$ (利用已有的 $p_i+q_i$ 值，不用每次累加)。
   2. 根据 $w$ 表寻找最佳根 $r$：遍历 $r$ 从 $i$ 到 $j$，
      1. 计算临时代价 $t = e[i, r-1] + e[r+1, j] + w[i, j]$。
      2. 找到最小的 $t$，存入 $e[i, j]$。
      3. 记录对应的 $r$ 存入 $root[i, j]$。

下面是一个例子：

概率表：

我们先从 $w$ 表开始，它的公式为：

填表有如下规律：

• 首先先填对角线，填入 $q_i$ 的所有内容。
• 然后再填已填写位置右侧的一格（例如已填写 w[1,0], 那么接下来就填 w[1,1]），它的内容根据公式等于 左侧单元格内容 + 当前列号(j)对应的 $p_j$ 和 $q_j$ 的概率和 。
• 这是一个斜向右填表的过程，如果已经到达右边的边上，则不用填。每次要填写的数据都少一个（即第一次填6个，第二次就填5个，因为最后那个已经到达边上）。

注意检查右上角的值一定为1！

接下来是 $e$ 表和 $root$ 表，$e$ 表的公式为：

填表有如下规律：先填主对角线 ($l=1$)，再填上面一条 ($l=2$)，最后右上角的 $e[1, n]$ 就是我们最终的最小期望代价。

• 首先也是对角线的值为 $q_i$ ；
• 之后的值中， r 的取值有 j-i 种，需要每个讨论 j-i 次，取其讨论的最小值。
• 每次讨论等价于对位相加。例如第 1 次讨论则是 $e$ 表中这一行的第 1 个数 + $e$ 表中这一列的第 1 个数 + $w$ 表中该位置的值。即 对于 e[i,j] 的第 $k(k∈[i,j])$ 次讨论，为该行（第i行）的第k个数 + 该列（第j列）的第k个数 $+ w[i,j]$ 。
• 对于讨论中相同的值，选择讨论次数 k 最小的，因为替换最小值时比较为 < 而不是 ≤。
• 这个过程也是斜向右填表，越往后的讨论次数越多。

例如，对于第 $(1,3)$ 位置上的 $e$ 值，算出它的所有讨论：

• $r = 1: e(1,0) + e(2,3) + w(1,3) = 0.06 + 0.68 + 0.42 = 1.16$
• $r = 2: e(1,1) + e(3,3) + w(1,3) = 0.28 + 0.32 + 0.42 = 1.02$
• $r = 3: e(1,2) + e(4,3) + w(1,3) = 0.62 + 0.06 + 0.42 = 1.10$

选择最小的 $1.02$ 作为 $e[1,3]$。我们需要记住这个选项选的是 $r = 2$ 的情况，它将成为该位置的 $root$ 值。

对于root表，它的行和列均为 $1 \dots n$，也是从对角线开始填。右上角为整个树的根。

我们在计算 $e$ 值表的时候，就需要记录对应的 $r$ 存入 $root[i, j]$。例如之前的例子中 $r = 2 \implies root[1,3] = 2$。

root表：

我们已经画出了 $root$ 表，接下来我们利用 $root$ 表进行递归构建得到最优二叉搜索树。

我们要知道：$root[i, j]$ 告诉我们在范围 $k_i \dots k_j$ 中，谁是 老大（根）。

构建的过程：

1. 找主根 (Main Root)：对于一个计算好的 $root$ 表，范围是 $1 \dots n$。例如我们这题的例子中范围是 $1 \dots 7$，那么主根就是 $root[1,7] = k_5$
2. 构建左子树：我们已经找到了主根为 $k_r=k_5$，那么它的左子树的范围是 $k_1 \dots k_{r-1}$ 即 $k_1 \dots k_4$。我们开始查找这个范围的根为 $root[1, r-1] = root[1, 4] = k_2$，左子树的根为 $k_2$。
3. 构建右子树：同理，它右子树的范围是 $k_{r+1} \dots k_n$ 即 $k_6 \dots k_7$。我们开始查找这个范围的根为 $root[r+1, n] = root[6, 7] = k_7$，右子树的根为 $k_7$。
4. 递归深入：我们对构建好的左右子树再递归应用上述的 (2) 和 (3)，直到该根没有子节点为止。例如，$k_2$ 的左子树查找 $root[1,1] = k_1$，但对于 $k_1$ 而言，当前的 $r_1 - 1 = 1 - 1 = 0$ 已经不存在了，就终止了。对于右子树同理，如果查到的范围是 $root[i, i-1]$ 时终止。
5. 处理伪关键字：在构建完根节点后，开始 从左向右 为那些根节点挂上叶子节点，并从 $0$ 开始顺序编号。

最后根据这个表，生成一个树如图：

基本图论#

本部分对应分篇：【算法设计与分析】基础图论算法

单源最短路#

本部分对应分篇：【算法设计与分析】单源最短路算法

这里简单复习一下所有的最短路径算法的问题模型：

对于图 $G=(V, E)$ 中的每个顶点 $v$，我们需要维护两个属性：

• $v.d$：从源点 $s$ 到顶点 $v$ 的 最短路径 估计 (shortest-path estimate)。初始化时，$s.d = 0$，其他所有 $v.d = \infty$。
• $v.\pi$：顶点 $v$ 在最短路径上的 前驱节点 (predecessor)。

最短路的问题是：一个带权有向图 $G=(V,E)$，边权函数 $w: E \to \mathbb{R}$，给定源点 $s\in V$，要找出对所有 $v\in V$ 的最短路径距离。

松弛操作 (relex) 是用来测试是否可以通过边 $(u, v)$ 找到一条到达 $v$ 的更短路径。如果是，这就叫做“松弛”了这条边，并更新 $v.d$ 和 $v.\pi$。

1
RELAX(u, v, w)
2
    if v.d > u.d + w(u, v)
3
        v.d = u.d + w(u, v)
4
        v.π = u

1
        u.d
2
    s ----→ u
3
            |
4
            | w(u,v)    u.d + w(u,v) < v.d ?
5
            ↓
6
    s - - → v
7
        v.d

最大流#

本部分对应分篇：【算法设计与分析】最大流

Edmonds-Karp 算法采用 BFS 的方式去寻找图中分配的最大流，它每次都会选择 最短的增广路径（边数最少的路径）。它的过程非常简单，可以描述为：

1. 画出残存网络（刚开始就是原图）。并令初始的流为 0。
2. BFS 扫描：找 $s$ 到 $t$ 边数最少的路。如果有两条路边数一样少，随便选一条（根据题目描述，通常选字典序小的，比如先走 $u$ 后走 $v$）。
3. 增广：找出瓶颈，更新流量，更新残存图（加反向边）。
4. 重复：再次 BFS。你会发现，随着残存图里正向边被切断，新的路径往往会通过反向边绕一下，或者走更远的边，路径长度逐渐增加。
5. 直到 $s$ 和 $t$ 不连通。

接下来是一个例子：

给出一个流网络，使用 Edmonds-Karp 算法找到其最小割和最大流。在考虑邻结点顺序时遵循：$\{s, v1, v2, v3, v4, t\}$.

对于这样的题目，我们首先将其转换为残存网络 $G_f$，如图 (b)。(图中阴影与本题无关)

忽略当前图中的流，从 0 开始。接下来开始进行 BFS，按照给出的邻结点顺序遍历。（注：下面过程中的图中，左侧图为当前步骤 执行前 的残存图 $G_f$，右侧图为当前步骤 执行后 的流网络图 $G$。）

(a). 第一次增广，先遍历 $v_1$，将选择：$s \to v_1 \to v_3 \to t$。它的瓶颈值 (minimum capacity) 是 $\min(16,12,20) = 12$，所以更新该增广路径的流为 12，并更新残存图 (显示在 (b) 中的左图)。

(b). 第二次增广，残存图中先经过 $v_1$ 的路径以及没有了，继续遍历 $v_2$，将选择：$s \to v_2 \to v_4 \to t$。它的瓶颈值是 $\min(13,14,4) = 4$，所以更新该增广路径的流为 4.

(c). 第三次增广，继续遍历 $v_2$，将选择：$s \to v_2 \to v_4 \to v_3 \to t$。它的瓶颈值是 $\min(13,14,7,20) = 7$，所以更新该增广路径的流为 7。此前已有流的边将增加 7 的值。

(d). 第四次增广，先经过 $v_2$ 到 $t$ 的路已经全部断开，继续尝试遍历其他结点。发现无法找到任何增广路径，此时算法结束，最后的残存图如下：

至此，Edmonds-Karp 算法的流程就结束了，当前 (d) 的结果就是最小割和最大流的情况。我们可以通过残存图构造这样的最小割：

• $S$: 包含所有 $s$ 能到达的结点，即 $S = \{s,v_1,v_2,v_4\}$.
• $T$: 包含所有 $s$ 无法到达的结点，即 $T = \{v_3, t\}$.

最大流的值为 $|f| = c(S,T) = c(v_1,v_3) + c(v_4,t) + c(v_4,v_3) = 12 + 4 + 7 = 23$

散列表——开放定址法（双散列）#

本部分对应分篇：【算法设计与分析】散列表

我们一般使用双散列比较多，下面是一个使用双散列的例子：

Consider inserting the keys 10, 22, 31, 4, 15, 28, 17, 88, 59 into a hash table of length m = 11 using open addressing.

Illustrate the result of inserting these keys using double hashing with h1(k) = k mod m and h2(k) = 1 + (k mod (m - 1)).

我们整合一下上面的两个函数，可以得到函数h(k,i)，k表示关键字， i从0开始 ，表示初始位置的基础上进行偏移的度：

h(k, i) = (h₁(k) + i*h₂(k)) mod m = (k mod m + i(1 + (k mod (m - 1)))) mod m

我们的操作如下：

1. 对于键值对10：h1(10) = 10 mod 11 = 1，插入键值对10到哈希表的第10个位置。
2. 接下来是键值对22：h1(22) = 22 mod 11 = 0，插入键值对22到哈希表的第0个位置。
3. 现在是键值对31：h1(31) = 31 mod 11 = 9，插入键值对31到哈希表的第9个位置。
4. 接下来是键值对4：h1(4) = 4 mod 11 = 4，插入键值对4到哈希表的第4个位置。
5. 现在是键值对15：h1(15) = 15 mod 11 = 4，4这个位置冲突了，继续计算h2(15) = 1 + (15 mod (11 - 1)) = 1 + 5 = 6，(4 + 6) mod 11= 10这个位置还是冲突，继续计算(4 + 2*6) mod 11 = 16 mod 11 = 5，插入键值对15到哈希表的第5个位置。
6. 接下来是键值对28：h1(28) = 28 mod 11 = 6，插入键值对28到哈希表的第6个位置。
7. 现在是键值对17：h1(17) = 17 mod 11 = 6，这个位置冲突了，计算h2(17) = 1 + (17 mod (11 - 1)) = 1 + 7 = 8，(6 + 8) mod 11 = 3，插入键值对17到哈希表的第3个位置。
8. 接下来是键值对88：h1(88) = 88 mod 11 = 0，位置冲突继续计算，h2(88) = 1 + (88 mod (11 - 1)) = 1 + 8 = 9，(0+9) mod 11 = 9冲突，继续计算(0+2*9) mod 11 = 7，插入键值对88到哈希表的第7个位置。
9. 最后是键值对59：h1(59) = 59 mod 11 = 4，位置冲突继续计算，h2(59) = 1 + (59 mod (11 - 1)) = 1 + 9 = 10，(4+10) mod 11 = 3冲突，(4+2*10) mod 11 = 2，插入键值对59到哈希表的第2个位置。

最后可以得到如下表格：

贪心算法——哈夫曼编码#

本部分对应分篇：【算法设计与分析】贪心算法

哈夫曼编码的贪心设计就非常明显了，只需要使用优先队列去存，每次都选择最小的两个合并，直到全部插入树中即可，例如：

以下字符频率基于斐波那契数列前8个数字的字符集的哈夫曼编码是怎样的? a:1 b:1 c:2 d:3 e:5 f:8 g:13 h:21

下面使用z(a,b)表示频数为z的节点左边的是频数a或字符a，右边的是频数b或字符b。

1. 把它们按照频数加入优先队列Q中，顺序刚好为： a:1 b:1 c:2 d:3 e:5 f:8 g:13 h:21
2. 取出前两个，合并插入到优先队列中得到： c:2 2(a,b) d:3 e:5 f:8 g:13 h:21
3. 依次类推继续合并插入得： d:3 4( c,2(a,b) ) e:5 f:8 g:13 h:21
4. e:5 7( d,4( c,2(a,b) ) ) f:8 g:13 h:21
5. f:8 12( e, 7( d,4( c,2(a,b) ) ) ) g:13 h:21
6. g:13 20( f,12( e, 7( d,4( c,2(a,b) ) ) ) ) h:21
7. h:21 33( g,20( f,12( e, 7( d,4( c,2(a,b) ) ) ) )
8. 54( h,33( g,20( f,12( e, 7( d,4( c,2(a,b) ) ) ) ) )

最终得到这样的一棵树，图(a)为该题答案，图(b)为前n为推广：

堆排序#

本部分对应分篇：【算法设计与分析】堆排序

这一节又分为分析和代码部分，其中比较重要的是如何维护堆和建堆。下面的证明可能与之前原文有所不同，选择好理解的就行。

1
MAX-HEAPIFY(A, i)
2
    l = LEFT(i)
3
    r = RIGHT(i)
4
    if l ≤ A.heap-size and A[l] > A[i]
5
        largest = l
6
    else largest = i
7
    if r ≤ A.heap-size and A[r] > A[largest]
8
        largest = r
9
    if largest ≠ i
10
        exchange A[i] with A[largest]
11
        MAX-HEAPIFY(A, largest)

1
        8
2
      /   \
3
     7     6
4
    / \   / \
5
   5   4 3   2
6
  /
7
 1

1
        8
2
      /   \
3
     7     6
4
    / \   / \
5
   5   4 3   2
6
  / \
7
 1   2

1
        8
2
      /   \
3
     7     6
4
    / \   / \
5
   5   4 3   2

1
BUILD-MAX-HEAP(A, n)
2
    A.heap-size = n
3
    for i = floor(n/2) down to 1
4
        MAX-HEAPIFY(A, i)

1
HEAPSORT(A, n)
2
    BUILD-MAX-HEAP(A, n)
3
    for i = n downto 2
4
        swap(A[1], A[i])
5
        A.heap-size = A.heap-size - 1
6
        MAX-HEAPIFY(A, 1)

1
MIN-HEAPIFY(A, i)
2
    l = LEFT(i)
3
    r = RIGHT(i)
4
    if l ≤ A.heap-size and A[l] < A[i]
5
        smallest = l
6
    else smallest = i
7
    if r ≤ A.heap-size and A[r] < A[smallest]
8
        smallest = r
9
    if smallest != i
10
        exchange A[i] with A[smallest]
11
        MIN-HEAPIFY(A, smallest)

1
MAX-HEAPIFY(A, i)
2
    while true
3
        l = LEFT(i)
4
        r = RIGHT(i)
5
        if l ≤ A.heap-size and A[l] > A[i]
6
            largest = l
7
        else largest = i
8
        if r ≤ A.heap-size and A[r] > A[largest]
9
            largest = r
10
        if largest == i
11
            return
12
        exchange A[i] with A[largest]
13
        i = largest

线性时间排序#

本篇原文：

https://hoyue.fun/algorithm_5.html

1
BUCKET-SORT(A, n)
2
    let B[0 : n - 1] be a new array
3
    for i = 0 to n - 1
4
        make B[i] an empty list
5
    for i = 1 to n
6
        insert A[i] into list B[⌊n · A[i]⌋]
7
    for i = 0 to n - 1
8
        sort list B[i] with insertion sort
9
    concatenate the lists B[0], B[1], ... , B[n - 1] together in order
10
    return the concatenated lists

1
COUNTING-SORT(A, n, k)
2
    let C[0:k] be new arrays
3
    for i = 0 to k
4
        C[i] = 0
5
    for j = 1 to n
6
        C[A[j]] = C[A[j]] + 1 // C[i] now contains the number of elements equal to i.
7
    p = 1
8
    for i = 0 to k
9
        while C[i] > 0
10
            A[p] = i
11
            p = p + 1
12
            C[i] = C[i] - 1

1
BUCKET-SORT(X, n)
2
    let B[0 : n - 1] be a new array
3
    for i = 0 to n - 1
4
        make B[i] an empty list
5
    for i = 1 to n
6
        if x_{i-1} ≤ X_i and X_i < x_i
7
        insert X_i into list B[i-1]
8
    for i = 0 to n - 1
9
        sort list B[i] with insertion sort
10
    concatenate the lists B[0], B[1], ... , B[n - 1] together in order
11
    return the concatenated lists

后记#

通过这次期末复习专题，我们系统回顾了算法设计与分析的核心内容，包括散列表的开放定址法、动态规划的最优二叉搜索树、贪心算法的哈夫曼编码、基本图论的 BFS 和 DFS、单源最短路的 Bellman-Ford 和 Dijkstra 算法、最大流中的 Edmonds-Karp 算法、堆排序以及线性时间排序算法。

这些算法各有特点和适用场景：

• 散列表 通过双散列等开放定址法有效解决冲突问题
• 动态规划 通过最优子结构和重叠子问题性质求解最优化问题
• 贪心算法 在每步做出局部最优选择，在特定问题上能得到全局最优解
• 图论算法 为后续复杂图算法奠定基础
• 最短路算法 分别适用于有负权边和无负权边的情况
• 堆排序 保证 $O(n \lg n)$ 的时间复杂度
• 线性时间排序 在特定条件下突破比较排序的下界

掌握这些基础算法的原理、实现和分析方法，对于解决实际问题和进一步学习高级算法具有重要意义。算法设计与分析不仅是计算机科学的核心课程，更是培养逻辑思维和问题求解能力的重要途径。