第三部分：精确最优化策略

本部分聚焦于解决多阶段决策过程、和组合优化问题，旨在寻找全局最优解。

3.1 动态规划 (Dynamic Programming)

3.1.1 动态规划和多阶段决策

动态规划是解决多阶段决策过程 (Multi-stage decision process) 最优化的一种方法。对于离散问题，解析数学无法施展，动态规划则成为一个非常有效的工具。

不同于线性规划等方法，动态规划建立目标函数方程后，没有通用的求解算法，需结合具体问题特性采用相应的数学技巧，且随着状态变量维度的增加，计算量呈指数级增长。

依据决策过程的时间参量与演变性质，动态规划模型可划分为以下四个维度：

时间参量维度：
离散决策过程 (Discrete)：过程可被划分为有限个阶段。

连续决策过程 (Continuous)：过程随时间连续变化。
演变性质维度：
确定性决策过程 (Deterministic)：状态转移是确定的。

随机性决策过程 (Stochastic)：状态转移服从某种概率分布。

通常来说，动态规划算法时间复杂度为多项式级，最终的目标是获得最优策略族，即每一个中间节点到重点的最优路线。

多阶段决策通常具备以下特征：

阶段划分：过程可分解为若干相互关联的时序阶段。
决策关联性：当前阶段的决策不仅决定当前状态的输出，更直接影响下一阶段的状态及决策环境，从而通过状态转移决定整个过程的轨迹。
策略 (Strategy)：各阶段决策构成的有序序列称为策略。
最优化目标：在可行策略集合中，根据预设的评价标准，甄选出使活动效果达到最佳的最优策略 (Optimal Strategy)。

例如最短路径问题、分配问题（之前提到的背包问题）、生产与库存规划问题等等。

多阶段决策问题的无后效性 (Markov Property)：某阶段之后的过程发展，仅取决于该阶段的状态，而与该阶段之前的过程如何演变无关。

DP 模型

阶段 (Stage)
将问题全过程按时间或空间特征，恰当地划分为若干个相互联系的子过程，称为阶段。通常用变量 $k$ 表示阶段序号。

状态 (State)
描述某阶段出发位置或状况的变量。状态既是当前阶段某支路的起点，也是前一阶段某支路的终点。常用 $x_k$ 表示第 $k$ 阶段的某一状态。第 $k$ 阶段所有可能状态的集合记为 $X_k$。 $X_k = \{ x_k(1), x_k(2), \dots, x_k(r) \}$

决策 (Decision)
当某阶段状态给定后，从该状态演变到下一阶段某状态的选择行为。常用 $u_k(x_k)$ 表示第 $k$ 阶段处于状态 $x_k$ 时的决策变量。决策变量的取值范围称为允许决策集合，记为 $D_k(x_k)$。

策略 (Policy)
由各个阶段的决策组成的序列。从第 1 阶段到终点的完整决策序列被称为全过程策略，记为 $p_{1,n}$。

$p_{1,n}(x_1) = \{ u_1(x_1), u_2(x_2), \dots, u_n(x_n) \}$

从第 $k$ 阶段到终点的后部子过程决策序列被称为子策略，记为 $p{k,n}$。$$p{k,n}(xk) = { u_k(x_k), u{k+1}(x_{k+1}), \dots, u_n(x_n) }$$
在允许策略集合 $P$ 中，使目标达到最优效果的策略被称为最佳策略。

指标函数 (Objective Function)
衡量过程优劣的数量指标，是定义在全过程或后部子过程上的函数。常用 $V{k,n}$ 表示从第 $k$ 阶段到终点的指标函数。$$V{k,n} = V{k,n}(x_k, u_k, x{k+1}, \dots, x{n+1})$$
第 $k$ 阶段从状态 $x_k$ 采取决策 $u_k$ 所产生的直接效益或成本，成为阶段指标，记为 $d_k(x_k, u_k)$。
指标函数 $V{k,n}$ 在最优策略下达到的极值（最大值或最小值）被称为最优指标函数 (Optimal Value Function)，记为 $f_k(x_k)$，表示从第 $k$ 阶段的状态 $x_k$ 出发，到终点所能达到的最短距离（或最大利润等）。

最优化原理

贝尔曼 (Bellman) 的最优化原理：

如果一条路线是起始点到终点的最优路径（最短路线），那么该路线上任意一点到终点的子路径，对于从该点出发到达终点的所有可能选择来说，也必定是最优的。

基于上述原理，动态规划通常采用逆序递推 (Backward Induction) 的方法：从终点出发，逐段向始点方向寻找最优子策略。

基本方程

如上所述，动态规划利用相邻两个阶段（$k$ 与 $k+1$）之间的递推关系来求解。其核心方程（贝尔曼方程形式）如下：

$\begin{aligned} &f_k\left(x_k\right)=\min _{u_k \in D_k\left(x_k\right)}\left\{d_k\left(x_k, u_k\left(x_k\right)\right)+f_{k+1}\left(x_{k+1}\right)\right\}\\ &k=n, n-1, \ldots, 1 \end{aligned}$

当前状态 $xk$ 的最优指标等于“当前阶段实施决策 $u_k$ 的即时效益”与“由此进入下一状态 $x{k+1}$ 后的最优后续效益”之和的极值。

由此，动态规划模型要求满足四个核心要素：

状态变量必须满足无后效性 (Markov Property)
确定每个阶段的决策变量 $u_k$，以及在该状态下的允许决策集合 $D_k(x_k)$。
描述由第 $k$ 段状态演变至第 $k+1$ 段状态的规律，即状态转移方程。下一阶段状态由当前状态和当前决策唯一确定。 $x_{k+1} = T_k(x_k, u_k)$
标函数 $V{k,n}$ 必须定义在全过程或后部子过程上，并满足递推关系（通常由分离性条件保证）：$$V{k,n}[xk, p{k,n}] = \psi [dk(x_k, u_k), V{k+1, n}(x{k+1}, p{k+1, n})]$$
函数 $\psi$ 需对变元 $V_{k+1, n}$ 严格单调。

3.1.2 经典应用实例

资源分配问题

资源分配问题旨在将有限的资源（如资金、设备、原材料等）分配给若干个使用者（或生产项目），以使系统的整体效用（如总收益、总产量）最大化。

设资源总量为 $a$，用于 $n$ 种产品的生产。

阶段：按分配给每个使用者的过程划分，通常第 $k$ 阶段对应第 $k$ 种产品的分配。
状态变量 ( $x_k$)：表示分配给第 $k$ 种至第 $n$ 种产品的可用资源总量。
决策变量 ($u_k$)：分配给第 $k$ 种产品的具体资源量。允许决策集合：$0 \le u_k \le x_k$（不能超出可用资源总量）。
状态转移：$x_{k+1} = x_k - u_k$。即剩余资源量等于当前资源量减去当前决策分配量。
基本方程：令 $g_k(u_k)$ 为第 $k$ 种产品获得资源 $u_k$ 时的收益，$f_k(x_k)$ 为从第 $k$ 种产品开始分配，拥有资源 $x_k$ 时的最大总收益。 $f_k(x_k) = \max_{0 \le u_k \le x_k} \{ g_k(u_k) + f_{k+1}(x_k - u_k) \}$
边界条件：$f_{n+1}(x) = 0$。（只是用于终止递归，本身并无含义）

生产与存储问题

在满足各时期市场需求且期末库存归零的约束下，确定各阶段的产量（决策变量），使得全周期的生产成本与库存费用之和最小。通常在离散时间上求解。

阶段：离散时间
状态：库存
决策变量：生产的量
状态转移： $x_{k+1} = x_k + u_k - d_k$
基本方程：$Jk(x_k) = \min{uk} { \text{生产成本}(u_k) + \text{存储费用}(x_k+u_k-d_k) + J{k+1}(x_{k+1}) }$。

Algorithm ProductionInventory(N, MaxInv, D, CostP, CostS)
// 输入：N (周期数), MaxInv (最大库容), D[k] (第 k 期需求), CostP(u) (生产 u 的成本), CostS(x) (存储 x 的费用)
// 输出：最小总成本 MinCost

1. // 初始化边界：第 N+1 期（结束时）要求库存为 0，成本为 0
2. F[N+1, 0] ← 0
3. for x ← 1 to MaxInv do F[N+1, x] ← infinity

4. // 逆序递推
5. for k ← N down to 1 do
6.    for x_curr ← 0 to MaxInv do
7.       min_c ← infinity
8.       // 决策 u (产量) 需满足：不缺货且不爆仓
9.       // 约束：x_next = x_curr + u - D[k]
10.      for u ← 0 to (MaxInv + D[k] - x_curr) do
11.         x_next ← x_curr + u - D[k]
12.         if x_next ≥ 0 then
13.            val ← CostP(u) + CostS(x_next) + F[k+1, x_next]
14.            if val < min_c then min_c ← val
15.         end if
16.      end for
17.      F[k, x_curr] ← min_c
18.   end for
19. end for
20. return F[1, 0] // 假设初始库存为 0

值得注意的是，这里我们是从后往前构建F表，因为我们首先知道F表的最后一行。第一次迭代计算倒数第二行，以此类推。

复合系统工作可靠性问题

对于一个由 $N$ 个部件串联组成的系统，其整体可靠性取决于各部件的可靠性乘积。通过为每个部件 $i$ 增加备用件 $z_i$（并联冗余），可以提高该部件的可靠性 $p_i(z_i)$，但会受到总成本 $C$ 和总重量 $W$ 的约束。

注意到系统受到成本和重量两重制约，因此需要构建二维状态。

阶段：考虑部件i
状态：第i步的总重量和总成本$(x{w,i},x{c,i})^t$
决策变量：在第二部是否增加备用件，增加多少
状态转移：$x{k+1} = x{k}+N(w,c)^t$
基本方程：$fk(w_k，c_k) = max{uk}{p_k(u_k)f{k-1}(w_k-u_kw,c_k-u_kc)}$

注意，这里使用已经选择的总成本和总重量作为状态。因此，在基本方程中并不像之前我们使用的那样，建立$xk$和$x{k+1}$的关系。换句话说，我们在这里使用了一种正向的做法，而非之前提到的逆向做法。这两种做法是等价的，只要我们更换状态的定义就可以互相转换。

对于如最短路径问题，因为约束是起点的路程为0，如果我们正向计算，很容易得知表格的第一行的内容，因此我们倾向于正向计算；而对于上一个生产与储存问题，因为约束要求最终的储存量为0，我们知道表格最后一行的内容，因此我们倾向于逆向计算。对于这个问题，因为我们既知道总成本和总重量的约束，又知道开始时的成本和重量势必为0，因此使用那种方法区别不大。

以下给出逆向的伪代码，可以与以上方程进行比较：

Algorithm SystemReliability(N, TotalC, TotalW, P, C, W)
// 输入：N, TotalC, TotalW,  P[k, z] (部件 k 装 z 个备件的可靠性), C[k, z] (费用), W[k, z] (重量)

1. // 初始化：第 N+1 阶段可靠性为 1 (乘法单位元)
2. for c ← 0 to TotalC do
3.    for w ← 0 to TotalW do
4.       F[N+1, c, w] ← 1
5.    end for
6. end for

7. // 逆序递推
8. for k ← N down to 1 do
9.    for c ← 0 to TotalC do
10.      for w ← 0 to TotalW do
11.         max_rel ← 0
12.         // 决策 z: 备用件数量，从 1 开始 (至少 1 个)
13.         z ← 1
14.         While C[k, z] ≤ c and W[k, z] ≤ w do
15.            curr_rel ← P[k, z] * F[k+1, c - C[k, z], w - W[k, z]]
16.            if curr_rel > max_rel then max_rel ← curr_rel
17.            z ← z + 1
18.         end While
19.         F[k, c, w] ← max_rel
20.      end for
21.   end for
22. end for

23. return F[1, TotalC, TotalW]

排序问题

$n$ 个工件需依次在机床 A 和机床 B 上加工，已知各工件在 A、B 上的加工时间分别为 $a_k, b_k$。目标是确定加工顺序，使总加工时间（Makespan）最短。

阶段：考虑第i个被加工的元件
状态：已经加工的工件集合S
决策变量：选择第u_i的零件作为第i个被加工的零件k
转移方程：$K = Ui$，另有 $(t{i+1,a},t{i+1,b}) = (t{i,a},t{i,b}) + PUNISH(t{i,a},t{i,b}, a{ui},b{u_i})$
其中PUNISH函数是为了保证依次加工所需的额外等待时间。分类讨论可得以下情况：
如果$t{i,b}-t{i,a} >= a_{u_i}, PUNISH = (0,0)$
如果$t{i,b}-t{i,a} < a{u_i}$且 $t{i,b}-t{i,a} >= 0$[事实上这项总是成立]， $PUNISH = (a{ui}-(t{i,b}-t_{i,a}))$，这意味着机器B已经完成上一个工件的加工，但是A还没完成这个工件的加工，因此B要等待一段时间。
基本方程：$fi(S) = min{k\in S \& k != ui}(f{i-1}(k)+t{i,b}+t{i,a}+PUNISH(t{i,a},t{i,b}, a{u_i},b{u_i}))$

根据这个基本方程，由于选择了被加工的工件集合作为状态，那么总共的可能的集合数量$2^n$势必会出现在时间复杂度中，因此这个方法至少是一个$O(2^n)$的算法。

基于动态规划框架的修改包括选取 $(X, t)$ 为状态，其中 $X$ 是待加工工件集合，$t$ 是机床 B 滞后于机床 A 的相对时间。如此可以代替PUNISH函数的复杂定义。更好的方法是将问题转化为贪心算法：

在所有未排序工件的加工时间 ${a_1 \dots a_n, b_1 \dots b_n}$ 中寻找最小值。
若最小值为 $a_i$（在机床 A 上的时间），则将工件 $i$ 排在最前面。
若最小值为 $b_i$（在机床 B 上的时间），则将工件 $i$ 排在最后面。
从集合中移除该工件，重复上述步骤直至排完。

这种算法被称为约翰逊法则。

3.1.3 使用动态规划思想的示例

计算二项式系数、最长公共子序列、矩阵链相乘

除此之外，计算二项式系数、最长公共子序列和矩阵链相乘也可以使用动态规划算法求解，将问题展示于此：

二项式系数 $C(n, k)$ 表示从 $n$ 个元素集合中选取 $k$ 个元素的组合数（子集数量），其中 $0 \le k \le n$。它因出现在二项式定理的展开式系数中而得名。

边界条件：$C(n, 0) = 1$/$C(n, n) = 1$

递推关系： $C(n, k) = C(n-1, k-1) + C(n-1, k)$

Algorithm Binomial(n, k)
    for i ← 0 to n do
        for j ← 0 to min(i, k) do
            if j = 0 or j = i then
                C[i, j] ← 1
            else
                C[i, j] ← C[i-1, j-1] + C[i-1, j]
    return C[n, k]

子序列是在原序列中删除若干元素（也可以不删）后得到的序列，保持相对顺序不变。例如$X = {A, B, C, B, D, A, B}$，其子序列可以是 ${B, C, D, B}$。

给定两个序列 $X={x_1, \dots, x_m}$ 和 $Y={y_1, \dots, y_n}$，找出它们的一个最长公共子序列。

动规的思想是维护一个二维表格，记录到第一个序列的位置i和第二个序列的位置j，可形成的最长子序列的长度。

其动规递推公式为：

$L[i, j] = \begin{cases} 0 & \text{若 } i=0 \text{ 或 } j=0 \\ L[i-1, j-1] + 1 & \text{若 } x\_i = y\_j \\ \max(L[i, j-1], L[i-1, j]) & \text{若 } x\_i \neq y\_j \end{cases}$

Algorithm LCS(A, B, n, m)
    // 初始化边界
    for i ← 0 to n do L[i, 0] ← 0
    for j ← 0 to m do L[0, j] ← 0
    
    // 填表
    for i ← 1 to n dos
        for j ← 1 to m do
            if A[i] = B[j] then
                L[i, j] ← L[i-1, j-1] + 1
            else
                L[i, j] ← max(L[i, j-1], L[i-1, j])
    return L[n, m]

矩阵乘法满足结合律，即 $(M_1 M_2) M_3 = M_1 (M_2 M_3)$，但不同的计算顺序（加括号的方式）会导致极为不同的标量乘法次数。

给定 $n$ 个矩阵的链，找到一种加括号方案，使得总的数量乘法次数最少。

这种算法本身有点类似于双指针问题，与子序列算法很像：

Algorithm MemoizedMatrixChain(r)
1. n ← length[r] - 1
2. for i ← 1 to n do
3.    for j ← 1 to n do
4.       M[i, j] ← Infinity
5.    end for
6. end for
7. return LookupChain(M, r, 1, n)

Algorithm LookupChain(M, r, i, j)
1. if M[i, j] < Infinity then
2.    return M[i, j]
3. end if
4. if i = j then
5.    M[i, j] ← 0
6.    return 0
7. end if
8.  for k ← i + 1 to j do
9.     q ← LookupChain(M, r, i, k-1) + LookupChain(M, r, k, j) + r[i] * r[k] * r[j+1]
10.    if q < M[i, j] then
11.       M[i, j] ← q
12.    end if
13. end for
14. return M[i, j]

以上伪代码使用了自顶向上的写法，可做参考。

0/1背包问题

$U={u_1, u_2, \dots, u_n}$ 是一个准备放入容量为 $C$ 的背包中的 $n$ 项物品的集合。对于 $1 \le j \le n$，令 $s_j$ 和 $v_j$ 分别为第 $j$ 项物品的体积和价值，$C, s_j, v_j$ 都是正整数。

用 $U$ 中的一些物品来装背包，这些物品的总体积不超过 $C$，然而要使它们的总价值最大。假设每项物品的体积不大于 $C$，给出有 $n$ 项物品的 $U$，我们要找出一个子集合 $S \subseteq U$，使得 $\sum{u_i \in S} v_i$ 在约束条件 $\sum{u_i \in S} s_i \le C$ 下最大。

这是一个组合问题。类似的问题我们在排序问题中见到过，如果直接使用每次选择的集合作为状态变量，会导致指数级别的时间复杂度。

如果我们希望考虑第k的物体要不要放进去，递推式应该类似于：

$V_k = min\{V_{k-1}(-)+v_k, V_{k-1}(-)\}$

V_k应该与某个状态有关，但为了避免指数级别的时间复杂度，应该避免直接使用已经选择的集合作为状态变量，唯一剩余的性质，也就是占用的空间大小了。最终的递归式应该类似于：

$V[i, j]= \begin{cases}0 & \text { 若 } i=0 \text { 或 } j=0 \\ V[i-1, j] & \text { 若 } j \backslash<s_{-} i \\ \max V[i-1, j], V\left[i-1, j-s_{-} i\right]+v_{-} i & \text { 若 } j \geq s_{-} i\end{cases}$

这个算法的复杂度是$O(n \cdot C)$，但是注意，这并不是一个多项式算法，这个算法的复杂度取决于背包容量C，因此当C非常大时，算法效率会降低，通常被称作伪多项式算法。

所有点对的最短路径问题

设 $G = (V, E)$ 是一个有向图，其中的每条边 $(i, j)$ 有一个非负的长度 $l[i, j]$。如果从顶点 $i$ 到顶点 $j$ 没有边，则 $l[i, j] = \infty$。

问题：找出从每个顶点到其他所有顶点的距离（从顶点 $x$ 到顶点 $y$ 的距离是指从 $x$ 到 $y$ 的最短路径的长度）。

假设 $V = {1, 2, \dots, n}$。设 $i$ 和 $j$ 是 $V$ 中两个不同的顶点，容易想到$d_{i,j}$是出现在递归方程中，递归方程应该符合类似于：

$d_{i,j}(?) = min(d_{i,j}(?-1) + cost)$

的形式。与上一个问题缺少状态不同，这个问题缺少了阶段的定义。定义 $d^k_{i,j}$ 是从 $i$ 到 $j$，并且不经过 ${k+1, k+2, \dots, n}$ 中任何顶点的最短路径的长度，即可得到递归式：

$d^k_{i,j} = \begin{cases} l[i, j] & \text{若 } k=0 \\ \min \{ d^{k-1}_{i,j}, \quad d^{k-1}_{i,k} + d^{k-1}_{k,j} \} & \text{若 } 1 \le k \le n \end{cases}$

在上述递归式中，使用$n\times n$的矩阵$D_k$来代替张量进行迭代，极为Floyd算法，能计算出每个顶点到其他所有顶点的距离。

Algorithm FLOYD
1. D ← l  
2. for k ← 1 to n do
3.    for i ← 1 to n do
4.       for j ← 1 to n do
5.          D[i,j] = min{ D[i,j], D[i,k] + D[k,j] }
6.       end for
7.    end for
8. end for

分组背包问题

给定背包容量 $W$ 与 $N$ 个物品，每个物品 $i$ 定义为三元组 $(wi, v_i, q_i)$，其中 $w_i$ 为重量，$v_i$ 为价值，$q_i$ 为依赖索引（若 $q_i=0$ 则 $i$ 为主件；若 $q_i>0$ 则 $i$ 为依赖于主件 $q_i$ 的附件，且每个主件最多有 2 个附件）；目标是寻找二元决策向量 $\mathbf{x} = {x_1, x_2, …, x_N} \in {0,1}^N$，在满足容量约束 $\sum{i=1}^N wi x_i \le W$ 以及依赖约束 $\forall i: q_i > 0, x_i = 1 \implies x{qi} = 1$ 的前提下，最大化总价值 $Z = \sum{i=1}^N v_i x_i$。

与0/1背包问题相似，我们容易看出递推方程应该符合

$Z_i(?) = min(Z_{i-1}(?(w_i,q_i))+v_i, Z_{i-1}(?(0,0)))$

同样需要定义状态。如果我们要记录主件，也会导致如之前提及的指数级别的时间复杂度。注意到，附件只依赖于对应主件，因此可以分组解决该问题，重新定义阶段为考虑第i个主件。

写出递归方程（先不考虑边界）：

$V[i,j] = \max \left( V[i-1,j], \quad \max_{(w, v) \in S_k \text{ 且 } w \le j} \{ V[i-1,j - w] + v \} \right)$

戳气球

给定一个正整数序列 $N = (n1, n_2, \dots, n_k)$，代表 $k$ 个气球上的标号。
为了方便处理边界，我们预先在序列两端添加两个虚拟气球，标号均为 1。
现在的序列为 $A = (a_0, a_1, \dots, a{k}, a{k+1})$，其中 $a_0 = a{k+1} = 1$，且 $a_i = n_i$ (对于 $1 \le i \le k$)。

每次选择一个索引 $i$ ($1 \le i \le k$) 进行“戳破”。
获得收益 $V = a{left} \times a_i \times a{right}$。

寻找一个消除序列（即 $1$ 到 $k$ 的全排列），使得依次戳破所有气球（仅剩两个虚拟边界）后，获得的总收益 $\sum V$ 最大。

我们希望去得到一个排列，如果直接输出，显然时间复杂度是指数级别。为此，我们应该用表格构建过程中的某个中间量来指示序列。理想情况下，表格每次迭代可能会指出排列的位置。

我们之前的方法，比如0/1背包问题，将“选择谁不选择谁”的问题，转化为了在如果一个片段已经最优化，那增加一个元素时会发生什么的问题。增加的元素如果被接纳，那么这个元素的序号被记录。

而这个问题，包括之前讨论过的矩阵相乘问题。它本质上是结构划分问题，每一次决策都是在将大区间切割成两个独立的子结构。某种意义上，可以认为是分治和减治的差异。所以那个切割点正是我们要记录进排列中的内容。

递归方程：

$dp[i][j] = \max_{i < k < j} \{ dp[i][k] + dp[k][j] + \mathbf{nums[i] \cdot nums[k] \cdot nums[j]} \}$

这种问题还包括：

有一个凸多边形，顶点按顺时针方向依次标记为 $A[0], A[1], …, A[N-1]$。每个顶点 $A[i]$ 都有一个正整数权值 $v_i$。要将这个凸多边形剖分成 $N-2$ 个三角形：

你可以连接任意两个不相邻的顶点形成一条对角线，但对角线之间不能在多边形内部相交。
每形成一个三角形（由顶点 $i, j, k$ 组成），该三角形的“得分”为三个顶点权值的乘积：$v_i \times v_j \times v_k$

相比于这个问题可能更加清晰一些。

有向图的传递闭包

定义一个 $n$ 顶点有向图的传递闭包为一个 $n$ 阶布尔矩阵 $T = {t{ij}}$。如果从顶点 $i$ 到顶点 $j$ 存在一条有效的有向路径，则 $t{ij}=1$，否则为 0。

直接遍历（DFS/BFS）效率较低，Warshall 算法 提供了一种基于矩阵计算的高效方法。

该算法构造一系列矩阵 $R^{(0)}, \dots, R^{(n)}$。其中 $R^{(k)}$ 的元素 $r_{ij}^{(k)}$ 为 1 当且仅当存在一条从 $v_i$ 到 $v_j$ 的路径，且路径上所有中间顶点的编号均不大于 $k$。

$R^{(0)}$：邻接矩阵（无中间顶点）。
$R^{(n)}$：传递闭包（允许所有顶点作为中间点）。

对于 $R^{(k)}$ 中的元素，路径分为两种互斥情况：

不经过 $vk$：路径完全包含在 $1 \dots k-1$ 的范围内，即 $r{ij}^{(k-1)}$。
经过 $v_k$：路径分解为 $v_i \to v_k$ 和 $v_k \to v_j$，且这两段子路径的中间顶点均 $\le k-1$。

$r_{ij}^{(k)} = r_{ij}^{(k-1)} \lor (r_{ik}^{(k-1)} \land r_{kj}^{(k-1)})$

Algorithm Warshall(A[1..n, 1..n])
1. R ← A
2. for k ← 1 to n do
3.    for i ← 1 to n do
4.       for j ← 1 to n do
5.          R[i, j] ← R[i, j] or (R[i, k] and R[k, j])

此算法的时间复杂度为 $\Theta(n^3)$。

最优二叉查找树

在键值查找概率已知（且不均等）的情况下，OBST 旨在构建一棵平均键值比较次数（即加权路径长度）最低的二叉查找树。这与传统的平衡二叉树不同，高频元素应更靠近根节点。

设 $a1, \dots, a_n$ 为有序键，$p_1, \dots, p_n$ 为查找概率。令 $C[i, j]$ 为由键 $a_i, \dots, a_j$ 构成的最优二叉树的最小平均查找次数。当选择 $a_k$ ($i \le k \le j$) 作为根节点时，左子树 $T{i, k-1}$ 和右子树 $T_{k+1, j}$ 的所有节点深度均增加 1。这意味着总成本增加了该子树内所有节点的概率之和。

递推方程 $C[i, j] = \min_{i \le k \le j} \{ C[i, k-1] + C[k+1, j] \} + \sum_{s=i}^{j} p_s$

3.1.4最优性近似与策略迭代

针对阶段数不确定或无限的多阶段决策问题（如不定步数最短路），传统的递推无法确定边界 $N$。此类问题通常通过迭代逼近求解。

逐次逼近法 (Successive Approximation)即值迭代 (Value Iteration)。通过不断增加步数 $k$，计算指标函数 $f_k(i)$ 直至收敛：
$f_k(i) = \min_j \{ c_{ij} + f_{k-1}(j) \}$
策略迭代法 (Policy Iteration)将“策略”与“价值”解耦，通过交替更新来逼近最优。
初始化：选择一个无回路的初始策略 $u0(i)$（即在状态 $i$ 下采取的动作）。
策略评估 (Policy Evaluation)：基于当前策略 $u_k$，求解方程组得到该策略下的价值函数 $f_k(i)$：$$f_k(i) = c{i, uk(i)} + f_k[u_k(i)]$$
策略改进 (Policy Improvement)：利用计算出的 $f_k$，贪心地寻找更优策略 $u{k+1}$： $u_{k+1}(i) \leftarrow \arg\min_u \{ c_{i,u} + f_k(u) \}$
重复上述步骤，直到 $uk(i) = u{k-1}(i)$ 对所有 $i$ 成立，此时获得最优策略。

3.2 回溯法 (Backtracking)

许多问题都可以穷尽有限搜索空间来得到解，而又存在许多仅有穷尽搜索一种解法的算法。对于这些算法，通常需要减少搜索空间。

P问题和NP问题
P 类问题 (Polynomial time)是可以在多项式时间 (Polynomial Time) 内被计算机解决的问题
NP 类问题是可以在多项式时间内被验证 (Verify) 一个解的问题。如哈密尔顿回路：给你一张图，让你找回路很难。但如果我给你一条路径，你检查它是否经过所有点且首尾相连，非常快。
NP-完全 (NP-Complete) 需要满足问题 $X$ 本身的解可以在多项式时间内被验证。任何 NP 问题都可以在多项式时间内归约 (Reduce) 为问题 $X$。[如果能找到一个多项式时间的算法来解决问题 $X$，那么所有的 NP 问题（比如哈密尔顿回路、3着色、背包问题）都可以转化为 $X$ 并在多项式时间内解决。NP-Hard]

组织搜索的一般技术之一是回溯法。这种算法设计技术可以被描述为有组织的穷尽搜索，它常常可以避免搜索所有的可能性。

3.2.1 回溯法

回溯法针对所要做的选择：

构造一棵所谓的状态空间树，树的每一层节点代表了对解的每一个分量所做的选择。
用深度优先法 (DFS) 搜索状态空间树。
在状态空间树中的任一节点，满足一定条件的情况下，搜索回溯（即：如果当前节点不包含有效解，则停止沿该分支的搜索，返回上一层）。

3.2.2 典型应用

3着色问题

给出一个无向图 $G=(V, E)$，需要用三种颜色之一为 $V$ 中的每个顶点着色，三种颜色分别为 1，2 和 3，使得没有两个邻接的顶点有同样的颜色。

一种着色可以用 $n$ 元组 ${c_1, c_2, \dots, c_n}$ 来表示，使 $c_i \in {1, 2, 3}, 1 \le i \le n$。

一个 $n$ 个顶点的图共有 $3^n$ 种可能的着色，所有可能的着色的集合可以用一棵完全的三叉树来表示，称为搜索树。那么后续的步骤很好理解：

Algorithm 3-COLORREC
输入：无向图 G=(V, E)。
输出：G 的顶点的 3 着色 c[1...n], 其中每个 c[j] 为 1，2 或 3。
1. for k ← 1 to n
2.    c[k] ← 0
3. end for
4. flag ← false
5. graphcolor(1)
6. if flag then output c
7. else output “no solution”

Algorithm graphcolor(k)
1. for color = 1 to 3
2.    c[k] ← color
3.    if c 为原问题的合法解 then flag ← true and exit
4.    else if c 是部分解 then graphcolor(k + 1)
5. end for

代码中的合法解和部分解分别代表：

如果从根到当前节点的路径对应于一个合法着色，且图中所有点均已着色，过程终止
如果这条路径的长度小于 $n$，并且相应的着色是合法的

这种算法的最坏时间复杂度就是树的大小乘以合法性检查所需要O(n)的时间复杂度：$T_{worst} = O(n3^n)$。合法性检查需要遍历某个顶点所有的邻接顶点，因此是O(n)。

N 皇后问题

8 皇后问题：如何在 $8 \times 8$ 的国际象棋棋盘上安排 8 个皇后，使得没有两个皇后能互相攻击？（如果两个皇后处在同一行、同一列或同一条对角线上，则她们能互相攻击。）

因为没有两个皇后能放在同一行或列上，则解向量必须是数 $1, 2, \dots, n$ 的一个排列。即一有 8 个分量的向量 $x={x_1, x_2, x_3, x_4,\dots}$ 来描述。$x_i$ 的值为棋盘上第 $i$ 行的皇后所处的列。

以4皇后问题为例，应该生成一颗完全四叉树，树的根对应于没有放置皇后的情况。第一层的节点对应于皇后在第一行的可能放置情况，第二层的节点对应于皇后在第二行的可能放置情况，依次类推。

Algorithm 4-QUEENS
输入：空。
输出：对应于 4 皇后问题的解的向量 x[1...4]。
1. for k ← 1 to 4
2.    x[k] ← 0 {棋盘上无皇后}
3. end for
4. flag ← false
5. k ← 1
6. while k ≥ 1
7.    while x[k] ≤ 3
8.       x[k] ← x[k] + 1    // 不断尝试第k个皇后能放置的位置
9.       if x 为原问题的合法解 then 
            flag ← true 且从两个 while 循环退出
10.      else if x 是部分解 then 
            k ← k + 1 {前进}
11.   end while
12.   x[k] ← 0
13.   k ← k - 1 {回溯}
14. end while
15. if flag then output x
16. else output “no solution”

回溯法最坏情况为 $n^n$。据经验它在有效性上远远超过蛮力方法的 $O(n!)$ 时间，作为它的可期望运行时间通常要快得多。

哈密尔顿回路 (Hamiltonian Circuit)

给定一个包含 $n$ 个顶点的连通图 $G = (V, E)$。
哈密尔顿回路（Hamiltonian Circuit，又称哈密尔顿圈）是指一条路径，它经过图中的每一个顶点恰好一次，并且最终回到出发点。

使用一个数组 x[0…n-1] 来记录路径。x[k] 表示路径中第 $k$ 个访问的顶点。

在为 x[k] 选择下一个顶点 v 时，必须满足以下两个条件，否则剪枝（回溯）：

顶点 x[k-1] 和 v 之间必须有边相连。
顶点 v 不能出现在当前的路径 x[0…k-1] 中。
当 k = n 时（所有顶点都已访问），检查最后一个顶点 x[n-1] 和起点 x[0] 之间是否有边。如果有，则找到了一条回路。

Algorithm Hamiltonian(k)
// 输入：图 G=(V, E)，当前路径深度 k
// 全局变量：解向量 x[0...n-1]，其中 x[0] 固定为起始点（如顶点 1）
1. 循环 v ← 2 到 n  // 尝试每一个可能的下一个顶点
2.    if (x[k-1], v) ∈ E AND v 不在 x[0...k-1] 中 then
3.        x[k] ← v    // 做出选择
4.        if k = n then
5.            if (x[n], x[0]) ∈ E then
6.                Output x[0...n] // 找到回路
7.                return // 找到一个解即可退出，若求所有解则 continue
8.        else
9.            Hamiltonian(k + 1) // 递归进入下一层
10.       x[k] ← 0    // 回溯：撤销选择
11.   end if
12. end loop

最坏时间复杂度：$O(n!)$。因为解空间是排列树，除了起点外，第一个位置有 $n-1$ 种选择，第二个有 $n-2$ 种… 总共约 $n!$ 个叶子节点。

3.2.3 一般回溯算法

一般回溯算法可以作为一种系统的搜索方法应用到一类搜索问题当中，这类问题的解由满足事先定义好的某个约束的向量 $(x_1, x_2, \dots, x_i)$ 组成。

PARTITION 问题变形

给定一个 $n$ 个整数的集合 $X = {x_1, x_2, \dots, x_n}$ 和整数 $y$，找出和等于 $y$ 的 $X$ 的子集 $Y$

解的布尔向量表示类似${1, 1, 1, 0, 0, 0}$。

假定算法已经找到部分解为 $(x1, x_2, \dots, x_j)$，然后再考虑向量 $v = (x_1, x_2, \dots, x_j, x{j+1})$，有下面的情况（解向量中每个 $x_i$ 都属于一个有限的线序集 $X_i$）

成功：如果 $v$ 表示问题的最后解，算法记录下它作为一个解，在仅希望获得一个解时终止，或者继续去找出其他解。
前进 (Forward)：如果 $v$ 表示一个部分解，算法通过选择集合 $X_{j+2}$ 中的第一个元素向前。
如果 $v$ 既不是最终的解，也不是部分解，则有两种子情况
- 如果从集合 $X{j+1}$ 中还有其他的元素可选择，算法将 $x{j+1}$ 置为 $X_{j+1}$ 中的下一个元素。
- 如果从集合 $X{j+1}$ 中没有更多的元素可选择，算法通过将 $x_j$ 置为 $X_j$ 中的下一个元素回溯；如果从集合 $X_j$ 中仍然没有其他的元素可以选择，算法通过将 $x{j-1}$ 置为 $X_{j-1}$ 中的下一个元素回溯，依次类推。

Algorithm BACKTRACKREC
输入：集合 X_1，X_2，…，X_n 的清楚的或隐含的描述。
输出：解向量 v = (x_1, x_2, …, x_i), i ≤ n。
1. v ← Φ
2. flag ← false
3. backrec(1)
4. if flag then output v
5. else output “no solution”

Procedure backrec (k)
1. for 每个 x ∈ X_k
2.    x_k ← x; 将 x_k 加入 v
3.    if v 为最终解 then set flag ← true and exit
4.    else if v 是部分解 then backrec(k + 1)
5. end for

3.3 分支定界法 (Branch and Bound)

在组合优化领域，决策问题通常分为判定性问题与最优化问题。以图着色问题（Graph Coloring Problem）为例：

判定问题：给定图 $G$，是否存在一种合法的 $N$ 着色方案（3-Coloring/N-Coloring）？
最优化问题：给定图 $G$，对其进行合法着色所需的最少颜色数量是多少？

分支定界法（Branch and Bound）是解决此类离散优化及整数规划（Integer Programming）问题的核心算法。它通过系统地枚举解空间，并利用界限信息来避免搜索无望的子空间（即剪枝），从而高效地寻找全局最优解。

3.3.1 从线性规划到整数规划

整数规划（Integer Programming）的数学模型建立在一般线性规划的基础之上，但增加了变量必须为整数的约束。

其通用形式如下：

目标函数（Objective Function）：

$Max(Min) \ z = c_1x_1 + c_2x_2 + \dots + c_nx_n$

约束条件（Constraints）：

$\begin{cases} a_{11}x_1 + a_{12}x_2 + \dots + a_{1n}x_n \le (=, \ge) \ b_1 \\ \dots \\ a_{m1}x_1 + a_{m2}x_2 + \dots + a_{mn}x_n \le (=, \ge) \ b_m \\ x_j \ge 0, \quad j=1, \dots, n \\ x_j \in \text{Integer} \quad (\text{整数约束}) \end{cases}$

例如，某厂需托运甲、乙两种货物，已知每箱的体积、重量限制及利润如下表所示：
| 货物名称 | 体积/箱 (Volume/Box) | 重量/箱 (Weight/Box) | 利润/箱 (Profit/Box) |
| :—- | :—-: | :—-: | :—-: |
| 甲 ($x_1$) | 9 | 7 | 40 |
| 乙 ($x_2$) | 7 | 20 | 90 |
| 托运限制 (Constraints) | 56 | 70 | 目标函数 (Max $z$) |

对应的整数规划形式为：

$Max \ z = 40x_1 + 90x_2 \quad (1)$

以及约束：

$\begin{cases} 9x_1 + 7x_2 \le 56 \quad (2) \\ 7x_1 + 20x_2 \le 70 \quad (3) \\ x_1, x_2 \ge 0 \quad (4) \\ x_1, x_2 \in \text{Integer} \quad (5) \end{cases}$

3.3.2 分支定界法

使用分支定界法解决整数规划问题

步骤一：松弛求解（Relaxation）首先暂时忽略整数约束（条件5），求解对应的线性规划问题

解（$R_1$）：$x_1 = 4.809, x_2 = 1.817, z = 355.890$，此解非整数，需进行分支。

步骤二：分支（Branching）
任选一个非整数变量（如 $x_1=4.809$），将其分为两个互斥的子问题：

分支 1：$x_1 \le 4$
分支 2：$x_1 \ge 5$

步骤三：迭代求解子问题

在 $R_1$ 基础上增加 $x_1 \le 4$约束
- 结果：$x_1 = 4.000, x_2 = 2.100, z = 349.000$
- 状态：$x_2$ 仍非整数，需继续对 $R_2$ 进行分支（$x_2 \le 2$ 或 $x_2 \ge 3$）。
在 $R_1$ 基础上增加 $x_1 \ge 5$
- 结果：$x_1 = 5.000, x_2 = 1.571, z = 341.390$
- 状态：$x_2$ 非整数，需继续分支。

步骤四：深入分支与剪枝（Pruning）
继续对 $R_2$ 进行分支：

$x_1 \le 4$ 且 $x_2 \le 2$
- 结果：$x_1 = 4.000, x_2 = 2.000, z = 340$
- 状态：获得可行整数解。此时 $z=340$ 成为当前最优解的下界。
$x_1 \le 4$ 且 $x_2 \ge 3$
- 结果：$x_1 = 1.428, x_2 = 3.000, z = 327.120$
- 状态：虽然可能有整数解，但其上限 $327.12$ 小于已有的最优解 $340$，故该分支被剪枝。
$x_1 \ge 5$ 且 $x_2 \le 1$
- 结果：$x_1 = 5.444, x_2 = 1.000, z = 307.760$
- 状态：目标值 $307.76 < 340$，剪枝。
$x_1 \ge 5$ 且 $x_2 \ge 2$
- 结果：无可行解（Infeasible）。

结论：最终最优整数解为 $x_1=4, x_2=2$，最大利润 $z=340$。

关于求解线性规划
线性规划的基本定理告诉我们：最优解一定出现在可行域的顶点上，也就是约束边界直线的交点上。
因此我们直接计算下式的解：
$\begin{cases} 9x_1 + 7x_2 = 56 \quad (\text{式A}) \\ 7x_1 + 20x_2 = 70 \quad (\text{式B}) \end{cases}$
即可得到x1,x2和z
再增加约束后，们需要看这条新线与哪条旧线相交构成了新的“最右上角[两个变量越大，利润越高，因此是右上角]”
如果 $x_1 = 4$，代入约束 1 ($9x_1 + 7x_2 = 56$)：
$36 + 7x_2 = 56 \implies 7x_2 = 20 \implies x_2 \approx 2.857$
如果 $x_1 = 4$，代入约束 2 ($7x_1 + 20x_2 = 70$)：
$28 + 20x_2 = 70 \implies 20x_2 = 42 \implies x_2 = \mathbf{2.1}$
因为 $2.1 < 2.857$，说明在 $x_1=4$ 这条线上，约束 2 更紧。
新的最优顶点是直线 $x_1=4$ 与直线 $7x_1 + 20x_2 = 70$ 的交点。

分支定界法算法

一般步骤

初始化：将原整数规划问题设为 A，对应的松弛线性规划问题设为 B。
求解松弛问题：若 B 无解，则 A 无解；若 B 的最优解符合整数条件，则该解即为 A 的最优解。
分支（Branching）：若 B 的解中有变量 $x_j=b_j$ 不符合整数条件，构造两个后继问题，分别添加约束：
- $x_j \le \lfloor b_j \rfloor$ （小于 $b_j$ 的最大整数）
- $x_j \ge \lceil b_j \rceil$ （大于 $b_j$ 的最小整数）
定界与选择：在所有待处理的子问题中，选择目标函数最优的节点继续分支。
剪枝（Pruning）：若某分支的最优可能值（边界）劣于当前已知的最佳整数解，则放弃该分支。

关键概念

可行解/不可行解（Feasible/Infeasible Solution）：满足约束条件的解。
部分解（Partial Solution）：决策树中非叶子节点的解。
最优解（Optimal Solution）：目标函数值达到极值的可行解。
遍历（Traverse）与回溯（Backtracking）：在解空间树中的搜索移动方式。
搜索策略：深度优先搜索（DFS）、广度优先搜索（BFS）、前沿搜索（Frontier Search）。

分支定界法的效率依赖于界限的计算与更新。该方法比单纯的回溯法增加了两个核心条件：

计算子树目标函数值的边界的方法。
记录目前求得的最佳解。

特性	回溯法 (Backtracking)	分支定界法 (Branch and Bound)

| :

3.3.2 简单示例

0/1背包问题

我们使用线性松弛方法，计算每条路径的上界，即假设物品可以切分，填满背包所能达到的理论最大价值。

例如，

Item 1: $w=4, v=40$ (密度 10)
Item 2: $w=7, v=42$ (密度 6)
Item 3: $w=5, v=25$ (密度 5)
Item 4: $w=3, v=12$ (密度 4)

计算上界：$UB = 40 + 6 \times (\text{Item 2 密度}) = 40 + 6 \times 6 = 76$

分支 1：装入 Item 1 (左节点 $x_1=1$)

计算上界：$UB = 40 + 6 \times 6 = 76$。
分支 2：不装入 Item 1 (右节点 $x_1=0$)
计算上界：$UB = 42 + 3 \times 5 = 57$。
左节点潜力 (76) > 右节点潜力 (57)。我们优先探索左节点。
分支 1-1：装入 Item 2 (左-左节点 $x_2=1$)
$11 > 10$ (超重)，剪枝。
分支 1-2：不装入 Item 2 (左-右节点 $x_2=0$)
计算上界：$UB = 40 + 25 + 1 \times 4 = 69$
整数解：$Z_{best} = 65$
分支 2 (右节点，不装 Item 1)
上界小于最优解，剪枝
得到最优解为65

TSP旅行商问题

分支通常是选择某条边 $(i, j)$ 是“包含在路径中”还是“不包含”，通常计算下界。

无向图 TSP：1-Tree 下界
将每个城市 $i$ 的“最短两条边之和”加起来除以 2。
假设我们在树的一个节点，决定了“必须走边 $(A, D)$”，则必须选取边 $(A, D)$ 的权重，哪怕它不是 $A$ 连接的最短边。然后再选一条除 $(A,D)$ 外最短的边，同理计算 $D$ 的 $s_D$。

有向图 TSP：矩阵规约法
这是处理非对称 TSP（如 $A \to B$ 和 $B \to A$ 距离不同）的经典方法。

TSP 路径在距离矩阵中对应着：每一行选一个数，每一列选一个数。
如果我们将矩阵的某一行所有元素都减去同一个常数 $k$，路径的总长度减少 $k$，但相对的最优路径不变。

行规约：遍历每一行，找到该行的最小值 $min_i$，该行所有元素减去 $min_i$，使得该行至少有一个 0。
- $LB \leftarrow LB + \sum min_i$
列规约：在行规约后的矩阵基础上，遍历每一列，找到该列最小值 $min_j$，该列所有元素减去 $min_j$。
- $LB \leftarrow LB + \sum min_j$

在选择时，基于最大遗憾，即如果不选它，代价最大

找到矩阵中所有的 0 元素
对于每个 0 元素 $(i, j)$，计算它的遗憾值 = (第 $i$ 行次小值) + (第 $j$ 列次小值)
选择遗憾值最大的那个 $(i, j)$ 进行分支

分支 1：包含边 $(i, j)$

删除第 $i$ 行和第 $j$ 列
将 $(j, i)$ 设为 $\infty$
对剩下的矩阵再次进行行/列规约
该分支新 $LB$ = 旧 $LB$ + 新的规约值

分支 2：不包含边 $(i, j)$

将矩阵元素 $M[i][j]$ 设为 $\infty$
对矩阵再次进行行/列规约
该分支新 $LB$ = 旧 $LB$ + 新的规约值

3.3.3 指派问题和匈牙利算法

指派问题

假设存在 $n$ 项任务需由 $n$ 个代理（人或机器）完成，且任务与代理之间一一对应。由于各代理的专长不同，完成不同任务的效率（或成本、时间）存在差异。

效率矩阵：定义矩阵 $C = (c{ij}){n \times n}$，其中元素 $c_{ij} > 0$ 表示第 $i$ 个代理完成第 $j$ 项任务的成本。

引入 0-1 变量 $x_{ij}$：

$x_{ij} = \begin{cases} 1, & \text{若指派第 } i \text{ 人完成第 } j \text{ 项任务} \\ 0, & \text{否则} \end{cases}$

数学表达为：

$\min z = \sum_{i=1}^{n} \sum_{j=1}^{n} c_{ij} x_{ij}$ $\text{s.t.} \begin{cases} \sum_{j=1}^{n} x_{ij} = 1, & i=1, 2, \dots, n \quad (\text{每个人只能完成一项任务}) \\ \sum_{i=1}^{n} x_{ij} = 1, & j=1, 2, \dots, n \quad (\text{每项任务只能由一人完成}) \\ x_{ij} \in \{0, 1\} \end{cases}$

已发现，这个表达式与TSP问题很像，唯一不同的是TSP解要求形成一个包含所有节点的大环，指派问题按照TSP的形式，是允许小环出现的。相差的约束就是MTZ 约束 (Miller-Tucker-Zemlin formulation)，它使得无法形成任何不包含起点的闭环。同时也是没有这个约束，匈牙利算法可以以多项式速度解决指派问题。

匈牙利算法

如上所述，指派问题的下界也可以通过矩阵规约方法求解。但在匈牙利算法中，矩阵规约知乎不使用最大遗憾值之类的选择方法，而是寻找最小直线覆盖：通过最少数量的直线覆盖矩阵中所有的 0。

从含 0 最少的行开始，标记一个 0（记为 ◎），并划去同行同列的其他 0（记为 Ø）。若能找到 $n$ 个 ◎，则对应 $x_{ij}=1$ 的解即为最优解，此时目标函数值 $z_b=0$。
对没有 ◎ 的行打 √，对打 √ 行中所有含 0 的列打 √，对打 √ 列中含 ◎ 的行打 √
对没有打 √ 的行画横线，对打 √ 的列画纵线。
然后进行矩阵变换，旨在增加独立零元素的数量
在未被直线覆盖的区域中找出最小元素 $k$。
对所有未被直线覆盖的行元素减去 $k$。对所有被直线覆盖的列元素加上 $k$。（也就是所有打√ 的部分）
直线交叉处的元素值增加 $k$，未覆盖处减小 $k$，单线覆盖处不变。此变换确保产生了新的 0 元素。
转回步骤 2 重复进行，直至找到最优解。

例如以下矩阵：

$C = \begin{bmatrix} 12 & 7 & 9 & 7 & 9 \\ 8 & 9 & 6 & 6 & 6 \\ 7 & 17 & 12 & 14 & 12 \\ 15 & 14 & 6 & 6 & 10 \\ 4 & 10 & 7 & 10 & 6 \end{bmatrix}$

行规约

$\begin{bmatrix} 5 & \mathbf{0} & 2 & \mathbf{0} & 2 \\ 2 & 3 & \mathbf{0} & \mathbf{0} & \mathbf{0} \\ \mathbf{0} & 10 & 5 & 7 & 5 \\ 9 & 8 & \mathbf{0} & \mathbf{0} & 4 \\ \mathbf{0} & 6 & 3 & 6 & 2 \end{bmatrix} \begin{matrix} \leftarrow \text{减 } 7 \\ \leftarrow \text{减 } 6 \\ \leftarrow \text{减 } 7 \\ \leftarrow \text{减 } 6 \\ \leftarrow \text{减 } 4 \end{matrix}$

列规约：矩阵没有变化，因为每列都已经包含了至少一个 0。

分配独立零元素

R3 只有一个 0 $\to$ 选 $(3,1)$。列1 的其他 0 划掉（$(5,1)$ 变为 Ø）。
R1 有两个 0，选 $(1,2)$。
R4 有两个 0，选 $(4,3)$。列3 的其他 0 划掉（$(2,3)$ 变为 Ø）。行4 的其他 0 划掉（$(4,4)$ 变为 Ø）。
R2 剩下 $(2,4)$ 和 $(2,5)$。选 $(2,4)$。行2 的其他 0 划掉（$(2,5)$ 变为 Ø）。
R5 原本的 $(5,1)$ 被 R3 占了，R5 没有可用的 0。

$\begin{bmatrix} 5 & ◎ & 2 & 0 & 2 \\ 2 & 3 & Ø & ◎ & Ø \\ ◎ & 10 & 5 & 7 & 5 \\ 9 & 8 & ◎ & Ø & 4 \\ Ø & 6 & 3 & 6 & 2 \end{bmatrix}$

只有 4 个独立零元素（$N=4 < 5$），不是最优解。需要进行最小直线覆盖。

对没有 ◎ 的行打 √：Row 5 没有分配任务 $\to$ √ Row 5
对打 √ 行中所有含 0 的列打 √：Row 5 在 Col 1 有个 0（虽然被划掉了，仍算 0 元素）$\to$ √ Col 1
对打 √ 列中含 ◎ 的行打 √：Col 1 的 ◎ 在 Row 3 $\to$ √ Row 3
继续循环：Row 3 的 0 在 Col 1（已勾），无新列。停止
画横线：没有打 √ 的行 $\to$ Row 1, Row 2, Row 4。画纵线：打 √ 的列 $\to$ Col 1。 $\begin{array}{c|ccccc} & \mathbf{L} & & & & \\ \hline \mathbf{L} & 5 & 0 & 2 & 0 & 2 \\ \mathbf{L} & 2 & 3 & 0 & 0 & 0 \\ & 0 & 10 & 5 & 7 & 5 \\ \mathbf{L} & 9 & 8 & 0 & 0 & 4 \\ & 0 & 6 & 3 & 6 & 2 \end{array}$

找出未被覆盖区域的最小元素 $k$ $k = 2$

未覆盖元素（R3, R5 的后四列）：减去 $2$
单线覆盖元素（不变）
双线交叉点（R1, R2, R4 与 C1 的交点）：加上 $2$。
$\begin{bmatrix} 5\mathbf{+2} & 0 & 2 & 0 & 2 \\ 2\mathbf{+2} & 3 & 0 & 0 & 0 \\ 0 & 10\mathbf{-2} & 5\mathbf{-2} & 7\mathbf{-2} & 5\mathbf{-2} \\ 9\mathbf{+2} & 8 & 0 & 0 & 4 \\ 0 & 6\mathbf{-2} & 3\mathbf{-2} & 6\mathbf{-2} & 2\mathbf{-2} \end{bmatrix} \rightarrow \begin{bmatrix} 7 & \mathbf{0} & 2 & \mathbf{0} & 2 \\ 4 & 3 & \mathbf{0} & \mathbf{0} & \mathbf{0} \\ \mathbf{0} & 8 & 3 & 5 & 3 \\ 11 & 8 & \mathbf{0} & \mathbf{0} & 4 \\ \mathbf{0} & 4 & 1 & 4 & \mathbf{0} \end{bmatrix}$

再次进行最优解试探：

$\begin{bmatrix} 7 & ◎ & 2 & 0 & 2 \\ 4 & 3 & 0 & ◎ & Ø \\ ◎ & 8 & 3 & 5 & 3 \\ 11 & 8 & ◎ & Ø & 4 \\ Ø & 4 & 1 & 4 & ◎ \end{bmatrix}$

回到原始矩阵查找成本，最小总成本 = $7 + 6 + 7 + 6 + 6 = \mathbf{32}$。

对于最大化指派问题，使用 $b{ij} = M - c{ij}$将其转化为最小化问题。

3.3.4 最小耗费网络流设计

在给定节点集合中，构建一个满足所有流量需求且总耗费最小的网络结构。

设 $G$ 为 $n$ 个节点上所有无向图的集合。任意图 $G \in \mathcal{G}$ 可由邻接矩阵 $B$（上三角部分）表示，元素 $b_{ij}$ 描述连接状态。

任意源-目的节点对 $(O-D)$ 间存在需传输的数据量 $d_{ij}$。
每条边 $(i,j)$ 存在最大负载限制 $k_{ij}$。
建立边 $(i,j)$ 的花费为 $c_{ij}$。

寻找最优子图 $G^* \in \mathcal{G}$，即在满足所有边容量限制 $k{ij}$ 的前提下，承载所有 $d{ij}$ 流量，并使得网络建设总成本最小。

引入 0-1 变量 $x_{ij}$：

$x_{ij} = \begin{cases} 1, & \text{若边 } (i,j) \text{ 被选中构建} \\ 0, & \text{若边 } (i,j) \text{ 未被选中} \end{cases}$

这是我们之前的最小费用通信网络的扩展。之前我们使用各种方式生成了该图的情况下的最小生成树，现在的问题只是在之前的问题上增加了流量和容量两个约束。

假设候选边数为m个，定义二叉搜索树为m层，每一层对应一条边的候选决策：

左分支 (Left Branch)：代表 $x_{ij}=1$，即选择该边加入网络。
右分支 (Right Branch)：代表 $x_{ij}=0$，即放弃该边。

从根节点 (Vertex 1) 开始，在下行扩展时，总是优先选择左分支，尝试加入边。当发生以下任一情况时，停止当前路径并回溯：

当前选择的边组合无法满足约束（如不连通或容量溢出）
已找到一个满足条件的可行解
触发定界条件

定界条件与我们之前的设置相同，为最小成本的下界，即UB = Cost(已经选择的边)+minCost(连接剩下所有节点)。一种方法是按照之前的旅行商问题的下界定义。更好的方法是受限最小生成树问题，称为SMST算法，因为主要考虑边的问题，所以使用Kruskal算法。

回忆Kruskal算法，这是一种维护不相交集合的算法。每一步选择合法的最短边，并合并该边连接的两个集合。

算法有一个显著的弱点，若位于搜索树上层（较早被决策）的某条边容量很小，算法可能会在深层搜索很久后才发现其导致的容量溢出。我们引入容量约束违背预测

这种预测利用最大流最小割定理的一个推论：

网络中任意一个“割”（将网络切成两部分的划分），其割边的总容量必须大于等于跨越该割的总流量需求。

即在 Kruskal 算法的某一步，我们考虑选择边 $(u, v)$ 来连接两个原本独立的连通分量（集合）$S1$ 和 $S_2$，计算必须跨越 $S_1$ 和 $S_2$ 之间的总流量需求 $D{cross}$：

$D_{cross} = \sum_{i \in S_1, j \in S_2} (d_{ij} + d_{ji})$

即：所有源点在 $S_1$、终点在 $S_2$（或反之）的数据流总和。

然后计算当前割容量，在当前的决策分支中，我们要看连接 $S1$ 和 $S_2$ 的边一共有哪些，在标准Kruskal算法中通常只有准备连接的一条边：$K{cut} = k_{uv}$。

判断是否满足$K{cut} < D{cross}$，如果成立（容量不足）：说明仅靠当前这条边（以及已选的边），物理上无法承载两个集合间的通信需求。

但是，直接说明这种选择不可行也是不合理的。引入强制增边：为了满足 D{cross} 的需求，我们必须从 $S_1$ 和 $S_2$ 之间的候选边集合中，继续寻找次便宜的边 $e_2, e_3…$，直到它们的总容量 $\sum k \ge D{cross}$。如此，这个分支的成本下界提高，如果超过了上界，则立即剪枝。

另一种下界改进方式被称为未来流量界。简单来说，容量约束违背预测算的是准备连接的这条链路可能的额外成本。

未来流量界考察目前所有未被连通的子树，也就是Kruskal算法中的不交叉集合。为了让这些子树可以互通，未来至少要引入一些链路，这些链路的成本为Y。将Y加入LB公式中，可以让下界进一步精确。

改进还包括链路度，这种方法提前计算每条链路可车挂载的最大节点数。在计算SMST算法中，由于有生成树约束，系统无环，可以用这一点快速检查是否满足容量要求。

除此之外可以做的优化包括：

把所有边从便宜到贵排序
在分支定界算法运行前，先运行一个修正版的Prim算法生成一颗满足单一约束（比如容量约束）的最小生成树。然后将这个成本作为上界，避免算法早期的盲目搜索

3.4 贪心算法 (Greedy Algorithms)

贪心算法是一种“非回溯算法”，其特征在于基于局部信息做出具有全局意义的、不可撤销的决策。

3.4.1 贪心算法

个有效的贪心策略必须严格满足以下三要素：

可行性 (Feasible)：每一步所做的选择必须严格满足问题的约束条件。
局部最优 (Locally Optimal)：在当前步骤的所有可行选择中，选取局部最佳方案。
不可取消性 (Irrevocable)：选择一旦做出，在算法的后续步骤中无法更改或撤销。

此类算法通常易于设计，且因其线性或线性对数级的时间复杂度，易于分析运行效率。然而，其主要挑战在于正确性证明，即证明一系列局部最优选择最终能收敛至全局最优解。

3.4.2 区间调度问题和区间划分问题

区间调度问题

已知包含 $n$ 项任务的集合 $S={1, 2, \dots, n}$，每项任务 $i$ 拥有固定的开始时间 $s_i$ 和结束时间 $f_i$。任务 $i$ 与 $j$ 相容，当且仅当 $s_i \ge f_j$ 或 $s_j \ge f_i$（即时间区间不重叠）。

寻找一个基数最大的两两相容的任务子集 $A$。

优先选择结束时间最早的任务，能够尽早释放资源，从而为后续任务保留最大的时间余量。因此优先选择结束时间早的废。

将所有任务按结束时间 $f_i$ 进行非递减排序。
初始化 $A$ 为空，遍历排序后的任务序列。
设 $j$ 为上一个加入 $A$ 的任务。对于当前任务 $i$，若 $s_i \ge f_j$（即与已选集合相容），则将 $i$ 加入 $A$。

这个算法的时间消耗在于排序，总的时间复杂度为$O(n \log n)$

证明贪心算法返回的任务集合 $A$ 是最优的。

假设贪心算法生成的解为 $A = {i_1, i_2, \dots, i_k}$（按添加顺序），最优解为 $O = {j_1, j_2, \dots, j_m}$。显然 $m \ge k$。我们只需证明 $m=k$。

易证贪心解在每一步都“领先”或不落后于最优解。即证明对于任意 $r \le k$，有 $f{i_r} \le f{j_r}$。

假设贪心解不是最优的，即 $m > k$。根据上述结论，有 $f{i_k} \le f{jk}$。
考虑最优解中的第 $k+1$ 个任务 $j{k+1}$。由定义知 $s{j{k+1}} \ge f{j_k}$。
因此 $s{j{k+1}} \ge f{jk} \ge f{ik}$。这意味着 $j{k+1}$ 与贪心解集 $A$ 相容。然而，贪心算法会在 $ik$ 处停止，说明后续没有相容任务。这与存在 $j{k+1}$ 相矛盾。
故假设不成立，必须有 $m=k$，即贪心解即为最优解。

扩展：加权区间调度问题
当引入权重因素，即每个任务具有权重 $w_i$，目标变为寻找总权重最大的相容子集时。

这个问题要用动态规划方法做。

一种思路是维护一个T(结束时间f，i)的记录在结束时间为f时，前i个任务可以达到的最大权重。实际上，结束时间的维度一般与i同规模。这个算法的时间复杂度为$O(n^2)$

更简单的算法是首先将任务按照结束时间排序，在进行动态规划前维护一个数组，记录每个任务的前驱任务，即与 $j$ 相容的任务的最大索引。

由此，递推公式为：

$OPT(j) = \max \begin{cases} w_j + OPT(p(j)) & \text{(选择任务 } j\text{)} \\ OPT(j-1) & \text{(不选任务 } j\text{)} \end{cases}$

算法的时间复杂度下降到 $O(n \log n)$。

区间划分问题

包含 $n$ 门课程的集合，每门课 $j$ 具有固定的开始时间 $s_j$ 和结束时间 $f_j$。寻找最小数目的教室，使得所有课程均能被安排，且同一教室在同一时间仅能容纳一门课。

策略：按开始时间 $s_j$ 对所有课程进行排序。

初始化教室集合为空。
遍历排序后的课程。对于当前课程 $j$，检查现有教室中是否有一间是空闲的（即该教室上一门课的结束时间 $\le s_j$）。
若有兼容教室，将课程 $j$ 安排进去（更新该教室的结束时间）。
若无兼容教室，开启一间新教室并安排课程 $j$。

算法使用优先队列 (Priority Queue) 维护所有教室最后加入课程的完成时间（最小堆），排序耗时 $O(n \log n)$，优先队列操作耗时 $O(n \log n)$，总计 $O(n \log n)$

证明上述贪心算法使用的教室数目等于区间集合的深度 $d$，即该算法能找到最小数目的教室。

假设算法最终开启了 $d$ 间教室。
考虑当第 $d$ 间教室被开启的时刻，意味着待安排的课程 $j$ 与前面 $d-1$ 间教室中正在进行的课程均不相容（即存在重叠）。
这表明在 $s_j$ 这一时刻，包括课程 $j$ 在内，共有 $d$ 门课程同时进行。
根据深度的定义，此时区间集合的深度至少为 $d$。
结合下界性质（$Classrooms \ge Depth$），可知算法所用的教室数 $d$ 恰好等于深度下界，因此是最优解。

3.4.3 最小延迟调度问题

输入：单个处理资源，处理 $n$ 个任务。每个任务 $j$ 包含处理时长 $t_j$ 和截止时间 $d_j$。

$s_j$：任务开始时间。
$f_j = s_j + t_j$：任务完成时间。延迟 (Lateness)：
$lj = \max{0, f_j - d_j}$。
目标：最小化最大延迟 $L{\max} = \max_j l_j$。

$l_j = \max{0, s_j + t_j - d_j}$，为了保证最大延迟最小，应该保证对于第j的元素，$s_j$和$t_j$尽可能小，$d_j$尽可能大。这个问题是最早截止时间优先。

证明定理：按截止时间排序的贪心调度 $S$ 是最优的。

假设 $S^$ 是某一最优调度。我们将通过一系列不增加最大延迟的交换操作，将 $S^$ 转化为 $S$。

在调度 $S$ 中，若任务 $i$ 和 $j$ 满足 $d_i \le d_j$（即 $i$ 应该先做），但实际调度中 $j$ 排在 $i$ 之前，则称 $(i, j)$ 为一个逆序。
- 贪心调度 $S$ 中不存在任何逆序。若任何其他调度包含逆序，必存在一对相邻的逆序任务。
假设在调度中存在相邻的逆序任务 $j$ 和 $i$（$j$ 在前，但 $d_i < d_j$）。交换二者的顺序后，新调度的最大延迟不会增加。
- 假设在调度中存在相邻的逆序任务 $j$ 和 $i$（$j$ 在前，但 $d_i < d_j$）。交换二者的顺序后，新调度的最大延迟不会增加。
- 任务 $i$ (交换后提前)：完成时间变早，延迟 $l’_i \le l_i$，不会变差。
- 任务 $j$ (交换后推迟)：
  交换后 $j$ 的新完成时间 $f’_j$ 等于交换前 $i$ 的完成时间 $f_i$。
  新延迟 $l’_j = f’_j - d_j = f_i - d_j$。
  由于存在逆序 $d_i < d_j$，故 $-d_j < -d_i$。
  所以 $l’_j < f_i - d_i = l_i$。
  这表明，$j$ 的新延迟甚至不超过交换前 $i$ 的延迟。
交换后的局部最大延迟 $\max(l’_i, l’_j) \le l_i$，即总体的最大延迟不会恶化。
最优调度 $S^$ 中最多存在 $C_n^2$ 个逆序。通过反复交换相邻逆序对，可以将 $S^$ 转化为没有任何逆序的调度（即贪心调度 $S$），且整个过程最大延迟非增。因此，$S$ 也是最优的。

若任务引入释放时间 $rj$（即任务不能早于 $r_j$ 开始），并要求判断是否存在调度使得所有任务均无延迟（$L{\max}=0$）。该问题是 NP-完全 (NP-Complete) 问题，目前尚未发现多项式时间算法

3.4.4 理论基础：拟阵 (Matroids)

拟阵

一个拟阵定义为有序对 $M = (S, I)$，需满足以下三个条件

$S$ 是一个非空的有限集合。
$I$ 是 $S$ 的子集构成的非空族（这些子集称为独立子集）。若 $B \in I$ 且 $A \subseteq B$，则 $A \in I$。（即独立集的任意子集仍是独立的）。
若 $A, B \in I$ 且 $|A| < |B|$，则必存在元素 $x \in B - A$，使得 $A \cup {x} \in I$。

例如：

矩阵拟阵
- ：给定实数域上的矩阵 $T$。令 $S$ 为 $T$ 的列向量集合，$I$ 为所有线性无关的列向量子集
- $(S, I)$ 构成一个拟阵，其性质直接对应向量空间中的线性无关性。
图拟阵
- 给定无向图 $G = (V, E)$。令 $S_G$ 为边集 $E$，$I_G$ 为无环边集的族（即森林）。则 $M_G = (S_G, I_G)$ 构成一个拟阵。

核心性质

扩展与基：

扩展：给定独立子集 $A \in I$，若存在 $x \notin A$ 使得 $A \cup {x} \in I$，则称 $x$ 为 $A$ 的一个扩展。
若独立子集 $A$ 不存在任何扩展，则称 $A$ 为拟阵的基。
定理 1：拟阵 $M$ 中所有极大独立子集（基）具有相同的大小
在图拟阵中，极大独立子集即为图的生成树（Spanning Tree），其边数恒为 $|V|-1$。

加权拟阵

若拟阵 $M=(S, I)$ 关联一个权函数 $w$，使得对任意 $x \in S$ 有 $w(x) > 0$，则称其为加权拟阵。
子集 $A$ 的权值定义为元素权值之和：$w(A) = \sum_{x \in A} w(x)$。
具有最大权值的独立子集是最优子集。由于权值为正，最优子集必然也是极大独立子集。

拟阵上的通用贪心算法

给定一个具有正权函数 $w$ 的加权拟阵 $M = (S, I)$，寻找 $S$ 的一个独立子集 $A \in I$，使得其总权值 $w(A)$ 最大。称 $A$ 为拟阵 $M$ 的最优子集 (Optimal Subset)。

由于所有元素的权值 $w(x)$ 均为正数，最优子集必然也是一个极大独立子集（即不存在可扩展元素）。

存在通用贪心算法：

Algorithm GREEDY(M, w)
输入：具有正权函数 w 的加权拟阵 M = (S, I)
输出：M 的最优子集 A
1.  A ← ∅
2.  将 S 中的元素按权值 w 单调递减排序
3.  for each x ∈ S  do
4.      if A ∪ {x} ∈ I then    // 独立性检查
5.          A ← A ∪ {x}
6.      end if
7.  end for
8.  return A

即满足条件的从大到小向A中加入S中的元素即可得到最优子集。

算法正确性证明

定理 2：如果 $M=(S, I)$ 是具有正权函数 $w$ 的加权拟阵，则调用 GREEDY(M, w) 必定返回一个最优子集。

引理 1：贪心选择性质 (Greedy Choice Property)

设 $M=(S, I)$ 是加权拟阵，元素已按权值降序排列。设 $x \in S$ 是第一个使得 ${x}$ 为独立子集的元素，则存在 $S$ 的一个最优子集 $A$ 包含 $x$。
- 若不存在这样的 $x$，则定理显然成立。
- 设 $B$ 是任意一个非空的最优子集。
  - 若 $x \in B$，则令 $A=B$，定理得证。
  - 若 $x \notin B$：
    - 由于 $x$ 是第一个单元素独立集，且 $B$ 中的任意元素 $y$ 构成的单元素集 ${y}$ 均独立（遗传性质），故 $w(x) \ge w(y), \forall y \in B$。
    - 构造包含 $x$ 的最优解：设初始 $A={x}$。若 $|B| > |A|$，反复利用交换性质，从 $B$ 中选择元素扩展 $A$，直到 $|A| = |B|$。
    - 在此过程中，必然存在一个元素 $y \in B$ 且 $y \notin A$，使得 $A = (B - {y}) \cup {x}$ 且 $A \in I$。
    - 计算权值：$w(A) = w(B) - w(y) + w(x)$。
    - 因 $w(x) \ge w(y)$，故 $w(A) \ge w(B)$。又因 $B$ 是最优子集，故 $w(A) = w(B)$。
    - 结论：$A$ 也是一个最优子集，且 $x \in A$。

引理 2：元素的不可撤销性

若 $S$ 中元素 $x$ 不是空集 $\emptyset$ 的可扩展元素（即 ${x} \notin I$），则 $x$ 不可能是 $S$ 中任一独立子集 $A$ 的可扩展元素。
- 假设 $x$ 不是 $\emptyset$ 的扩展（即 ${x}$ 相关），但存在独立子集 $A$ 使得 $A \cup {x} \in I$。根据遗传性质，$A \cup {x}$ 的子集 ${x}$ 必须是独立的。这与假设矛盾。
- 算法在初始化阶段或后续步骤中被判定为“不可加入”并舍弃的元素，可以被永久安全地丢弃，不会影响最优解的构造。

引理 3：最优子结构性质

设 $x$ 是贪心算法选中的第一个元素。原问题可简化为求解收缩拟阵 (Contraction Matroid) $M’ = (S’, I’)$ 的最优子集问题。
- $S’ = {y \in S \mid {x, y} \in I}$（即 $y$ 是 ${x}$ 的可扩展元素）。
- $I’ = {B \subseteq S-{x} \mid B \cup {x} \in I}$。
- $M’$ 的权函数是 $M$ 在 $S’$ 上的限制。
$M$ 中包含 $x$ 的最优子集，由 ${x}$ 与 $M’$ 的最优子集并集构成。

基于上述三个引理，我们可以归纳证明 GREEDY 算法的正确性：

第一步选择：由引理 1，算法选中的第一个元素 $x$ 必然属于某个最优子集。
舍弃安全：由引理 2，算法舍弃的元素永远不会被最优解需要。
递归结构：由引理 3，选中 $x$ 后，剩余问题转化为在收缩拟阵 $M’$ 上寻找最优子集。
由于每一步选择都是安全的（包含在最优解中），且问题规模不断缩小但结构不变，归纳可得算法最终输出的集合 $A$ 即为全局最优子集。

最小生成树问题

我们已经多次提到最小生成树问题旨在寻找无向连通图 $G=(V, E)$ 中权值和最小的生成树。虽然拟阵的通用贪心法通常用于求解最大权独立子集，但 MST 问题可以通过简单的权值变换适配该框架

令 $w_0$ 为足够大的常数，定义新权值 $w’(e) = w_0 - w(e) > 0$。（最大值变最小值）

Kruskal 算法完全对应于拟阵的通用贪心框架。它维护一个无环的边集（森林），即图拟阵中的独立集。

初始化独立集 $A = \emptyset$。
将所有边按权值从小到大排序。
依次考察每条边 $(u, v)$：若加入该边不形成回路（即保持独立性），则 $A \leftarrow A \cup {(u, v)}$。
从这个例子可以看出，通常我们不会得到拟阵中真正的I，A ∪ {x} ∈ I的一步通常对应独立性检查。

单位时间任务调度问题

输入：$n$ 个单位时间任务集合 $S = {a_1, \dots, a_n}$。

截止时间 $d_i$：任务 $i$ 期望在时间 $d_i$ 之前完成。
误时惩罚 $w_i$：若任务未按时完成，将招致 $w_i$ 的惩罚。

目标：寻找一个调度序列，使得总误时惩罚最小。
等价目标：寻找一个权值和最大的早任务 (Early Task) 集合（即按时完成的任务子集）。

为了应用贪心法，我们需要定义任务集上的拟阵结构。

任务子集 $A$ 被称为独立的，当且仅当存在一个调度方案，使得 $A$ 中所有任务均不误时（即都是早任务）。
子集 $A$ 是独立的，当且仅当对于任意时间 $t$，集合 $A$ 中截止时间不晚于 $t$ 的任务数量不超过 $t$。即：
$N_t(A) = |\{a_i \in A \mid d_i \le t\}\le t, \quad \text{for } t=1, 2, \dots, n$

证明有序对 $(S, I)$ 构成一个拟阵：

若任务集 $B$ 可按时完成，其子集 $A \subseteq B$ 显然也可按时完成
设 $A, B$ 为独立集且 $|B| > |A|$
- 设 $k$ 为满足 $N_t(B) \le N_t(A)$ 的最大时间点。由于 $|B| > |A|$，在时间 $n$ 时 $N_n(B) > N_n(A)$，故必然存在时间点 $k$ 使得 $k < n$
- 可以证明，在 $B$ 中存在一个截止时间为 $k+1$ 的任务 $x \notin A$，将其加入 $A$ 后，新的集合 $A’ = A \cup {x}$ 仍然满足独立性判据 $N_t(A’) \le t$。

该问题转化为在加权拟阵上求最大权独立子集

将所有任务按惩罚 $w_i$ 单调递减排序
初始化 $A = \emptyset$。依次考察每个任务 $x$：
- 对所有 $t$，是否 $N_t(A \cup {x}) \le t$
  - 若满足，则 $A \leftarrow A \cup {x}$（该任务被标记为按时完成）
  - 若不满足，则该任务必须被丢弃（标记为迟任务，接受惩罚）
将集合 $A$ 中的任务按截止时间递增排序（早任务优先形式）
将迟任务 ($S - A$) 随意安排在 $A$ 之后

实例：给定任务集，按惩罚 $w_i$ 排序后为 ${1(4,70), 2(2,60), 3(4,50), 4(3,40), 5(1,30), 6(4,20), 7(6,10)}$

加入 1, 2, 3, 4：均满足 $N_t \le t$，保留。
尝试加入 5 ($d_5=1$)：此时 $d=1$ 的任务有 ${1, 5}$，数量为 2，大于时间 1。违反独立性，舍弃 5。
尝试加入 6 ($d_6=4$)：加入后导致截止时间 $\le 4$ 的任务数超标。舍弃 6。
尝试加入 7 ($d_7=6$)：满足条件，保留。
最终最优解：$A = {1, 2, 3, 4, 7}$。