408 lines
23 KiB
Markdown
408 lines
23 KiB
Markdown
# 第五章 贪心法 (Greedy Method)
|
||
|
||
|
||
## 目录大纲
|
||
|
||
* **5.1 一般方法**
|
||
|
||
* **5.2 背包问题**
|
||
|
||
* **5.3 带有期限的作业调度问题**
|
||
|
||
* **5.4 最小生成树问题**
|
||
|
||
* **5.5 货郎担问题**
|
||
|
||
* **5.6 小结**
|
||
|
||
|
||
---
|
||
|
||
## 5.1 一般方法
|
||
|
||
### 1. 贪心方法适用的问题特点
|
||
|
||
贪心方法适用于这样一类问题：它有 $n$ 个输入，而它的解就是这 $n$ 个输入的某个**子集**，这些子集必须满足某些事先给定的条件。为了准确描述，引入了以下核心算法术语：
|
||
|
||
* **约束条件**：问题必须满足的条件。
|
||
|
||
|
||
* **可行解**：满足约束条件的输入子集。
|
||
|
||
|
||
* **目标函数**：预先给定的衡量标准（以函数形式给出），用来衡量可行解的优劣。
|
||
|
||
|
||
* **最优解**：使目标函数取极值（极大值或极小值）的可行解。
|
||
|
||
|
||
|
||
> **💡 现实世界引入例（PPT第4页）**：如果有一个机会可以帮助你梦想成真，让你从“1.看足球世界杯总决赛”、“2.游览新西兰风光”、“3.学习潜水”、“4.听阿黛尔的演唱会”中选择**哪两个**活动？组合形式有：(1,2), (1,3), (1,4), (2,3), (2,4), (3,4)。
|
||
> **思考题**：上述术语和这个例子如何对应？
|
||
>
|
||
>
|
||
> * *对应分析*：输入是4个活动；约束条件是“只能选2个”；可行解是任意包含2个活动的子集（共6种组合）；目标函数是你的期望满足度；最优解是让你最开心的那个组合。
|
||
>
|
||
>
|
||
>
|
||
>
|
||
|
||
### 2. 贪心法的求解思想
|
||
|
||
贪心方法是一种“只顾眼前”的分级处理方法：
|
||
|
||
1. 根据题意选取一种**量度标准（Greedy Metric）**；
|
||
|
||
|
||
2. 按该标准一次选中一个输入；
|
||
|
||
|
||
3. 如果这个输入和当前的部分解加在一起**满足约束条件**，则将其加入到部分解中；否则舍弃掉。
|
||
|
||
|
||
|
||
> **思考题**：贪心法得到的可行解是否一定是问题的最优解？取决于贪心法中的哪个环节？
|
||
>
|
||
>
|
||
> * *结论*：不一定是最优解。它是否最优完全取决于**“量度标准”**的选择。
|
||
>
|
||
>
|
||
>
|
||
>
|
||
|
||
### 3. 算法5.1：贪心法的抽象化控制
|
||
|
||
这是贪心算法的通用高层伪代码模版：
|
||
|
||
```pascal
|
||
Procedure GREEDY(A, n)
|
||
// A(1:n) 包含 n 个输入
|
||
solution ← ∅ // 解向量 solution 初始化为空
|
||
for i ← 1 to n do
|
||
x ← SELECT(A) // SELECT: 按某种最优量度标准从 A 中选择一个输入赋值给 x，并从 A 中消去它
|
||
if FEASIBLE(solution, x) then // FEASIBLE: 判定 x 是否可以包含在解向量中
|
||
solution ← UNION(solution, x) // UNION: 将 x 与解向量结合并修改约束判定
|
||
endif
|
||
repeat
|
||
return (solution)
|
||
end GREEDY
|
||
```
|
||
|
||
### 4. 贪心法的优缺点
|
||
* **核心问题**：如何选择能产生问题最优解的量度标准（即最优量度标准）。
|
||
* **缺点**：
|
||
* 不是对所有问题都能得到最优解。
|
||
* 基于目标函数制定的度量标准不一定是最优的。
|
||
* 最优量度标准需要经过严格的数学证明。
|
||
* **优点**：
|
||
* 一旦最优量度标准证明成立后，它就是一种极其高效的算法。
|
||
* 策略的构造简单易行。
|
||
* 对许多问题都能产生整体最优解或者非常优秀的近似最优解。
|
||
|
||
---
|
||
|
||
## 5.2 背包问题 (Fractional Knapsack)
|
||
|
||
### 1. 问题描述
|
||
已知有 $n$ 种物品和一个可容纳 $M$ 重量的背包，每种物品 $i$ 的重量为 $w_i$，假定将物品的某一部分 $x_i$ 放入背包就会得到 $p_i x_i$ 的效益（其中 $0 \le x_i \le 1, p_i > 0, w_i > 0$）。采用怎样的装包方法会使装入背包物品的总效益最大？
|
||
|
||
**形式化数学描述**：
|
||
* 极大化目标函数： $\sum_{1 \le i \le n} p_i x_i$
|
||
* 约束条件： $\sum_{1 \le i \le n} w_i x_i \le M$ 且 $0 \le x_i \le 1$
|
||
|
||
### 2. 问题实例分析
|
||
假设实例为： $n=3, M=20$。效益效益值 $P = (25, 24, 15)$，重量 $W = (18, 15, 10)$。我们可以尝试三种不同的贪心策略：
|
||
|
||
| 贪心量度策略 | 物品挑选顺序与最终解 $(x_1, x_2, x_3)$ | 容量消耗 $\sum w_i x_i$ | 总效益 $\sum p_i x_i$ | 策略优缺点分析 |
|
||
| :--- | :--- | :--- | :--- | :--- |
|
||
| **1. 按效益值非增次序** | 先选物品1，再选物品2：$(1, \frac{2}{15}, 0)$ | $18 + 15 \times \frac{2}{15} = 20$ | $25 + 24 \times \frac{2}{15} = 28.2$ | **缺点**：容量消耗过快 |
|
||
| **2. 按物品重量非降次序** | 先选物品3，再选物品2：$(0, \frac{2}{3}, 1)$ | $10 + 15 \times \frac{2}{3} = 20$ | $24 \times \frac{2}{3} + 15 = 31$ | **缺点**：效益值增长缓慢 |
|
||
| **3. 按 $p_i/w_i$ 比值非增次序** | 比值分别为 $1.39, 1.6, 1.5$。<br>顺序：物品2 $\rightarrow$ 物品3 $\rightarrow$ 物品1。<br>最终解：$(0, 1, \frac{1}{2})$ | $15 + 10 \times \frac{1}{2} = 20$ | $24 + 15 \times \frac{1}{2} = 31.5$ | **优点**：每消耗单位容量，将获得当前最大的效益值（**最优**） |
|
||
|
||
### 3. 算法5.2：背包问题的贪心算法
|
||
*前提：先将物品按 $p_i/w_i$ 比值的非增次序进行降序排序*。
|
||
|
||
```pascal
|
||
procedure GREEDY-KNAPSACK(P, W, M, X, n)
|
||
real P(1:n), W(1:n), X(1:n), M, cu; // X表示解向量，cu表示背包剩余容量
|
||
integer i, n;
|
||
X ← 0; cu ← M
|
||
for i ← 1 to n do
|
||
if (W(i) > cu) then exit endif // 如果当前物品重量大于剩余容量则跳出循环
|
||
X(i) ← 1
|
||
cu ← cu - W(i)
|
||
repeat
|
||
if (i <= n) then X(i) ← cu / W(i) // 说明还有剩余容量，将物品i放入一部分
|
||
end GREEDY-KNAPSACK
|
||
```
|
||
|
||
> **思考题**：该算法的时间复杂度是多少？如何确认它是最优解？
|
||
> * *解答*：如果不包含排序，贪心循环部分的时间复杂度为 $O(n)$（若算上预排序则为 $O(n \log n)$）。通过下面的数学定理来证明其最优性。
|
||
|
||
### 4. 最优量度标准证明的基本思想（剪枝/替换法）
|
||
把算法的贪心解与假定的最优解相比较，如果这两个解不同，就去找开始不同的第一个分量 $x_i$，然后设法用贪心解的 $x_i$ 去替换掉最优解中的该分量，并证明最优解在分量替换前后目标函数值没有任何减少。反复进行这种替换，直到最优解被完全转换成贪心解，从而证明贪心解就是最优解。
|
||
|
||
### 5. 定理5.1：背包问题贪心解最优证明
|
||
**定理**：如果 $\frac{p_1}{w_1} \ge \frac{p_2}{w_2} \ge \dots \ge \frac{p_n}{w_n}$，则算法 `GREEDY-KNAPSACK` 生成一个最优解。
|
||
|
||
**详细证明步骤**：
|
||
1. 设 $X=(x_1, \dots, x_n)$ 是算法生成的贪心解。如果所有 $x_i=1$，显然是最优解。否则，设 $j$ 是使 $x_j \neq 1$ 的最小下标。由算法逻辑可知：
|
||
* 对于 $1 \le i < j$， $x_i = 1$；
|
||
* 对于 $j < i \le n$， $x_i = 0$；
|
||
* 对于 $i = j$， $0 \le x_j < 1$。
|
||
* 此时贪心解的形式为：$(1, \dots, 1, x_j, 0, \dots, 0)$。
|
||
2. 若 $X$ 不是最优解，则必存在一个最优解 $Y=(y_1, \dots, y_n)$ 使得目标函数 $\sum p_i y_i > \sum p_i x_i$。假定整个包全装满，即 $\sum w_i y_i = M$。设 $k$ 是使得 $y_k \neq x_k$ 的最小下标，此 $k$ 必定存在。
|
||
3. 我们可以推断出 **$y_k < x_k$ 必然成立**。因为 $k$ 与 $j$ 的关系只有三种可能：
|
||
* **① 若 $k < j$**：此时依据贪心解有 $x_k = 1$。既然 $y_k \neq x_k$，则必然有 $y_k < 1 = x_k$，即 $y_k < x_k$。
|
||
* **② 若 $k = j$**：如果此时 $x_k < y_k$，由于前面的项都相等且一直加到了满负荷 $\sum w_i x_i = M$，若 $y_k > x_k$ 则会导致 $\sum w_i y_i > M$（超重矛盾）；如果 $y_k = x_k$ 又与假设矛盾，所以必有 $y_k < x_k$。
|
||
* **③ 若 $k > j$**：因为贪心解在第 $j$ 项时就已经把背包全部装满了（$\sum_{i=1}^j w_i x_i = M$），而最优解 $Y$ 在前 $k-1$ 项（包含 $j$）都与 $X$ 完全一样，导致在前 $j$ 项时 $Y$ 的重量就已经达到 $M$。若 $k > j$ 且还有不同的 $y_k$ 存在，必然导致 $Y$ 总重超重 $\sum w_i y_i > M$（矛盾）。因此 $k > j$ 的情况根本不存在。
|
||
4. 现在我们在最优解中进行**替换**：把 $y_k$ 增加到 $x_k$ 的大小，为了保持总重量依然为 $M$，必须从后面的分量 $(y_{k+1}, \dots, y_n)$ 中减去同等的重量。从而构造出一个新解 $Z=(z_1, \dots, z_n)$，满足 $z_i = x_i \, (1 \le i \le k)$。且满足重量关系：
|
||
$$\sum_{k < i \le n} w_i(y_i - z_i) = w_k(z_k - y_k)$$
|
||
5. 计算新解 $Z$ 的效益值：
|
||
$$\sum_{1 \le i \le n} p_i z_i = \sum p_i y_i + (z_k - y_k)p_k - \sum_{k < i \le n} (y_i - z_i)p_i$$
|
||
$$= \sum p_i y_i + (z_k - y_k)w_k \frac{p_k}{w_k} - \sum_{k < i \le n} (y_i - z_i)w_i \frac{p_i}{w_i}$$
|
||
由于物品已经按照 $\frac{p_i}{w_i}$ 降序排列，所以当 $i > k$ 时， $\frac{p_i}{w_i} \le \frac{p_k}{w_k}$。因此有：
|
||
$$\sum p_i z_i \ge \sum p_i y_i + \left[(z_k - y_k)w_k - \sum_{k < i \le n}(y_i - z_i)w_i\right] \frac{p_k}{w_k} = \sum p_i y_i$$
|
||
即 $\sum p_i z_i \ge \sum p_i y_i$。
|
||
6. 因为 $Y$ 已经是假设的最优解，所以只能是 $\sum p_i z_i = \sum p_i y_i$，说明新构造的 $Z$ 也是最优解。如果此时 $Z=X$，则贪心解最优性得证；如果 $Z \neq X$，就对 $Z$ 重复上述讨论，每次都会消除一个与 $X$ 不同的分量，最终必然能将最优解完全等价地转换成贪心解 $X$。证毕。
|
||
|
||
---
|
||
|
||
## 5.3 带有期限的作业调度问题 (Job Scheduling with Deadlines)
|
||
|
||
### 1. 问题描述与核心术语
|
||
在一台机器上处理 $n$ 个作业，每个作业均可在**单位时间**内完成。每个作业 $i$ 都有一个整数截止期限 $d_i > 0$，只有当作业 $i$ 在其截止期限之前被完成，才能获得效益 $p_i > 0$。
|
||
* **可行解**：这 $n$ 个作业的一个子集合 $J$，其中所有作业都能在各自的截止期限前被安全处理完。其效益为 $\sum_{j \in J} p_j$。
|
||
* **最优解**：具有**最大效益值**的可行解。
|
||
|
||
### 2. 问题实例分析
|
||
假设 $n=4$， 效益值 $P = (100, 10, 15, 20)$，截止期限 $D = (2, 1, 2, 1)$。以下是全量的可行解及其处理顺序分析：
|
||
|
||
| 可行解集合 $J$ | 允许的处理顺序（调度序列 $\sigma$） | 总效益值 $\sum p_j$ |
|
||
| :--- | :--- | :--- |
|
||
| $\{1\}$ | 1 | 100 |
|
||
| $\{2\}$ | 2 | 10 |
|
||
| $\{3\}$ | 3 | 15 |
|
||
| $\{4\}$ | 4 | 20 |
|
||
| $\{1, 2\}$ | 2, 1 | $10 + 100 = 110$ |
|
||
| $\{1, 3\}$ | 1, 3 或 3, 1 | $100 + 15 = 115$ |
|
||
| **$\{1, 4\}$** | **4, 1** | **$20 + 100 = 120$（最优解）** |
|
||
| $\{2, 3\}$ | 2, 3 | $10 + 15 = 25$ |
|
||
| $\{3, 4\}$ | 4, 3 | $20 + 15 = 35$ |
|
||
|
||
### 3. 算法5.3：贪心法实现思想
|
||
* **最优量度标准**：选择当前能带来最大效益增量的作业（即按效益 $p_i$ 从大到小降序排列：$p_1 \ge p_2 \ge \dots \ge p_n$）。
|
||
|
||
```pascal
|
||
procedure GREEDY_JOB(D, J, n)
|
||
// 输入的作业已经满足 p1 >= p2 >= ... >= pn；D(1:n)为期限值
|
||
J ← {1} // 效益最大的作业1直接计入
|
||
for i ← 2 to n do
|
||
if (J ∪ {i} 的所有作业都能在它们的截止期限前完成) then
|
||
J ← J ∪ {i}
|
||
endif
|
||
repeat
|
||
end GREEDY_JOB
|
||
```
|
||
|
||
> **思考题**：这个贪心算法一定能提供最优解吗？如何快速验证一个集合 $J$ 是可行的？
|
||
> * *解答*：一定能提供最优解（定理5.2证明）。要判定可行性，只需要把 $J$ 中的作业按**期限非降次序（从小到大）**排序，看是否每一项都满足 $d_{i_j} \ge j$ 即可（定理5.3证明）。
|
||
|
||
### 4. 定理5.2：作业调度最优解的数学证明
|
||
* **证明思路**：设 $J$ 是贪心解， $I$ 是一个最优解。若 $I \neq J$，由贪心策略可知，对于在 $I$ 中而不在 $J$ 中的任意作业 $b$，以及在 $J$ 中而不在 $I$ 中的作业 $a$，必然满足效益值 $p_a \ge p_b$（否则贪心会先选 $b$）。通过在最优解的调度表 $S_I$ 中用 $a$ 替换掉 $b$，可以证明其效益值不会变少，从而逐步证明 $J$ 也是最优解。
|
||
|
||
### 5. 定理5.3：可行调度判定证明
|
||
* **定理**：设 $J$ 是 $k$ 个作业的集合， $\sigma = i_1, i_2, \dots, i_k$ 是 $J$ 的一种排列，且满足 $d_{i_1} \le d_{i_2} \le \dots \le d_{i_k}$。$J$ 是可行解的**充要条件**是：按照 $\sigma$ 的次序处理，每个作业都不违反截止期限（即对所有 $j$， $d_{i_j} \ge j$）。
|
||
|
||
### 6. 算法5.4：基于直接插入排序的贪心算法 (基础实现)
|
||
根据定理5.3，每次加入新作业时，用直接插入法将其按期限从小到大放入 $J$ 中，若放完后仍满足可行性则保留。
|
||
|
||
```pascal
|
||
procedure JS(D, J, n, k)
|
||
integer D(0:n), J(0:n), i, k, n, r
|
||
D(0) ← J(0) ← 0; k ← 1; J(1) ← 1 // 初始化
|
||
for i ← 2 to n do
|
||
r ← k
|
||
while D(J(r)) > D(i) and D(J(r)) ≠ r do // 从后向前寻找插入位置 r+1
|
||
r ← r - 1
|
||
repeat
|
||
if D(J(r)) <= D(i) and D(i) > r then // 满足插入的可行性条件
|
||
for l ← k to r + 1 by -1 do
|
||
J(l+1) ← J(l) // 位置 r+1 到 k 的作业依次后移一位
|
||
repeat
|
||
J(r+1) ← i; k ← k + 1; // 作业 i 正式插入
|
||
endif
|
||
repeat
|
||
end JS
|
||
```
|
||
|
||
* **核心复杂度分析**：外层 `for` 循环 $n-1$ 次，内层 `while` 循环最多 $k \le n$ 次，因此该基础算法的时间复杂度为 **$O(n^2)$**。
|
||
* **思考题**：能否进一步降低时间复杂度？
|
||
|
||
### 7. 优化思想：用空间换时间
|
||
* **核心改变**：若一个作业 $i$ 被计入，我们不把它盲目插入，而是直接将其分配到时间片 $[\alpha-1, \alpha]$，其中 **$\alpha$ 是不大于 $d_i$ 的最大空闲时间片**。如果不存在这样的空闲时间片，则直接拒绝该作业。
|
||
* **示例（PPT第29页）**： $P=(20, 15, 10, 5, 1), D=(2, 2, 1, 3, 3)$。
|
||
* ① 计入作业1： $d_1=2$，分配最大空闲时间片 $[1, 2]$。
|
||
* ② 计入作业2： $d_2=2$， $[1, 2]$ 已被占，向前找到最大空闲 $[0, 1]$ 分配给作业2。
|
||
* ③ 考虑作业3： $d_3=1$， $[0, 1]$ 已满，直接舍弃。
|
||
* ④ 计入作业4： $d_4=3$，分配最大空闲时间片 $[2, 3]$。
|
||
* ⑤ 考虑作业5： 此时没有不大于3的空闲时间片，舍弃。
|
||
* **如何高效找到 $\alpha$**：如果定义一维数组 $F(d)$ 来代表截止期限为 $d$ 的作业当前可用的最大空闲时间片，虽然省去了移位，但仍需要顺序维护。为了彻底消除循环，引入了**集合树（并查集）**。
|
||
|
||
### 8. 补充知识：集合树 (Disjoint Set Tree)
|
||
用于模拟和维护最大可用时间片，同一棵树中的节点拥有相同的最大可用时间片（即根节点对应的值）。
|
||
* **存储规则**：定义一维数组 $P$。
|
||
* 若 $P(i) = -k$ ($k>0$)，说明 $i$ 是根节点， $k$ 为该树的节点总数。
|
||
* 若 $P(i) = k$ ($k>0$)，说明 $i$ 是普通节点，它的父节点是 $k$。
|
||
* **核心操作**：
|
||
* **查找 `FIND(i)`**：基于**压缩规则（路径压缩）**，找到 $i$ 所在树的树根，并把路径上所有节点的父指针直接指向根。
|
||
* **合并 `UNION(i, j)`**：基于**加权规则（小树并入大树）**，将两棵树合并，节点数少的根指向节点数多的根。
|
||
|
||
#### 集合树核心代码：
|
||
```pascal
|
||
procedure FIND(i)
|
||
integer i, j, k
|
||
j ← i
|
||
while PARENT(j) > 0 do j ← PARENT(j) repeat // 找到根节点 j
|
||
k ← i
|
||
while k ≠ j do // 路径压缩
|
||
t ← PARENT(k); PARENT(k) ← j; k ← t
|
||
repeat
|
||
return j
|
||
end FIND
|
||
|
||
procedure UNION(i, j)
|
||
integer i, j, x
|
||
x ← PARENT(i) + PARENT(j)
|
||
if PARENT(i) > PARENT(j) then // 说明树i的节点数少于树j
|
||
PARENT(i) ← j; PARENT(j) ← x
|
||
else
|
||
PARENT(j) ← i; PARENT(i) ← x
|
||
endif
|
||
end UNION
|
||
```
|
||
|
||
### 9. 算法5.5：基于集合树的终极优化算法 (`FJS`)
|
||
* **设计精髓**：我们将时间片抽象为集合树节点。当作业的期限为 $D(i)$ 时，我们通过 `FIND` 迅速拿到它所属树的根节点 $j$。如果对应的最大空闲时间片 $F(j) \neq 0$，则将作业放入，并立刻将当前树 $j$ 和相邻的左边时间片的树 $l = \text{FIND}(F(j)-1)$ 实施 `UNION` 合并，同时更新可用的时间片。
|
||
|
||
```pascal
|
||
procedure FJS(D, n, b, J, k)
|
||
// b = min{n, max{d_j}} 为可能分配的时间片范围
|
||
integer b, D(n), J(n), F(0:b), P(0:b)
|
||
for i ← 0 to b do
|
||
F(i) ← i; P(i) ← -1 // 初始化：各个节点自成一棵树，可用时间片为自身
|
||
repeat
|
||
k ← 0
|
||
for i ← 1 to n do
|
||
j ← FIND(min(n, D(i))) // 寻找 D(i) 所在树的根节点 j
|
||
if F(j) ≠ 0 then
|
||
k ← k + 1; J(k) ← i; // 作业 i 计入解集
|
||
l ← FIND(F(j) - 1);
|
||
call UNION(l, j); // 合并两棵树
|
||
F(j) ← F(l); // 刷新当前根节点的最远可用时间片
|
||
endif
|
||
repeat
|
||
End FJS
|
||
```
|
||
|
||
* **高效性原因**：通过带有路径压缩和加权合并的并查集，查找和合并操作的时间复杂度几近常数 $O(1)$，使整个作业调度的总复杂度从 $O(n^2)$ **降低到了接近 $O(n)$**。
|
||
|
||
### 10. `FJS` 算法完整运行实例
|
||
实例参数： $n=7$， $P = (35, 30, 25, 20, 15, 10, 5)$， $D = (4, 2, 4, 3, 4, 8, 3)$。
|
||
* **初始化**： $F = [0,1,2,3,4,5,6,7]$， 树状态为各自独立且值为 $-1$。
|
||
|
||
* 运行演进过程：
|
||
1. **考虑作业1** ($d_1=4$)： 查找根 $j=4$， $F(4)=4 \neq 0$。安排在时间片 $[3,4]$。 $J=\{1\}$。合并树3和树4，树状态里节点4的父亲变成3，根节点3的权重变成 $-2$。 $F(4)$ 更新为 $F(3)=3$。
|
||
2. **考虑作业2** ($d_2=2$)： 查找根 $j=2$， $F(2)=2 \neq 0$。安排在时间片 $[1,2]$。 $J=\{1,2\}$。合并树1和树2， $F(2)$ 更新为 $F(1)=1$。
|
||
3. **考虑作业3** ($d_3=4$)： 查找根，因4指向3，根 $j=3$， $F(3)=3 \neq 0$。安排在时间片 $[2,3]$。 $J=\{1,2,3\}$。合并树2和树3， $F(3)$ 更新为 $F(2)=1$。
|
||
4. **考虑作业4** ($d_4=3$)： 查找根为1， $F(1)=1 \neq 0$。安排在时间片 $[0,1]$。 $J=\{1,2,3,4\}$。合并树0和树1，此时 $[0,4]$ 时间片全满，其根节点的值 $F$ 均变为了0。
|
||
5. **考虑作业5** ($d_5=4$)： 查找根，一路上溯发现根节点对应的 $F$ 值为 0，**直接舍弃**。
|
||
6. **考虑作业6** ($d_6=8$)： $\min(7,8)=7$， 查找根 $j=7$，$F(7)=7 \neq 0$。安排在时间片 $[6,7]$。 $J=\{1,2,3,4,6\}$。
|
||
7. **考虑作业7** ($d_7=3$)： 查找根对应 $F$ 值为 0，**直接舍弃**。
|
||
|
||
* **最终解**：最优作业集 $J=\{1,2,3,4,6\}$， 实际在机器上的处理次序为 **4, 2, 3, 1, 6**， 能够斩获的最大总效益值为 **120**。
|
||
|
||
---
|
||
|
||
## 5.4 最小生成树问题 (Minimum Spanning Tree - MST)
|
||
|
||
### 1. 问题基础回顾
|
||
* **定义**：设 $G=(V,E)$ 是一个加权无向连通图。一棵生成树是一棵无向树 $T=(V,E')$，其中 $E' \subseteq E$，且 $T$ 的所有边的权值之和是最小的。
|
||
* **约束条件**：包含全部 $n$ 个顶点；只能包含 $n-1$ 条边；**绝对不能形成环（回路）**。
|
||
* **目标函数**：边权值之和达到最小。
|
||
* **贪心量度标准**：将边的权值从小到大进行排列，每次优先尝试加入权值最小的边。
|
||
|
||
### 2. Kruskal 算法描述
|
||
```pascal
|
||
// 输入：加权连通无向图 G=(V,E)
|
||
// 输出：最小生成树 T
|
||
T ← Ø // 存储选中的边
|
||
while T所含的边数少于 n-1 do
|
||
从 E 中选择一条最小权值的边(v,w) 并从 E 中删除它
|
||
if (将(v,w)加入 T 中没有形成一个回路) then
|
||
将(v,w)加入 T 中
|
||
else
|
||
放弃(v,w)
|
||
endif
|
||
repeat
|
||
```
|
||
* **时间复杂度**：包含对边的预排序，时间复杂度为 **$O(n^2 \log n)$** （或者是依据边数 $e$ 写的 $O(e \log e)$）。
|
||
|
||
### 3. 实例运行过程分析
|
||
对于课件给出的图（顶点 A, B, C, D, E）：
|
||
1. **边权值升序排序结果**： (AE):50, (CD):60, (BC):70, (BD):75, (AD):80, (ED):90, (BE):200, (AC):300。
|
||
2. **贪心选择过程**：
|
||
* 选择 **(AE):50** $\rightarrow$ 加入 $T$（无环）
|
||
* 选择 **(CD):60** $\rightarrow$ 加入 $T$（无环）
|
||
* 选择 **(BC):70** $\rightarrow$ 加入 $T$（无环）
|
||
* 检查 (BD):75 $\rightarrow$ 舍弃（会形成 B-C-D 回路）
|
||
* 选择 **(AD):80** $\rightarrow$ 加入 $T$（无环）
|
||
3. **结束**： 此时已成功选满 4 条边（$n-1$），最小生成树成功构建。
|
||
|
||
### 4. Kruskal 算法最优性证明（剪枝替换法）
|
||
* **证明核心**：设 $T$ 是 Kruskal 算法产生的生成树， $T'$ 是最小成本树。若 $E(T) \neq E(T')$，选出一条属于 $E(T)$ 但不属于 $E(T')$ 的最小成本边 $e$。把 $e$ 强行加入 $T'$ 会创造一个环。该环中必有一条边 $e_j \notin E(T)$。
|
||
* 如果 $e_j$ 的成本小于 $e$，根据贪心策略，Kruskal 应该先选 $e_j$，产生矛盾，因此必然有 $c(e_j) \ge c(e)$。我们此时在 $T'$ 中剔除 $e_j$ 换入 $e$，形成新树 $T''$，其成本绝对不会比最小成本树 $T'$ 高。反复进行此操作，可无损地将 $T'$ 变成 $T$，从而证明 Kruskal 的解必定是最优生成树。
|
||
|
||
---
|
||
|
||
## 5.5 货郎担问题 (Traveling Salesman Problem - TSP)
|
||
|
||
### 1. 问题描述
|
||
售货员要到 $n$ 个城市销售货物，已知各城市之间的距离。要求从某一城市出发，**每个城市必须且只能经过一次**，最后回到原出发城市，使得走过的总路程最短。
|
||
|
||
### 2. 贪心策略与失效分析
|
||
* **贪心策略**：每次选择距离当前所在城市**最近**且未访问过的城市作为下一站。
|
||
|
||
<blockquote>
|
||
<p><strong>⚠️ 贪心策略在此问题中失效（PPT第53页、56页）</strong>：</p>
|
||
<ul>
|
||
<li><strong>若从城市1出发</strong>： 贪心路径为 $1 \rightarrow 4 \rightarrow 3 \rightarrow 5 \rightarrow 2 \rightarrow 1$，总距离为 <strong>14</strong>。</li>
|
||
<li><strong>若从城市2出发</strong>： 贪心路径为 $2 \rightarrow 5 \rightarrow 4 \rightarrow 1 \rightarrow 3 \rightarrow 2$，总距离为 <strong>17</strong>。</li>
|
||
<li><strong>然而该图的真正的全局最优解是</strong>： $1 \rightarrow 2 \rightarrow 5 \rightarrow 4 \rightarrow 3 \rightarrow 1$，总距离为 <strong>13</strong>。</li>
|
||
</ul>
|
||
</blockquote>
|
||
|
||
* **结论**：货郎担问题**不满足“贪心选择性质”**。只顾眼前的最好选择，无法推导到全局最优解，贪心法在此只能求出近似解。
|
||
|
||
---
|
||
|
||
## 5.6 小结与理论升华
|
||
|
||
### 1. 贪心选择性质 vs 最优子结构性质
|
||
课件最后精辟地总结了判定一个问题能否用贪心法求解的核心理论依据：
|
||
|
||
* **贪心选择性质（充分条件）**：
|
||
* 指全局最优解可以通过一系列局部最优（贪心）的选择来达到。
|
||
* 求解时只需要考虑当前情况，不需要依赖或者考虑子问题的解。
|
||
* **最优子结构性质（必要条件）**：
|
||
* 指一个问题的最优解中包含其子问题的最优解。
|
||
* 满足贪心法的问题一定具备最优子结构性质。
|
||
|
||
### 2. 章节核心要点提炼
|
||
1. **一般方法**：必须牢固掌握约束条件、可行解、最优解和目标函数的定义，理解量度标准的关键作用。
|
||
2. **背包问题**：记住按 **$p_i/w_i$ 比值降序** 是最优量度标准，掌握替换法证明思想。
|
||
3. **作业调度问题**：利用**集合树（并查集）**的路径压缩和加权合并，能够把算法复杂度从 $O(n^2)$ 极限优化到 **$O(n)$**。
|
||
4. **最小生成树**：掌握 **Kruskal 算法** 边排序加回路判定的贪心流程及最优性证明。
|
||
5. **货郎担问题**：作为典型的 NP 难问题，它说明了贪心法的局限性（无法求得精确最优解），但贪心法常用于此类复杂问题的**近似算法设计**中。
|
||
|