期末速通

算法：贪心法

每一步都做出当前的最优选择

每一步都做出当前的最优选择。

优化问题

最优化研究的就是将问题转化为 $\max$ 或 $\min$ 的方法。

一个优化问题可以描述如下：

  1. 问题的解为一个复杂的结构，例如元组形式 $(x_1, x_2, \cdots, x_n)$
  2. 约束条件：$B(x_1, \cdots, x_n)$，使得 $B(x_1, \cdots, x_n)$ 为真的元组称为可行解。
  3. 目标函数；$f(x_1, \cdots, x_n)$

优化解即指使目标函数极大化（或极小化）的可行解，对应的目标函数值称为优化值。

很多优化问题是NP难问题，迄今找不到它们的多项式算法。所以计算上可行的方法就是求其近似解。贪心法是求近似算法的主要途径。

贪心问题的数学形式化描述：$\max / \min f(x)$ 其中，$x$ 通过贪心策略逐步构建

基本概念

概念 内容
分步决策 贪心算法的每一步总是做出当前最好的选择
最优子结构 如果一个问题的最优解包含其子问题的最优解，那么这个问题就具有最优子结构的性质
贪心选择性质 每一步的局部最优选择必须能导向全局最优解，即通过当前最优决策逐步构建的解最终是全局最优的

通用的贪心伪代码框架如下：

 1
 2
 3
 4
 5
 6
 7
 8
 9
10

def greedy(problem):
    # 初始化
    solution = []
    # 遍历所有可选项，通常需要按照某种规则排序
    for item in sorted(problem.items, key = rule):
        # 贪心选择：如果当前选择满足条件则采纳它
        if isFeasible(solution, item):
            solution.append(item)
    # 返回最终构造的解
    return solution

贪心选择性质关注局部决策的全局有效性，最优子结构关注问题分解的递归性。两者相互独立，需同时满足才能保证贪心算法的正确性。

贪心算法的特点

贪心法是一种通过局部最优选择逐步逼近全局最优解的算法：

  1. 不回溯：选定一个分量后，不重试其他可能。
  2. 局部最优：减小计算开销。
  3. 高效性：通常时间复杂度低。
  4. 实现简单：逻辑清晰易懂。
  5. 贪心算法并不总能求出问题的整体最优解。

存在具有最优子结构，但是不满足贪心选择性的问题。

贪心法与动态规划的比较：

条件 贪心算法 动态规划算法
最优子结构 必须满足 必须满足
贪心选择性质 必须满足 不需要
重叠子问题 不需要 必须满足

贪心算法的验证

在实际解决问题的过程中，判断贪心算法是否适用的步骤如下：

  • 先验证最优子结构
    • 假设原问题的最优解为 $S = \{A_1, A_2, \cdots, A_n\}$，其中 $A_1$ 是结束时间最早的活动。
    • 分解子问题：在 $A_1$ 结束之后，剩余时间内选择最大相容活动子集 $S'$
    • 反证：若子问题的最优解不是 $S'$，则存在更大的相容活动集合 $S''$，使得 $|S''| > |S'|$；此时，原问题的解可重构为 $\{A_1\} \cup S''$，其总活动数为 $1+|S''|>|S|$，与原解 $S$ 的最优性矛盾。
    • 此时子问题的解 $S'$ 必须是最优的，否则原解 $S$ 不可能是最优的。
  • 再验证贪心选择性

案例

最短处理时间

已知 $n$ 个任务的执行序列。假设任务 $i$ 需要 $t_i$ 个时间单位。如果任务完成的顺序为 $1, 2, \ldots, n$，则任务 $i$ 的完成时间为：$\displaystyle c_i = \sum_{j=1}^{i} t_j$。

任务的平均完成时间（ACT）：

$$\text{ACT} = \frac{1}{n}\sum_{i=1}^{n} c_i$$

现要求生成一个任务序列使得 $\text{ACT}$ 最小。

贪心的生成方法是：分 $n$ 步生成一个任务序列，每一步从剩下的任务里选择花费时间最少的任务。

伪代码如下：

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16

int t[N];
// 将 t[1..n] 按非递减顺序排序（从小到大）
// 排序后的序列即为最优执行序列

// 计算 ACT
int act(int t[]) {
    int total_completion = 0;
    int current_sum = 0;
    for i = 1 to n {
        // 每个任务完成的总时间为它的前缀和
        current_sum = current_sum + t[i];
        total_completion = total_completion + current_sum;
    }
    ACT = total_completion / n;
    return ACT;
}

总的时间复杂度为 $\mathrm{O}(n \log n)$。

货箱装船

设有 $n$ 个集装箱，集装箱大小一样，第 $i$ 个集装箱的重量为 $w_i$，船的载重量为 $c$，设计一个装船的方法使得装入的集装箱数量最多。

最优子结构：装载 $k$ 个集装箱后，移除一个集装箱后剩余集装箱的装载问题仍需是最优解。

令 $(x_1, x_2, \cdots, x_k)$ 是一种装载方法：

  • 约束条件：$\displaystyle \sum_{i=1}^{n} w_i \leqslant c$
  • 目标函数：$\displaystyle \sum_{i=1}^{n} w_i$

算法：按重量从小到大对集装箱排序，并依次装入直到超过船的载重量。

证明：设货箱装船问题的最优解为 $(y_1, y_2, \cdots, y_n)$。如果最优解不含箱子1（$y_1=0$），将箱子1替换优化解中某一个箱子得到一个新的解（必须替换，因为如果箱子1还能继续装入船中，则 $(y_1, y_2, \cdots, y_n)$ 不是优化解）。

由于箱子1是最轻的，所以替换后的解仍是可行的。替换后装入的箱子数仍然等于优化解的装箱数，所以它仍是优化解。

经过有限次替换后，新的优化解与设想的贪心解都包含箱子1。反复替换得到一个优化解，它就是设想的贪心解。

0/1背包

设有容量为 $c$ 的背包和 $n$ 件物品，物品 $u_i$ 的重量为 $w_i$，价值为 $p_i$。给出一个装入物品的方法，使得总收益最大。

📝 备注

0/1背包问题是NP难问题，任何多项式复杂度的算法产生的解都是近似解。

当 $p_i = 1$ 时，0/1背包问题退化为货箱装船问题。

0/1背包问题的形式化描述如下：

使用数组 $(x_1, x_2, \cdots, x_n)$ 表示一个装法，其中 $x_i = 1$ 表示装物品 $i$，否则不装。此时约束条件为：

$$\sum_{i=1}^{n} w_i x_i \leqslant c$$

可用的贪心策略：

  1. 价值优先：从未装入的物品中，选取价值最大的物品装入背包。
  2. 重量优先：从未装入的物品中，选择重量最小的物品装入背包。
  3. 价值率优先：选择价值率 $\displaystyle \frac{p_i}{w_i}$ 最高的的物品装入背包。
  4. k-优化算法：先对物品按价值率从大到小排序，现将一些物品装入背包，然后对剩余物品使用贪心法。

使用k-优化算法得到的解误差不超过 $\displaystyle \frac{1}{k+1}$

  • 当 $k=1$ 时为 $50\%$ 以内，即如果优化值为 $100$，贪心法算出的值不低于 $50$；
  • 当 $k=2$ 时，为 $33.33\%$ 以内。

算法的时间复杂度随 $k$ 的增大而增加：需要测试的子集数目为 $\mathrm{O}(n^k)$，每一个子集做贪心法需时间 $\mathrm{O} (n)$，因此当 $k>0$ 时总的时间开销为 $\mathrm{O} (n^{k+1})$.

特别地，如果允许将物品“部分”放入背包，即每种物品可以只取一部分（比如取 60%），价值也按比例计算，则完全可以按照价值密度排序后再使用贪心法求解。

活动安排

设有 $n$ 个活动的集合 $E=\{1,2, \cdots,n\}$，每个活动都要求互斥地使用同一资源。每个活动 $i$ 都有一个要求使用该资源的起始时间 $s_i$ 和一个结束时间 $f_i$，且 $s_i <f_i$（即如果选择了活动 $i$，则它在半开时间区间 $[s_i, f_i)$ 内占用资源）。

现要在所给的活动集合中选出最大的相容活动子集。

若区间 $[s_i, f_i)$ 与区间 $[s_j, f_j)$ 不相交，则称活动 $i$ 与活动 $j$ 是相容的。即当 $s_i \geqslant f_j$ 或 $s_j \geqslant f_i$ 时，活动 $i$ 与活动 $j$ 相容。

使用贪心算法时，应当先对所有活动按照结束时间排序，即先结束的活动排在前。

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25

int s[N];   // 各活动的起始时间
int f[N];   // 各活动的结束时间
bool a[N];
// s和f按结束时间的非减序排列 

int activity_selector(int s[], int f[], bool a[]) {
    int n = s.length - 1;
    // a[i]=true 表示第i个活动被选择。
    a[1] = true;
    // 上一个被选择的活动的索引
    int j = 1;         
    // 被选择的活动的数量
    int count = 1;   
    for (int i=2; i<=n; i++) {
        if (s[i] >= f[j]) {
            a[i] = true;
            j = i;
            count++;
        }
        else {
            a[i] = false;
        }
    }
    return count;
}

排序 $\mathrm{O} (n \log n)$，选择 $\mathrm{O} (n)$，则总复杂度：$\mathrm{O} (n \log n)$。

进一步，如果需要求完成所有活动需要的最少资源数量，则可以使用扫描线算法

哈夫曼编码

前缀码：一种编码方式，其中任意一个字符的二进制代码都不是另一个字符代码的前缀。

使平均码长达到最小的前缀码编码方案称为给定编码字符集C的最优前缀码。哈夫曼编码的核心目标正是通过动态分配最短二进制码（0/1组成的字符串）给不同字符，使得高频字符用更短的编码，低频字符用更长的编码，从而实现整体压缩效率的最优。

平均码长：

$$B(T) = \sum_{c \in C} f(c) \cdot d_T(c)$$

使用哈夫曼编码进行压缩和解压时，必须提前有一个字典

具体算法为：

  1. 根据 $n$ 个权值 $\{w_1, w_2, \cdots, w_n\}$ 构成 $n$ 棵二叉树的集合 $F=\{T_1, T_2, \cdots, T_n\}$，其中每棵二叉树 $T_i$ 中只有一个带权为 $w_i$ 的根结点，其左右子树均为空。
  2. 在 $F$ 中选取两棵根结点的权值最小的树作为左右子树来构造一棵新的二叉树，且置新的二叉树的根结点的权值为其左、右子树结点的根结点的权值之和。
  3. 在 $F$ 中删除这两棵树，同时将新得到的二叉树加入 $F$ 中。
  4. 重复2和3，直到 $F$ 中只含一棵树时为止。称这棵树为最优二叉树（或哈夫曼树）。如果约定将每个结点的左分支表示字符“0”，右分支表示字符“1”，则可以把从根结点到某叶子结点的路径上分支字符组成的字符串作为该叶子结点的编码。

哈夫曼算法以自底向上的方式构造表示最优前缀码的二叉树 $T$。算法以 $|C|$ 个叶结点开始，执行 $|C|-1$ 次的“合并”运算后产生最终所要求的树 $T$。

参见此处：构造哈夫曼编码

算法的优先队列 $Q$ 可以用最小堆实现。初始化优先队列需要 $\mathrm{O} (n\log n)$ 计算时间，由于最小堆的插入和删除运算均需 $\mathrm{O} (\log n)$ 时间，$n-1$ 次的合并总共需要 $\mathrm{O} (n\log n)$。因此关于 $n$ 个字符的哈夫曼算法的计算时间为 $\mathrm{O} (n\log n)$。

哈夫曼编码是典型的贪心算法，因为它在每一步选择中只考虑当前局部最优解（合并频率最小的两个节点），通过这种局部最优的累积，最终达到全局最优（平均码长最短）。

拓扑排序

拓扑排序是一种针对有向无环图（DAG）的线性序列排序方法。该序列满足以下条件：

  • 每个顶点在该序列中仅出现一次。
  • 若图中存在一条从顶点 $u$ 出发到顶点 $v$ 的边，则在序列中 $u$ 必须出现在 $v$ 之前。

贪心法从空集开始，每步产生拓扑排序序列中的一个顶点 $w$：从当前尚不在拓扑排序序列的顶点中选择一顶点 $w$，它的所有先行节点 $v$ 都在已产生的拓扑序列中（或无先行顶点）并将其加入到拓扑序列中。

通过每一步的局部最优选择（即优先处理当前无依赖的顶点）逐步构造全局有效序列。

具体可用减节点入度的方法确定 $w$：即入度变成 $0$ 的顶点为要加到拓扑序列中的新顶点。

参见此处：拓扑排序

📝 备注

该算法也可用于判断图中是否存在环。即如果拓扑排序失败，则有向图含有环路。

设 $V$ 为算法结束时算法输出的节点构成的集合，当失败时 $|V|<n$，且剩下的顶点不能加入已排好的序列 $V$ 中。

则至少有一节点 $q_1$ 和一条边 $(q_2, q_1)$ 且 $q_1, q_2$ 不在V中，否则 $q_1$ 可加入 $V$ 中。

同理，有边 $(q_3, q_2)$ 且 $q_3$ 不在 $V$ 中，否则 $q_2$ 可加入 $V$ 中。若 $q_3=q_1$ 则 $q_1 q_2 q_3$ 是有向图中的一个环；若 $q_3 \ne q_1$，则必存在 $q_4$，$(q_4, q_3)$ 是有向图的边且 $q_4$ 不在 $V$中，否则 $q_3$ 应在 $V$ 中。若 $q_4$ 为 $q_1, q_2, q_3$ 中的任何一个，则该有向图含有环。

因为有向图有有限个节点，重复上述步骤，一定能找到一个环路。

最短路径

单源最短路径问题是图论中的经典问题，其目标是从一个指定的源节点出发，找到到达加权图中所有其他节点的最短路径。这里的“最短”定义为路径上所有边的权重之和最小。

参见此处：Dijkstra算法

最小生成树

Kruskal算法：每次选择权值 $c(e)$ 最小且与之前选择的边不成环的边 $e$。

参见此处：Kruskal算法

Prim算法：从一个顶点开始，然后重复寻找连接已选择顶点和未选择顶点的最小权值的边。

参见此处：Prim算法

偶图覆盖

偶图是图论中的一个重要概念，也称为二分图。偶图中，所有的顶点可以被分为两个不相交的集合，使得图中的每一条边都连接了这两个集合中的两个顶点。

形式化定义：一个图 $G=(V,E)$ 是偶图当且仅当它的顶点集 $V$ 可以被划分为两个互不相交的子集 $(V_1, V_2)$，满足：

  1. $V_1, V_2 \ne \oslash$。
  2. 没有两个在 $V_1$ 中的顶点之间有边相连；没有两个在 $V_2$ 中的顶点之间有边相连。
  3. $V_1$ 中的每个顶点都至少与 $V_2$ 中的一个顶点有边相连，反之也成立。

在偶图中寻找最小覆盖的问题称为偶图覆盖问题。

偶图覆盖问题的应用：

  • 在一个教室里，有学生和座位两类资源，每个学生都有自己喜欢的座位。偶图覆盖问题可以用来找到一个最大的座位安排，使得每个学生都坐在自己喜欢的座位上，并且没有座位重复安排。
  • 在一个电影院里，有电影和观众两类资源，每部电影都有自己的类型。偶图覆盖问题可以用来找到一个最大的观影匹配，使得每个观众都看一部符合他的喜好的电影，并且没有电影重复匹配。

例如，对于如图所示的具有17个顶点的二分图，可划分为子集 $A = \{1, 2, 3, 16, 17\}$ 和 $B = \{4, 5, 6, 7, 8, 9, 10, 11, 12, 13, 14, 15\}$。其中 $A' = \{1, 16, 17\}$ 是 $B$ 的最小覆盖。

偶图覆盖问题

贪心策略：选择覆盖 $B$ 中那些尚未被覆盖的顶点数最多的 $A$ 的节点。

偶图覆盖等价于集合覆盖问题：$n$ 个集合的族 $F=\{S_1, S_2, \cdots, S_n\}$ 满足 $\displaystyle \bigcup_{i=1}^n S_i = U$，设 $\{S_{i1}, S_{i2}, \cdots, S_{ik}\}$ 为 $F$ 的子族且 $\displaystyle \bigcup_{j=1}^n S_{ij} = U$，则称其为 $U$ 的一个覆盖。集合覆盖问题就是要找出包含的集合数目最小的覆盖。

令 $F=\{S_1, S_2, \cdots, S_5\}$，$U=\{4, 5, \cdots, 15\}$，各个子集为 $S_1=\{4,6,7,8,9,13\}$，$S_2=\{4,5,6,8\}$，$S_3=\{8,10,12,14,15\}$，$S_4=\{5,6,8,12,14,15\}$，$S_5=\{4,9,10,11\}$。则 $S'= \{S_1,S_4,S_5\}$ 是一个大小为3的覆盖，没有更小的覆盖，$S'$ 即为最小覆盖。

这个集合覆盖问题可变换为上述的偶图，即用顶点 $1, 2, 3, 16, 17$ 分别表示集合 $S_1, S_2, S_3, S_4, S_5$，顶点 $j$ 表示集合 $U$ 中的元素 $j$ $(4 \leqslant j \leqslant 15)$。两个问题等价，都是NP难问题。

© 2025 - 2026 RunicDolphin806
网站总访客数：Loading

使用 Hugo 构建
主题 Stack 由 Jimmy 设计