Data-Structure/Algorithm/Exam/6.md

第一部分：6.1 一般方法 (General Method)

1. 动态规划方法适用的问题特点

动态规划主要用于解决多阶段决策优化问题（也称组合优化问题）。这类问题具有以下特征：

• 多阶段决策结构：问题可以被分解为若干个相互联系的阶段，每一个阶段都需要作出决策，且第 i 阶段的决策仅依赖于该阶段当前的状态。

• 决策序列与解：当每个阶段的决策都确定后，问题就得到了一个完整的决策序列，进而计算出一个解。

• 目标明确：动态规划适用于求解最优解（最大值或最小值），因此问题描述中一定存在目标函数，旨在寻找最优解和最优决策序列。

2. 最优性原理 (Principle of Optimality)

由贝尔曼（Bellman）等人在20世纪50年代提出，是动态规划的核心基石：

• 定义：过程的最优决策序列具有如下性质：无论过程的初始状态和初始决策是什么，其余的决策都必须相对于初始决策所产生的状态构成一个最优决策序列。

• 状态转移模型：$S_{0} \xrightarrow{x_{1}} S_{1} \xrightarrow{x_{2}} S_{2} \xrightarrow{x_{3}} \dots S_{n}$。

• 最优子结构性质：最优性原理表明，如果原问题包含子问题，那么原问题的部分最优决策序列一定是其子问题的最优决策序列。满足最优性原理的问题即具有最优子结构性质。

• 课件思考题：

• 思考1：任意子问题的最优决策序列都是原问题的部分最优决策序列么？

• 思考2：最优性原理的逆否命题是什么？

最优性原理的证明思想（以0/1背包问题为例）

• 证明四步法：①确定最优决策序列的形式；②确定初始状态和初始决策；③确定初始决策所产生的状态；④证明其余决策相对于③是最优决策序列。

• 0/1背包问题形式化定义：对 n 个物品，容量为 M 的背包，物品只能整件装入（$x_i=1$）或不装入（$x_i=0$）。目标是极大化效益 $\sum_{1 \le i \le n} p_i x_i$，满足约束条件 $\sum_{1 \le i \le n} w_i x_i \le M$。问题可记为 $KNAP(1, n, M)$。

• 证明过程：

• 设 x_{1}, x_{2}, \dots, x_{n} 是原问题的最优决策序列。

• 若 $x_{1}=0$，则 x_{2}, x_{3}, \dots, x_{n} 必须相对于子问题 KNAP(2, n, M) 构成一个最优序列。如若不然，则 x_{1}, x_{2}, \dots, x_{n} 就不是原问题的最优序列。

• 若 $x_{1}=1$，则 x_{2}, x_{3}, \dots, x_{n} 必须是子问题 KNAP(2, n, M-w_{1}) 的最优序列。如若不然，必存在另一个0/1序列 z_{2}, z_{3}, \dots, z_{n} 满足 \sum w_{i}z_{i} \le M-w_{1} 且具有更大效益值 $\sum p_{i}z_{i} > \sum p_{i}x_{i}$。那么序列 x_{1}, z_{2}, z_{3}, \dots, z_{n} 对原问题 KNAP(1, n, M) 就会产生更大的总效益，与假设矛盾。

• 从而证明0/1背包问题满足最优性原理。

3. 递推关系式设计的两种基本方法

• 向前处理法 (Forward Approach)：从最后阶段开始，逐步向前递推。即根据 x_{i+1}, \dots, x_{n} 的那些最优决策序列来列出求取决策值的关系式。

• 0/1背包简化公式：设 $g_{j}(X) = KNAP(j+1, n, X)$，一般递推式为 $g_{j}(X) = \max{g_{j+1}(X), g_{j+1}(X-w_{j+1}) + p_{j+1}}$，边界为 X<0 时 $g_n(X)=-\infty$，X \ge 0 时 $g_n(X)=0$。

• 向后处理法 (Backward Approach)：从初始阶段开始，逐步向后递推。即根据 x_{1}, \dots, x_{i-1} 的那些最优决策序列来列出求取 x_{i} 决策值的关系式。

• 0/1背包简化公式：设 $f_{i}(X) = KNAP(1, i, X)$，一般递推式为 $f_{i}(X) = \max{f_{i-1}(X), f_{i-1}(X-w_{i}) + p_{i}}$，边界为 X<0 时 $f_0(X)=-\infty$延展，X \ge 0 时 $f_0(X)=0$。

4. 重叠子问题性质 (Overlapping Subproblems)

• 性质定义：在自顶向下递归求解原问题时，同一个子问题在不同的递归分支中被多次重复重用计算。

• 解决方案：放弃自顶向下的递归，采用自底向上迭代求解。重叠子问题越多，动态规划相比于穷举或单纯递归的效率优势就越明显。

5. 动态规划的核心设计思想

1. 证明多阶段决策问题满足最优性原理。

2. 设计递推关系式：精心设计函数表达形式（函数值代表最优解，参数集作为状态用来刻画问题规模、边界和约束条件），根据最优性原理确立原问题与子问题的对应关系。

3. 以自底向上方式设计程序：从最小的子问题开始迭代计算，直到扩至原问题规模。计算过程中利用备忘录（表格）和标记函数保存所有子问题的最优解和最优决策，重用时直接查表。

6. 动态规划的优缺点

• 优点：在思想上远优于蛮力穷举法，在实现方法和效率上优于单纯的递归法。

• 缺点：若子问题重叠程度低，时间复杂度改善不明显；同时，过大的空间需求（需要表格存储状态）往往成为导致算法效率低下的主要制约因素。

---

第二部分：6.2 多段图问题 (Multistage Graph)

1. 问题描述与特点

多段图 G=(V,E) 是一种特殊的有向图：

• 结点集 V 被划分成 k \ge 2 个互不相交的集合 $V_1, V_2, \dots, V_k$。其中 V_1 仅包含源点 $s$，V_k 仅包含汇点 $t$。

• 所有的边 \langle u, v \rangle \in E 必须满足：若 $u \in V_i$，则 v \in V_{i+1} （$1 \le i < k$），每条边均附有成本 $c(u,v)$。

• 问题目标：寻找一条从 s 到 t 的最小成本路径。

2. 最优性原理证明

设 s, v_{2}, v_{3}, \dots, v_{k-1}, t 是一条从 s 到 t 的最短路径，初始决策使系统进入状态 $v_{2}$。此时原问题的子问题即为求从 v_2 到 t 的最短路径。根据假设，原路径中后半段 v_{2}, v_{3}, \dots, v_{k-1}, t 必然是从 v_2 到 t 的最短路径。否则，若存在更短路径 $v_{2}, q_{3}, \dots, q_{k-1}, t$，则将其与 \langle s, v_2 \rangle 拼接，将产生一条比原假设更短的 s \to t 路径，引发矛盾。因此最优性原理成立。

3. 向前处理递推关系式与计算示例

设 COST(i, j) 表示从 V_i 段的结点 j 到汇点 t 的最小路径成本：

COST(i,j) = \min_{l \in V_{i+1}, \langle j,l \rangle \in E} \{c(j,l) + COST(i+1,l)\}

• 初值设定：在第 k-1 段，若 $\langle j, t \rangle \in E$，则 $COST(k-1, j) = c(j,t)$，否则为 $\infty$。

实例推导（图源见课件PPT）

课件中给出了一个5段图（结点1为 $s$，结点12为 $t$）：

• $V_4$阶段（自底向上起点）：

• COST(4,9) = c(9,12) = 4; COST(4,10) = c(10,12) = 2; $COST(4,11) = c(11,12) = 5$。

• $V_3$阶段：

• $COST(3,6) = \min{c(6,9)+4, c(6,10)+2} = \min{6+4, 5+2} = 7$。

• $COST(3,7) = \min{c(7,9)+4, c(7,10)+2} = \min{4+4, 3+2} = 5$。

• $COST(3,8) = \min{c(8,10)+2, c(8,11)+5} = \min{5+2, 6+5} = 7$。

• $V_2$阶段：

• $COST(2,2) = \min{c(2,6)+7, c(2,7)+5, c(2,8)+7} = \min{4+7, 2+5, 1+7} = 7$。

• 同理算得 $COST(2,3)=9$，$COST(2,4)=18$，$COST(2,5)=15$。

• $V_1$阶段（源点）：

• $COST(1,1) = \min{c(1,2)+7, c(1,3)+9, c(1,4)+18, c(1,5)+15} = \min{9+7, 7+9, 3+18, 2+15} = 16$。

空间优化技巧

对结点从源点开始统一进行单一编号（1到$n$），可以省去 COST(i,j) 和决策数组 D(i,j) 中的第一个表示段数的下标 $i$，将其压缩为一维数组存储。

向前处理算法伪代码 (FGRAPH)

procedure FGRAPH(E, k, n, P)
// P(1:k) 用来保存最终求得的最小成本路径上的结点编号
real COST(n); int D(n-1), P(k), r, j, k, n
COST(n) <- 0
for j <- n-1 to 1 by -1 do
    寻找一个邻接结点 r，满足 <j, r> ∈ E 且使 c(j, r) + COST(r) 最小
    COST(j) <- c(j, r) + COST(r);
    D(j) <- r;
repeat
P(1) <- 1; P(k) <- n
for j <- 2 to k-1 do 
    P(j) <- D(P(j-1)) 
repeat
end FGRAPH

• 复杂度：时间复杂度 $\Theta(n+e)$，空间复杂度 $\Theta(n+e)$（基于邻接表存储图 $G$）[cite: 1]。
• 根据标记函数回溯路径：$D(1)=2, D(2)=7, D(7)=10, D(10)=12$，最短路径为 $1 \to 2 \to 7 \to 10 \to 12$，总成本为 16[cite: 1]。

4. 向后处理递推关系式

设 BCOST(i, j) 表示从源点 s 到第 i 段结点 j 的最小路径成本[cite: 1]： $BCOST(i,j) = \min_{l \in V_{i-1}, \langle l,j \rangle \in E} \{BCOST(i-1,l) + c(l,j)\}$[cite: 1]

• 经过同样的递推与回溯，求得的最优路径方案为 $1 \to 3 \to 6 \to 10 \to 12$，总成本同样为 16[cite: 1]。

5. 典型应用：资源分配问题 (Resource Allocation)

• 问题描述：将 n 个相同的资源分配给 r 个项目，使得总净利润最大[cite: 1]。N(i, j) 表示把 j 个资源分配给项目 i 获得的利润[cite: 1]。
• 建模为多段图：构建一个 r+1 段图[cite: 1]。结点 V(i, j) 表示把 j 个资源总共分配给了前 i-1 个项目[cite: 1]。有向边 \langle V(i,j), V(i+1,l) \rangle 表示将 l-j 个资源分配给第 i 个项目，该边的利润收益为 $N(i, l-j)$[cite: 1]。从源点 V(1,0) 到汇点 V(r+1, n) 的最长路径即为最大利润方案[cite: 1]。

---

第三部分：6.3 货郎担问题 (TSP)

1. 问题形式化描述

货郎担问题（Traveling Salesperson Problem）要求售货员从商店（结点1）出发，访问其余每个村庄各一次，最后回到起点，求总路程最短的周游路线（即包含图中所有顶点的简单有向环）[cite: 1]。

2. 最优性原理证明

任何一条最优周游路线都由一条初始边 \langle 1, j \rangle 以及一条从结点 j 返回结点1的简单路径构成，其中 $j \in V-{1}$[cite: 1]。显然，这条由 j 到1的路径必须无重复地通过集合 V-\{1,j\} 中的所有结点[cite: 1]。如果原周游路线是最优的，则这条由 j 到1的后半段路径也必须是通过剩余结点集的最短路径[cite: 1]。若有更短路径，则替代后可得到更优的周游路线，产生矛盾[cite: 1]。最优性原理成立[cite: 1]。

3. 递推关系式设计

设 g(i, S) 表示从结点 i 出发，无重复地通过集合 S 中的所有结点，并在结点1终止的最短路径长度[cite: 1]。

• 递推公式：$g(i, S) = \min_{j \in S} \{c_{ij} + g(j, S-\{j\})\}$[cite: 1]
• 边界初始值：g(i, \emptyset) = c_{i1} （$1 < i \le n$）[cite: 1]。
• 最终求解目标：$g(1, V-{1})$[cite: 1]。

4. 4顶点实例完整计算过程

代价矩阵如下： $\begin{matrix} 0 & 10 & 15 & 20 \\ 5 & 0 & 9 & 10 \\ 6 & 13 & 0 & 12 \\ 8 & 8 & 9 & 0 \end{matrix}$[cite: 1]

• $|S|=0$：$g(2,\emptyset)=5, g(3,\emptyset)=6, g(4,\emptyset)=8$[cite: 1]。
• $|S|=1$：
  • g(2,\{3\}) = c_{23} + g(3,\emptyset) = 9 + 6 = 15; $g(2,{4}) = c_{24} + g(4,\emptyset) = 10 + 8 = 18$[cite: 1]。
  • g(3,\{2\}) = c_{32} + g(2,\emptyset) = 13 + 5 = 18; $g(3,{4}) = c_{34} + g(4,\emptyset) = 12 + 8 = 20$[cite: 1]。
  • g(4,\{2\}) = c_{42} + g(2,\emptyset) = 8 + 5 = 13; $g(4,{3}) = c_{43} + g(3,\emptyset) = 9 + 6 = 15$[cite: 1]。
• $|S|=2$：
  • $g(2,{3,4}) = \min{c_{23}+g(3,{4}), c_{24}+g(4,{3})} = \min{9+20, 10+15} = 25$[cite: 1]。
  • $g(3,{2,4}) = \min{c_{32}+g(2,{4}), c_{34}+g(4,{2})} = \min{13+18, 12+13} = 25$[cite: 1]。
  • $g(4,{2,3}) = \min{c_{42}+g(2,{3}), c_{43}+g(3,{2})} = \min{8+15, 9+18} = 23$[cite: 1]。
• $|S|=3$：
  • $g(1,{2,3,4}) = \min{c_{12}+g(2,{3,4}), c_{13}+g(3,{2,4}), c_{14}+g(4,{2,3})} = \min{10+25, 15+25, 20+23} = 35$[cite: 1]。

通过标记函数 D(i, S) 反向追溯可得最优路线为：$1 \to 2 \to 4 \to 3 \to 1$，总成本为 35[cite: 1]。

5. 复杂度分析

• 对于给定的规模 $k = |S|$，结点 i 有 n-1 种选择，集合 S 有 C_{n-2}^k 种可能[cite: 1]。
• 整个算法需要求解的函数值个数为 $\sum_{k=0}^{n-2}(n-1)C_{n-2}^k = (n-1)2^{n-2}$[cite: 1]。
• 计算各状态时需要做相应的比较，时间复杂度为 $\boxed{\Theta(n^2 2^n)}$[cite: 1]。此结果虽然远优于蛮力全排列的 $O(n!)$，但由于呈指数级增长，当 n 较大时依然不可取[cite: 1]。

---

第四部分：6.4 0/1背包问题 (0/1 Knapsack Problem)

1. 经典迭代解法与备忘录

采用向后处理递推式：$f_{i}(X) = \max{f_{i-1}(X), f_{i-1}(X-w_{i}) + p_{i}}$[cite: 1]。

• 实例参数：$n=3, w=(2,3,4), p=(1,2,5), M=6$[cite: 1]。
• 备忘录表格 F(i, X) 构建过程：
  • $i=0$：对所有容量 X \in [0,6] 均为 0[cite: 1]。
  • i=1 (w_1=2, p_1=1)：当 0 \le X < 2 时 $F(1,X)=0$；当 2 \le X \le 6 时 $F(1,X)=1$[cite: 1]。
  • i=2 (w_2=3, p_2=2)：运用归并和极大化规则，得到如下阶跃段：$0 \le X < 2 \to 0$；$2 \le X < 3 \to 1$；$3 \le X < 5 \to \max{1, 0+2}=2$；$5 \le X \le 6 \to \max{1, 1+2}=3$[cite: 1]。
  • i=3 (w_3=4, p_3=5)：阶跃结果为 0\le X <2 \to 0; 2\le X <3 \to 1; 3\le X <4 \to 2; 4\le X <6 \to \max\{2, 0+5\}=5; $X=6 \to \max{3, 1+5}=6$[cite: 1]。
• 最优解与回溯确定决策变量：
  • F(3,6)=6 为最优效益值[cite: 1]。
  • 比较 $F(3,6) \neq F(2,6) \implies x_3=1$，剩余容量 $6 - 4 = 2$[cite: 1]。
  • 比较 $F(2,2) = F(1,2) \implies x_2=0$，剩余容量仍为 2[cite: 1]。
  • 比较 $F(1,2) \neq F(0,2) \implies x_1=1$[cite: 1]。
  • 得到最优决策序列：$(x_1, x_2, x_3) = (1, 0, 1)$[cite: 1]。

传统迭代算法的时空复杂度

• 时间复杂度：$\Theta(nM)$；空间复杂度：$\Theta(nM)$[cite: 1]。
• 属性：因为其受背包容量 M 大小的影响，所以属于伪多项式时间算法[cite: 1]。

2. 递推关系式的函数曲线与序偶对法 (Ordered Pairs)

• 函数图像规律：f_{i-1}(X-w_i)+p_i 的图像可由 f_{i-1}(X) 的曲线在 x 轴上向右平移 w_i 个单位、并在垂直方向上移 p_i 个单位得到[cite: 1]。f_i(X) 的新图像由这两条曲线按 X 相同时取极大值的规则归并而成，形成一系列阶跃点（阶梯波）[cite: 1]。
• 序偶对的引入：每一个阶梯波形可以完全由产生阶跃的转折点组成的集合刻画，记为序偶 $(P_j, W_j)$，其中 W_j 是转折容量，P_j 是对应的效益值[cite: 1]。序偶集按 W_j 递增排序，同时必然满足 P_j 严格递增[cite: 1]。

支配规则 (Domination Rule)

已知两序偶 (P_j, W_j) \in S^{i-1} 和 $(P_k, W_k) \in S_1^i$[cite: 1]。如果满足：

W_j \ge W_k \quad \text{且} \quad P_j \le P_k

则说明序偶 (P_j, W_j) 是劣质状态，应予以舍弃，称为 (P_k, W_k) 支配 $(P_j, W_j)$[cite: 1]。

序偶对法的生成与计算实例

• 基础集合：$S^0 = {(0,0)}$[cite: 1]。
• 衍生规则：$S_1^i = {(p+p_i, w+w_i) \mid (p,w) \in S^{i-1}}$[cite: 1]。在生成过程中剔除所有 w > M 的可行解[cite: 1]。
• 按照上述同样实例 n=3, p=(1,2,5), w=(2,3,4), M=6 推演[cite: 1]：
  • $S^0 = {(0,0)}$[cite: 1]。
  • $S_1^1 = {(1,2)} \implies S^1 = {(0,0), (1,2)}$[cite: 1]。
  • S_1^2 = \{(2,3), (3,5)\} \implies S^2 = \{(0,0), (1,2), (2,3), (3,5)\} （无支配发生）[cite: 1]。
  • S_1^3 = \{(5,4), (6,6), (7,7), (8,9)\} \to 剔除 w>6 的项，保留 ${(5,4), (6,6)}$[cite: 1]。
  • 归并 S^2 和 $S_1^3$：由于 (5,4) 的容量小于 (3,5) 且效益大于 $(3,5)$，根据支配规则，(5,4) 支配并舍弃掉 $(3,5)$[cite: 1]。
  • 最终获得 $S^3 = {(0,0), (1,2), (2,3), (5,4), (6,6)}$[cite: 1]。最末序偶效益值 6 即为最优解[cite: 1]。

序偶对法的复杂度与优化

• 最坏复杂度：若无序偶被消除，集合大小每轮翻倍，空间和时间复杂度均为 $O(2^n)$[cite: 1]。
• 整数情况下的复杂度：若 p, w 为整数，集合大小受限于效益总和或容量上限，总运行时间为 $O(\min{2^n, \sum p_j, nM})$[cite: 1]。在支配规则作用下，能够有效处理 n 较大的实际问题[cite: 1]。
• 强力改进：试探/剪枝法：
  • 利用贪心算法预估一个全局可行解效益的下界 L （即满足最终最优解 $f_n(M) \ge L$）[cite: 1]。
  • 定义剩余物品的最大可能总效益为 $PLEFT(i) = \sum_{i < j \le n} p_j$[cite: 1]。
  • 剪枝判定：若当前序偶满足 $p + PLEFT(i) < L$，说明该分支即使后续全部选满也无法超越当前已知下界，直接将 (p,w) 从 S^i 中清除，这极大地压缩了状态空间[cite: 1]。

---

第五部分：6.5 可靠性设计 (Reliability Design)

1. 问题背景与最优化描述

• 系统构造：一个系统由 n 个不同的设备级串联而成：$D_1 \to D_2 \to \dots \to D_n$[cite: 1]。若每级只有一个设备，设备的可靠性（正常运转概率）为 $r_i$，则系统总可靠性为 $\prod r_i$，可靠性会随级数增加而剧烈退化[cite: 1]。
• 改进机制：通过在第 i 级串联处并联配置 m_i 台重复的冗余设备来提升可靠性，该级的正常运转概率改善为 $\phi_i(m_i) = 1 - (1-r_i)^{m_i}$[cite: 1]。
• 最优化目标：在限定的总投资成本预算 C 的约束下，分派各级的设备数量 $m_i$（每级至少1台），使得系统总可靠性最高[cite: 1]。
• 各级设备台数上限确定：$u_j = \lfloor(C + c_j - \sum_{k=1}^n c_k) / c_j\rfloor$[cite: 1]。

2. 递推关系式

使用类似0/1背包的序偶对方法进行极大化求解，状态序偶形式为 $(f, x)$，其中 f 为当前系统可靠性， x 为已消耗的成本[cite: 1]：

• 递推公式：$f_i(x) = \max_{1 \le m_i \le u_i} \{\phi_i(m_i)f_{i-1}(x - c_i m_i)\}$[cite: 1]
• 支配规则：已知两个状态 (f_1, x_1) 和 $(f_2, x_2)$，当且仅当 f_1 \ge f_2 且 x_1 \le x_2 时，第一个状态支配第二个状态，可将 (f_2, x_2) 从集合中剔除[cite: 1]。

3. 三级系统实例计算

系统约束：C=105 元；三级设备成本为 $c=(30, 15, 20)$；可靠性为 $r=(0.9, 0.8, 0.5)$[cite: 1]。

• 计算配置上限：$u_1 = \lfloor(105-15-20)/30\rfloor = 2, u_2=3, u_3=3$[cite: 1]。

• 各阶段序偶集推演：

  • 初始 $S^0 = {(1, 0)}$[cite: 1]。
  • i=1 阶段：$\phi_1(1)=0.9, \phi_1(2)=1-(0.1)^2=0.99 \implies S^1 = {(0.9, 30), (0.99, 60)}$[cite: 1]。
  • i=2 阶段：$\phi_2(1)=0.8, \phi_2(2)=0.96, \phi_2(3)=0.992$[cite: 1]。
    • $S_1^2 = {(0.72, 45), (0.792, 75)}$[cite: 1]
    • S_2^2 = \{(0.864, 60)\} （另一序偶由于超预算或加后续最低成本超105而被剔除）[cite: 1]
    • $S_3^2 = {(0.8928, 75)}$[cite: 1]
    • 归并得 S^2 = \{(0.72, 45), (0.864, 60), (0.8928, 75)\} （其中 (0.792,75) 被 (0.8928,75) 支配舍弃）[cite: 1]。
  • i=3 阶段：$\phi_3(1)=0.5, \phi_3(2)=0.75, \phi_3(3)=0.875$[cite: 1]。
    • 经过相互乘积扩展、预算控制与支配消除，最终得到 $S^3 = {(0.36, 65), (0.432, 80), (0.4464, 95), (0.54, 85), (0.648, 100), (0.63, 105)}$[cite: 1]。

• 最优解回溯：最大可靠性为 0.648，对应总成本 100[cite: 1]。追溯其来源，发现该状态由 S_2^3 产生 $\implies m_3=2$[cite: 1]；其前驱状态 (0.864, 60) 由 S_2^2 产生 $\implies m_2=2$[cite: 1]；再前驱状态 (0.9, 30) 来自 $S_1^1 \implies m_1=1$[cite: 1]。最优决策序列为 $(m_1, m_2, m_3) = (1, 2, 2)$[cite: 1]。

---

第六部分：6.6 最优二分检索树 (Optimal Binary Search Tree)

1. 问题形式化描述

已知一个固定的、排好序的标识符集合 $(a_1, a_2, \dots, a_n)$[cite: 1]。

• 产生一棵含有 n 个圆内结点（代表成功检索项）和 n+1 个方外结点（代表不成功检索的概率区间 $a_i < X < a_{i+1}$）的二分检索树[cite: 1]。
• 目标：令 P(i) 为成功检索 a_i 的概率，Q(i) 为在不成功区间检索的概率，求一棵使预期平均检索成本（比较次数）最小的二分检索树[cite: 1]。
• 预期成本计算公式： $Cost(T) = \sum_{1 \le i \le n} P(i) \cdot level(a_i) + \sum_{0 \le i \le n} Q(i) \cdot (level(E_i) - 1)$[cite: 1]

2. 递推关系式分析

若当前树 T 的根节点选为 $a_k$，则其左子树 L 包含 $(a_1 \dots a_{k-1})$，右子树 R 包含 $(a_{k+1} \dots a_n)$[cite: 1]。将整棵树的成本拆解为子树成本之和加上全体权重在进入下一层级时带来的增量支出[cite: 1]：

• 定义权值 $W(i, j) = Q(i) + \sum_{l=i+1}^j (Q(l) + P(l))$，满足递推关系：$W(i, j) = W(i, j-1) + Q(j) + P(j)$[cite: 1]。
• 设 C(i, j) 为包含标识符子集 a_{i+1} \dots a_j 构成的最优二分检索树的最小预期成本[cite: 1]。
• 通用递推式： $C(i,j) = \min_{i < k \le j} \{C(i, k-1) + C(k, j)\} + W(i,j)$[cite: 1]
• 初始状态（无内结点，规模 $j-i=0$）：C(i,i) = 0 且 W(i,i) = Q(i) （$0 \le i \le n$）[cite: 1]。

3. n=4 实例推导矩阵

参数：$P(1:4) = (3,3,1,1)$，$Q(0:4) = (2,3,1,1,1)$[cite: 1]。 自底向上按照问题规模 m = j-i 从 1 逐步扩增至 4 填表[cite: 1]：

• $m=1$：算得各单结点树成本 C(0,1)=8 [R=1], C(1,2)=7 [R=2], C(2,3)=3 [R=3], $C(3,4)=3 [R=4]$[cite: 1]。
• $m=2$：例如 $C(0,2) = \min_{k \in {1,2}} {C(0,k-1)+C(k,2)} + W(0,2) = \min{0+7, 8+0} + 12 = 19 [R=1]$[cite: 1]。同理算得 C(1,3)=12 [R=2], $C(2,4)=8 [R=3]$[cite: 1]。
• $m=3$：算得 C(0,3)=25 [R=2], $C(1,4)=19 [R=2]$[cite: 1]。
• $m=4$：最终算得全局最优总成本 $C(0,4) = 32$，对应的根节点指标为 $R(0,4) = 2$[cite: 1]。
• 结构解析：因为根节点为 $a_2 (if)$，左子树对应 $R(0,1) \implies a_1 (do)$，右子树对应 $R(2,4) \implies a_3 (read)$，再层层展开即可构建出最优树形态[cite: 1]。

4. D.E.Knuth（高德纳）极限优化与伪代码

标准的动态规划计算中，为了找出区间内的极小值，需要对所有的 k 进行遍历，时间复杂度为 $O(n^3)$[cite: 1]。 高德纳证明了最优的根节点位置 k 的选择范围具有单调性区间约束： $R(i, j-1) \le k \le R(i+1, j)$[cite: 1] 将寻找最优分割点的搜索范围大幅收窄，从而将算法运行的时间复杂度成功优化降至 $O(n^2)$[cite: 1]。

最优二分检索树算法 (OBST)

procedure OBST(P, Q, n)
real P(1:n), Q(0:n), C(0:n, 0:n), W(0:n, 0:n); integer R(0:n, 0:n)
for i <- 0 to n-1 do
    (W(i,i), R(i,i), C(i,i)) <- (Q(i), 0, 0)
    (W(i,i+1), R(i,i+1), C(i,i+1)) <- (Q(i)+Q(i+1)+P(i+1), i+1, Q(i)+Q(i+1)+P(i+1))
repeat
(W(n,n), R(n,n), C(n,n)) <- (Q(n), 0, 0)

for m <- 2 to n do  // m表示子问题规模
    for i <- 0 to n-m do
        j <- i + m
        W(i,j) <- W(i,j-1) + P(j) + Q(j)
        // 限制k在Knuth优化区间内搜索：
        k <- 区间 [R(i, j-1), R(i+1, j)] 中使 {C(i, l-1) + C(l, j)} 最小的 l 值
        C(i,j) <- C(i, k-1) + C(k, j) + W(i,j)
        R(i,j) <- k
    repeat
repeat
end OBST

---

第七部分：6.7 矩阵链乘积问题 (Matrix Chain Multiplication)

1. 问题背景与开销计算

• 问题描述：给定一个矩阵序列（矩阵链） $A_1, A_2, \dots, A_n$，要求计算它们的完整乘积 $A_1 A_2 \dots A_n$，求一种最佳的加括号运算次序，使得总乘法执行次数（计算代价）最少[cite: 1]。
• 乘法代价公式：两个矩阵 A_{p \times q} 与 B_{q \times r} 相乘，得到的乘积矩阵大小为 $p \times r$，所需的乘法执行总次数为 $p \times q \times r$[cite: 1]。
• 不同结合顺序的开销差距示例： 已知三个矩阵规格为：$(A_1){10 \times 100}, (A_2){100 \times 5}, (A_3)_{5 \times 50}$[cite: 1]。
  • 方案一 $(A_1 A_2)A_3$：耗费 10 \times 100 \times 5 + 10 \times 5 \times 50 = 5000 + 2500 = 7500 次[cite: 1]。
  • 方案二 $A_1(A_2 A_3)$：耗费 100 \times 5 \times 50 + 10 \times 100 \times 50 = 25000 + 50000 = 75000 次[cite: 1]。 可以看出，不同的结合次序对运算开销有成倍甚至十倍以上的巨大影响[cite: 1]。

2. 最优性原理证明

在对矩阵子链 A_i A_{i+1} \dots A_j 寻找最佳括号化方案时，必须要选择一个最终的矩阵分割切分点 A_k （$i \le k < j$），将原链一分为二：$(A_i \dots A_k)(A_{k+1} \dots A_j)$[cite: 1]。假设整体方案是最优的，根据最优性原理，此时这两部分子链自身的加括号组合方案也必须分别是各自子问题的最优解[cite: 1]。否则，如果左侧子链存在更省乘法次数的加括号次序，我们直接替换它，就可以拼凑出比原假设成本更低的整体乘积方案，从而产生矛盾[cite: 1]。最优性原理完全成立[cite: 1]。

3. 递推关系式设计

假定矩阵 A_t 的维数可以由维数数组表示为 p_{t-1} \times p_t （对 $t = i, \dots, j$）[cite: 1]。 设 m(i, j) 表示计算矩阵链 A_i \dots A_j 所需的最小乘法代价[cite: 1]。 $m(i,j) = \begin{cases} 0, & i=j \\ \min_{i \le k < j} \{m(i,k) + m(k+1,j) + p_{i-1}p_k p_j\}, & i<j \end{cases}$[cite: 1]

4. 自底向上动态规划实现伪代码

算法同样依据计算链长度 w = j-i 逐层迭代，从小规模合并依次拓展到计算 $m(1, n)$[cite: 1]。

Procedure Matrix-Chain-Order(n)
// 输入参数 n 表示矩阵序列链中矩阵的个数
// 矩阵 A1 的规格为 p0 x p1, A2 规格为 p1 x p2, ... An 规格为 pn-1 x pn
int m(1:n, 1:n), s(1:n-1, 1:n)  // s(i, j) 用于记录使代价最小的分割点 k

for i <- 1 to n-1 do            // 问题规模为 1 时的初始化
    (m(i,i), s(i,i)) <- (0, 0)
    (m(i,i+1), s(i,i+1)) <- (pi-1 * pi * pi+1, i)
repeat
m(n,n) <- 0; s(n,n) <- 0

for w <- 2 to n-1 do            // w 表示问题合并的跨度规模
    for i <- 1 to n-w do
        j <- i + w
        // 在区间内搜索使得乘法总次数最小的分割切分位置 k：
        k <- 区间 [i, j) 中使 {m(i, l) + m(l+1, j) + pi-1 * pl * pj} 取最小值的位置值
        m(i,j) <- m(i,k) + m(k+1,j) + pi-1 * pk * pj
        s(i,j) <- k
    repeat
repeat
end Matrix-Chain-Order

---

注：课件目录中列出的 6.8 流水线调度问题 及 6.9 小结 在后续PPT页面中被略过或未包含具体展开页，以上内容已完全覆盖PPT展示出的所有实质知识体系与推导步骤[cite: 1]。