## 四、实验要求 ### 1. 实验步骤 #### 1.1 算法设计思路 **算法一：直接递归求解** 这是最直观的思路，完全基于问题的递归定义。 * **核心思想**：若要求解 `A[i...j]` 的最小乘法次数，可以将其在 `k` (其中 `i ≤ k < j`) 处分割为两部分：`(A[i...k])` 和 `(A[k+1...j])`。其总成本为左部分的成本 + 右部分的成本 + 两个结果矩阵相乘的成本。我们遍历所有可能的分割点 `k`，取其中的最小值。 * **递归公式**： $$ m[i, j] = \begin{cases} 0 & \text{if } i = j \\ \min_{i \le k < j} \{m[i, k] + m[k+1, j] + p_{i-1}p_k p_j\} & \text{if } i < j \end{cases} $$ * **设计流程图**: ```mermaid graph TD A("开始: solve(i, j)") --> B{i == j?}; B -- 是 --> C("返回 0"); B -- 否 --> D["初始化 min_cost = ∞"]; D --> E("循环 k 从 i 到 j-1"); E --> F["cost = solve(i, k) + solve(k+1, j) + p[i-1]*p[k]*p[j]"]; F --> G{"cost < min_cost?"}; G -- 是 --> H["更新 min_cost = cost"]; G -- 否 --> I("继续循环"); E -- 循环结束 --> J("返回 min_cost"); H --> I; ``` * **预见的问题**：该方法存在大量的重叠子问题。例如，在计算 `m[1,4]` 和 `m[2,5]` 时，都会重复计算 `m[2,3]`、`m[3,4]` 等，导致时间复杂度呈指数级增长，效率极低。 **算法二：备忘录方法（自顶向下动态规划）** 为了解决直接递归的效率问题，引入了备忘录。 * **核心思想**：这是一种带有优化的递归。在递归的基础上，使用一个二维数组（备忘录 `m`）来存储已经计算过的子问题的解。在每次计算 `m[i,j]` 之前，先检查备忘录中是否已有该值。如果有，直接返回；如果没有，则按常规递归方式计算，并将结果存入备忘录后再返回。 * **设计流程图**: ```mermaid graph TD A("开始: solve(i, j, memo)") --> B{"memo[i,j] 是否已计算?"}; B -- 是 --> C("返回 memo[i,j]"); B -- 否 --> D{i == j?}; D -- 是 --> E("设置 memo[i,j] = 0"); D -- 否 --> F["初始化 min_cost = ∞"]; F --> G("循环 k 从 i 到 j-1"); G --> H["cost = solve(i, k, memo) + solve(k+1, j, memo) + ..."]; H --> I{"cost < min_cost?"}; I -- 是 --> J["更新 min_cost = cost, 更新分割点 s[i,j] = k"]; I -- 否 --> K("继续循环"); G -- 循环结束 --> L["设置 memo[i,j] = min_cost"]; L --> M("返回 memo[i,j]"); J --> K; ``` * **优点**：通过空间换时间，避免了重复计算，将时间复杂度从指数级降至多项式级 $O(n^3)$。 **算法三：动态规划（自底向上）** 这是一种更系统化的非递归方法。 * **核心思想**：它迭代地解决问题。首先解决所有长度为2的矩阵链的子问题，然后是长度为3的，依此类推，直到解决整个长度为 `n` 的问题。在计算长链问题时，它所需要的所有短链子问题的解都已经被计算并存储在表中了。 * **设计流程**： 1. 初始化 `m[i,i] = 0` 对所有 `i`。 2. 使用一个循环控制矩阵链的长度 `l`，从2到 `n`。 3. 在 `l` 循环内，使用另一个循环控制起始位置 `i`，从1到 `n-l+1`。 4. 计算结束位置 `j = i + l - 1`。 5. 在 `i` 循环内，使用第三个循环来寻找最优分割点 `k`，从 `i` 到 `j-1`。 6. 根据动态规划公式计算 `m[i,j]` 的值并更新。 7. 同时，使用另一个表 `s[i,j]` 记录最优的分割点 `k`。 * **优点**：与备忘录法的时间复杂度相同（$O(n^3)$），但没有递归开销，通常在实践中效率更高。 #### 1.2 编码、调试与测试 在理解了上述三种思想后，我使用Python语言进行编码。 * **编码**：我将三种方法分别封装在不同的函数中，并设计了一个共用的辅助函数 `_get_parens_from_s_table` 来从记录分割点的 `s` 表中构造最终的加括号字符串。 * **调试**：调试过程中主要遇到的问题是数组索引。矩阵 `Aᵢ` 的维度是 `p[i-1] x p[i]`，在代码中需要小心处理 1-based (矩阵索引) 和 0-based (Python列表索引) 的转换，避免出现越界或逻辑错误。通过小规模的手动计算（如n=3, n=4）来验证程序的输出，确保了算法的正确性。 * **测试**：设计了多组测试数据，包括小规模（n=3）和中等规模（n=13）的数据，以验证代码的正确性并直观地对比不同算法的性能差异。 ### 2. 调试过程与实验结果 #### 测试数据 | 测试名称 | 输入 `p` 数组 | 矩阵数量 `n` | 最优值（乘法次数） | 最优解（加括号方式） | | :------- | :------------------------------- | :----------- | :----------------- | :-------------------------------------- | | 测试1 | `[40, 20, 30, 10, 30]` | 4 | 26000 | `((A1 * (A2 * A3)) * A4)` | | 测试2 | `[30, 35, 15, 5, 10, 20, 25]` | 6 | 15125 | `((A1 * (A2 * A3)) * ((A4 * A5) * A6))` | | 测试3 | `[10, 30, 5, 60]` | 3 | 4500 | `((A1 * A2) * A3)` | | 测试4 | `[30, 35, ..., 14, 20]` (见代码) | 13 | 14690 | `((A1 * (A2 * A3)) * ...)` (见截图) | #### 运行效果截图 ![](../assets/Lab02-strassen.png) ### 4，心得体会 通过本次实验，我不仅成功地用三种不同方法解决了矩阵链乘问题，更对算法设计中的核心思想——特别是动态规划——有了前所未有的深刻理解。 **遇到的问题及解决方法：** 1. **索引的混乱**：在动态规划和备忘录实现中，数组 `p` 的索引 `p[i-1]`, `p[k]`, `p[j]` 与矩阵 `Aᵢ` 的对应关系很容易出错。我曾多次因为循环边界或数组索引错误导致结果不正确。**解决方法**是在纸上画出 `n=4` 的小例子，手动模拟程序的循环过程，跟踪 `i`, `j`, `k`, `l` 等变量的变化，确保逻辑与数学定义一致后，才修复了代码中的bug。 2. **如何构造最优解**：一开始我只关注如何计算最优值（最小乘法次数），但忽略了如何输出具体的加括号方案。**解决方法**是引入一个额外的二维数组 `s[i,j]`，专门用来记录计算 `m[i,j]` 时所选择的最佳分割点 `k`。在计算完所有最优值后，再通过一个独立的递归函数 `_get_parens_from_s_table` 来解析 `s` 表，自顶向下地构造出最优解的字符串表示。 **实验收获与总结：** 1. **深入理解动态规划**：本次实验是理解动态规划思想的绝佳案例。它完美地展示了动态规划的两个核心要素：**最优子结构**（问题的最优解包含其子问题的最优解）和**重叠子问题**（子问题被反复计算）。 2. **掌握DP的两种实现范式**：我亲手实现了自顶向下（备忘录法）和自底向上（迭代法）两种动态规划。我认识到它们在逻辑上是等价的，都是解决同一问题的有效途径，但在实现细节和性能上略有差异。备忘录法更贴近递归的自然思维，而迭代法通常有更好的性能（无递归函数调用开销）。 3. **理论与实践的结合**：通过时间对比，直观地体会到算法复杂度 $O(2^n)$ 和 $O(n^3)$ 具体差别，这让我明白了在解决实际问题时，选择正确高效的算法是多么重要。 ### 4. 附录 ```python import time import sys # =================================================================== # 辅助函数: 根据分割点表 s 构造最优加括号方式的字符串 # (此函数被备忘录和动态规划方法共用) # =================================================================== def _get_parens_from_s_table(s, i, j): """ 根据分割点表 s 递归地构造最优解字符串。 s: 存储最优分割点的二维列表 i, j: 矩阵链的起始和结束索引 """ if i == j: return f"A{i}" else: # 获取i到j之间的最优分割点 k = s[i][j] # 递归构造左右两部分 left = _get_parens_from_s_table(s, i, k) right = _get_parens_from_s_table(s, k + 1, j) # 组合成最终形式 return f"({left} * {right})" # =================================================================== # 方法一: 直接递归求解 # =================================================================== def solve_by_recursion(p): """ 直接递归方法的入口函数。 """ num_matrices = len(p) - 1 if num_matrices == 0: return 0, "" return _recursive_helper(p, 1, num_matrices) def _recursive_helper(p, i, j): """ 递归辅助函数，返回 (最优值, 最优解字符串)。 这种方法会进行大量重复计算，效率极低。 """ # 基本情况：只有一个矩阵，成本为0 if i == j: return 0, f"A{i}" min_cost = float('inf') optimal_solution_str = "" # 遍历所有可能的分割点 k for k in range(i, j): # 递归求解左右子链 cost1, solution1 = _recursive_helper(p, i, k) cost2, solution2 = _recursive_helper(p, k + 1, j) # 计算当前分割方式的总成本 # 成本 = 左部分成本 + 右部分成本 + 两次结果矩阵相乘的成本 current_cost = cost1 + cost2 + p[i - 1] * p[k] * p[j] # 如果当前成本更低，则更新记录 if current_cost < min_cost: min_cost = current_cost optimal_solution_str = f"({solution1} * {solution2})" return min_cost, optimal_solution_str # =================================================================== # 方法二: 备忘录方法求解 # =================================================================== def solve_by_memoization(p): """ 备忘录方法的入口函数。 """ n = len(p) - 1 # m 备忘录存储子问题的最小代价，s 表存储最优分割点 m = [[-1 for _ in range(n + 1)] for _ in range(n + 1)] s = [[0 for _ in range(n + 1)] for _ in range(n + 1)] # 调用辅助函数计算最优值，并填充 s 表 cost = _memoization_helper(p, 1, n, m, s) # 根据 s 表构造最优解字符串 solution_str = _get_parens_from_s_table(s, 1, n) return cost, solution_str def _memoization_helper(p, i, j, m, s): """带备忘录的递归辅助函数，避免重复计算。""" # 如果子问题已经求解过，直接返回存储的结果 if m[i][j] >= 0: return m[i][j] if i == j: m[i][j] = 0 return 0 min_cost = float('inf') for k in range(i, j): cost1 = _memoization_helper(p, i, k, m, s) cost2 = _memoization_helper(p, k + 1, j, m, s) current_cost = cost1 + cost2 + p[i - 1] * p[k] * p[j] if current_cost < min_cost: min_cost = current_cost s[i][j] = k # 关键：记录最优分割点 # 在返回前，将结果存入备忘录 m[i][j] = min_cost return m[i][j] # =================================================================== # 方法三: 动态规划算法求解 # =================================================================== def solve_by_dp(p): """ 使用动态规划方法求解。 """ n = len(p) - 1 m = [[0 for _ in range(n + 1)] for _ in range(n + 1)] s = [[0 for _ in range(n + 1)] for _ in range(n + 1)] # l 是矩阵链的长度，从2到n for l in range(2, n + 1): # i 是起始矩阵的索引，从1到n-l+1 for i in range(1, n - l + 2): j = i + l - 1 m[i][j] = float('inf') # k 是分割点，从i到j-1 for k in range(i, j): # 状态转移方程 q = m[i][k] + m[k + 1][j] + p[i - 1] * p[k] * p[j] if q < m[i][j]: m[i][j] = q s[i][j] = k # 从 s 表中构造最优解字符串 solution_str = _get_parens_from_s_table(s, 1, n) return m[1][n], solution_str # =================================================================== # 主程序: 运行和对比 # =================================================================== if __name__ == '__main__': test_cases = { "测试1 (n=4)": [40, 20, 30, 10, 30], "测试2 (n=6)": [30, 35, 15, 5, 10, 20, 25], "测试3 (n=13)": [30, 35, 15, 5, 10, 20, 25, 10, 15, 5, 10, 12, 14, 20] } for name, p in test_cases.items(): n = len(p) - 1 print(f"\n\n{'='*20} {name} {'='*20}") print(f"问题: {n}个矩阵的链乘问题") print(f"输入维度 p = {p}") print("-" * (42 + len(name))) print("1) 直接递归求解:") start_time = time.perf_counter() cost_rec, solution_rec = solve_by_recursion(p) end_time = time.perf_counter() print(f" 最优值: {cost_rec}") print(f" 最优解: {solution_rec}") print(f" 运行时间: {end_time - start_time:.6f} 秒\n") # 备忘录方法 print("2) 备忘录方法求解:") start_time = time.perf_counter() cost_memo, solution_memo = solve_by_memoization(p) end_time = time.perf_counter() print(f" 最优值: {cost_memo}") print(f" 最优解: {solution_memo}") print(f" 运行时间: {end_time - start_time:.6f} 秒\n") # 动态规划方法 print("3) 动态规划算法求解:") start_time = time.perf_counter() cost_dp, solution_dp = solve_by_dp(p) end_time = time.perf_counter() print(f" 最优值: {cost_dp}") print(f" 最优解: {solution_dp}") print(f" 运行时间: {end_time - start_time:.6f} 秒\n") ```