文章

算法作业4解答题

发表于
作者 Metahumanz
12 分钟阅读
算法作业4解答题

结合您提供的《Chapter 9: Greedy Algorithms》和《Chapter 9: Dynamic Programming》课件，以下是解答题的详细分析过程。我们将直接对标课件中的核心定理、算法思想（如贪心选择性质、最优子结构、自底向上求解等）来进行讲解。

一. 解答题详细分析

1. 矩阵链乘法最优计算顺序

【结合课件讲解】 本题完全对应 DP课件 (Dynamic Matrix Multiplication, Slides 35-48) 中的动态规划矩阵连乘模型。

  • 最优子结构 (Principle of Optimality)：如 DP 课件 Slide 40 所述，最优的矩阵链乘法顺序必定包含其子链的最优顺序。
  • 状态转移方程 (Recurrence Equation)：根据 DP 课件 Slide 42，设 $m[i, j]$ 为计算 $A_i \dots A_j$ 的最少标量乘法次数，递推公式为： \(m[i, j] = \min_{i \le k < j} \{ m[i, k] + m[k+1, j] + P_{i-1} P_k P_j \}\)
  • 计算顺序 (Bottom-up fashion)：根据 DP 课件 Slide 43-44，我们需要按子链的长度（Length r 或 len）从小到大、自底向上地填表。

【解题过程】 已知矩阵维度序列 $P = [10, 30, 5, 60, 10]$。

  1. 初始状态（链长 L=1，对应 Slide 41 $i=j$ 的情况）： $m[1,1] = m[2,2] = m[3,3] = m[4,4] = 0$
  2. 链长 L=2： $m[1,2] = m[1,1] + m[2,2] + 10 \times 30 \times 5 = 1500$ (断点 $k=1$) $m[2,3] = m[2,2] + m[3,3] + 30 \times 5 \times 60 = 9000$ (断点 $k=2$) $m[3,4] = m[3,3] + m[4,4] + 5 \times 60 \times 10 = 3000$ (断点 $k=3$)
  3. 链长 L=3： 计算 $m[1,3]$：
    • $k=1: m[1,1] + m[2,3] + 10 \times 30 \times 60 = 0 + 9000 + 18000 = 27000$
    • $k=2: m[1,2] + m[3,3] + 10 \times 5 \times 60 = 1500 + 0 + 3000 = 4500$ 取最小值，故 $m[1,3] = 4500$ (断点 $k=2$，结合方式 $(A_1A_2)A_3$)

    计算 $m[2,4]$：

    • $k=2: m[2,2] + m[3,4] + 30 \times 5 \times 10 = 0 + 3000 + 1500 = 4500$
    • $k=3: m[2,3] + m[4,4] + 30 \times 60 \times 10 = 9000 + 0 + 18000 = 27000$ 取最小值，故 $m[2,4] = 4500$ (断点 $k=2$，结合方式 $A_2(A_3A_4)$)
  4. 链长 L=4（最终目标 $m[1,4]$）：
    • $k=1: m[1,1] + m[2,4] + 10 \times 30 \times 10 = 0 + 4500 + 3000 = 7500$
    • $k=2: m[1,2] + m[3,4] + 10 \times 5 \times 10 = 1500 + 3000 + 500 = 5000$
    • $k=3: m[1,3] + m[4,4] + 10 \times 60 \times 10 = 4500 + 0 + 6000 = 10500$ 取最小值，故 $m[1,4] = 5000$ (断点 $k=2$)

答： 最少的乘法次数为 5000 次。根据断点追踪，最优计算顺序为 $(A_1 A_2)(A_3 A_4)$。

2. 广告选择问题

1. 假设所有广告效益相等（使用贪心算法） 【结合课件讲解】 根据 Greedy课件 Slide 5 (Definition of Greedy Algorithms)，贪心算法通过一步步做出局部最优选择 (Locally optimal choice)，以期达到全局最优解。贪心选择必须满足三个条件：可行(Feasible)、局部最优(Locally optimal)、不可撤销(Irrevocable)。 本题要求在相容的前提下选择数量最多的广告，类似于找零问题或分数背包问题，需要定义一个度量标准(Metric)。

  • 算法设计： 根据 Greedy课件 Slide 6 (Basic Steps of Greedy Algorithms)，我们选取“截止时间最早”作为度量标准。 已知广告已经按截止时间 $d(i)$ 升序排列。初始化选中集合 $A = {1}$，当前结束时间 $last_end = d(1)$。 依次遍历后续广告 $i = 2 \dots n$，若该广告的开始时间 $s(i) \ge last_end$（满足 Feasible），则将其加入集合 $A$，并更新 $last_end = d(i)$（不可撤销地做出选择）。
  • 正确性证明（贪心选择性质）： 参考 Greedy课件 Slide 21 (贪心选择性和最优子结构) 的证明思路。 设全局最优解为 $O$。将 $O$ 中的广告按截止时间升序排列，设 $O$ 中第一个广告为 $o_1$。 由我们的贪心策略，我们首选了截止时间最早的广告 $1$，显然有 $d(1) \le d(o_1)$。 若 $o_1 \neq 1$，我们将 $O$ 中的 $o_1$ 替换为广告 $1$。由于 $d(1) \le d(o_1)$，广告 $1$ 结束得更早，绝不会与 $O$ 中剩余的其他广告发生时间冲突。因此得到的新集合 $O’$ 依然是相容的，且广告总数不变（依然是最优解）。 这说明总是存在一个包含当前贪心选择的全局最优解（即具备 Greedy-choice property）。同理，对剩余时间段的子问题也满足此性质。得证。
  • 时间复杂度： 由于输入序列已按截止时间排序，算法只需线性扫描一次数组，时间复杂度为 $O(n)$。

2. 如果效益 $v(i)$ 可以取任意正整数（使用动态规划算法） 【结合课件讲解】 参考 DP课件 Slide 46 (0-1背包 v.s. 分数背包)，当带有任意权重（效益）且不能分割时，简单的贪心选择无法保证全局最优，因为“部分闲置的时间空间可能使总体价值降低了”。此时必须放弃贪心算法，改用动态规划 (Dynamic Programming)。

  • 设计思想与主要步骤： 利用 DP 课件中自底向上 (Bottom-up) 的思想。
    1. 最优子结构：按截止时间排序后，对于第 $i$ 个广告，我们只有两种策略：选它，或者不选它。
    2. 定义前驱：为了选它，我们需要找到在广告 $i$ 开始之前就已经结束的最晚广告，记其编号为 $p(i)$。即最大的 $j < i$ 使得 $d(j) \le s(i)$，若不存在则 $p(i)=0$。
    3. 状态定义与转移方程：令 $dp[i]$ 表示在前 $i$ 个广告中能获得的最大总效益。 若不选第 $i$ 个广告：效益为 $dp[i-1]$； 若选第 $i$ 个广告：效益为 $v(i) + dp[p(i)]$。 根据 Bellman 最优化原理 (DP Slide 9)，取两者最大值： $dp[i] = \max(dp[i-1], dp[p(i)] + v(i))$，初始化 $dp[0] = 0$。
    4. 计算顺序：自底向上从 $i=1$ 循环计算至 $n$。最后 $dp[n]$ 即为最大总效益。
  • 最坏情况下的时间复杂度： 计算 $dp$ 数组需要遍历 $n$ 次，耗时 $O(n)$。在每一步寻找 $p(i)$ 时，由于 $d(i)$ 已经是有序的，可以使用二分查找，每次耗时 $O(\log n)$。因此最坏情况下的时间复杂度为 $O(n \log n)$。

3. 字符串运算问题

【结合课件讲解】 本题的结构与 DP课件中的动态矩阵乘法 (Dynamic Matrix Multiplication) 极其相似。给定一个序列，要求判定是否存在某种加括号（运算）顺序使其等于特定结果。 根据 DP课件 Slide 12 (Main idea of Dynamic-Programming)，我们可以将原问题分解为重叠的子问题：一个长字符串的运算结果，取决于它在某个位置切断后，左右两部分子串的运算结果的组合。

  • 算法设计思想： 这是一种典型的区间 DP。我们采用自底向上 (Bottom-up fashion, DP Slide 43) 的方式进行计算。 定义状态 $dp[i][j]$ 为子串 $x_i \dots x_j$ 所有可能的合法运算结果的集合（集合内元素为 ‘a’, ‘b’, ‘c’ 的子集）。我们需要从小到大枚举子串的长度，逐步合并结果。

  • 主要步骤（递归方程）：
    1. 初始化 (Initial Settings)：对于长度为 1 的子串，$dp[i][i] = { x_i }$，其中 $1 \le i \le n$。
    2. 迭代计算 (Bottom-up computation)：参照矩阵链乘法的代码结构，外层循环枚举区间长度 $L$ 从 $2$ 到 $n$。
    3. 内层循环枚举区间的起点 $i$，则终点 $j = i+L-1$。
    4. 状态转移：寻找最优子结构，枚举区间 $[i, j]$ 的分割点 $k$ ($i \le k < j$)。 子问题 1 是 $dp[i][k]$，子问题 2 是 $dp[k+1][j]$。 将这两个集合中的元素两两根据集合 $A$ 的规则进行叉乘运算，将所有可能产生的新字符并入 $dp[i][j]$ 集合中。 公式表示为：$dp[i][j] = \bigcup_{k=i}^{j-1} { c_1 \otimes c_2 \mid c_1 \in dp[i][k], c_2 \in dp[k+1][j] }$。
    5. 返回结果：全部计算完毕后，检查目标字符 ‘a’ 是否存在于集合 $dp[1][n]$ 中。若在则返回 “1”，否则返回 “0”。
  • 最坏情况下的时间复杂度： 参考 DP 课件 Slide 46 对于矩阵乘法的效率分析。 算法包含三重循环：
    1. 枚举长度 $L$，执行 $O(n)$ 次；
    2. 枚举起点 $i$，执行 $O(n)$ 次；
    3. 枚举分割点 $k$，执行 $O(n)$ 次。 在最内层循环中，合并两个 $dp$ 集合的运算。由于题目中字符域只有 ${a, b, c}$ 3 个元素，每个集合的大小最大为 3。集合的遍历和合并（常数次 $3 \times 3 = 9$ 次查表）操作耗时为 $O(1)$。 因此，算法的整体最坏情况时间复杂度为 $O(n^3)$，与动态矩阵乘法的时间复杂度完全一致。
学习, 算法设计与分析
本文由作者按照 CC BY 4.0 进行授权