算法导论 14.3 Exercises 答案

发表于 2022-12-17 更新于 2023-07-03 分类于算法导论阅读次数： 87 本文字数： 1.3k 阅读时长 ≈ 1 分钟

14.3-1

调用程序 RECURSIVE-MATRIX-CHAIN 要比直接枚举括号序列优秀。

假设枚举括号序列时也涉及到了第 $k$ 个位置的划分，那么相当于将左半部分的所有解和右半部分的所有解一一组合，和最终答案比较。

而调用程序 RECURSIVE-MATRIX-CHAIN 仅仅将左半部分的最优解和右半部分的最优解进行组合，效率相对有所提升。

14.3-2

MERGE-SORT 的递归树如图所示：

归并排序时对于一个区间 $[l : r]$ 而言，MERGE-SORT 递归地使用 $[l, (l + r) / 2], [(l + r) / 2 + 1]$ 这两个区间的子问题结果。但是这两个子问题并不重叠，因此记忆化并不能够有效改进分值算法的效率，如归并排序。

14.3-3

如果是最大化矩阵链乘的开销，这个问题仍然具有最优子结构：对于矩阵 $A_{i} A_{i + 1} A_{i + 2} \dots A_{j}$ 的链乘，它的最大开销一定是存在某个 $k$ ，来自 $A_{i} A_{i + 1} A_{i + 2} \dots A_{k}$ 和 $A_{k + 1} A_{k + 2} \dots A_{j}$ 的最大开销之和，并且组合起来。

14.3-4

考虑 $n = 3$ ，并且 $⟨ p_{0}, p_{1}, p_{2}, p_{3} ⟩ = ⟨ 5, 7, 6, 3 ⟩$ 。

按照这个贪心思想，那么实际上这个矩阵的运算顺序是 $((A_{1} A_{2}) A_{3})$ ，总开销为 $5 \times 7 \times 6 + 5 \times 6 \times 3 = 300$ 。因为在求解 $m [1, 3]$ 时，有 $p_{2} < p_{1}$ 。

实际上，最优的运算顺序为 $(A_{1} (A_{2} A_{3}))$ ，总开销为 $7 \times 6 \times 3 + 5 \times 7 \times 3 = 231$ ，比这种贪心策略优秀。

14.3-5

不成立。最优子结构要求我们不关心以前做出的决策。但是以前做出的决策中，可能以前做出的决策是已经出来了 $l_{i}$ 根长度为 $i$ 的钢条，如果现在继续以 $i$ 作为决策，那么就会违反题目条件。也就是说，前面的决策会影响后面的决策进行。