C[i, j ] = min{C[1, k − 1] + C[k , n] + r1rk rn +1}
1< k ≤ n
这样，求 M1M2…Mn 所需要最少数量乘法次数只需要求解 C[1,n]即可。 其算法伪代码如下： 1. for i←1 to n 2. C[i,j]←0 3. end for 4. for d←1 to n-1 5. for i←1 to n-d 6. j←i+d 7. C[i,j]←∞
n −1
f ( n) =
1 2n − 2 (2n − 2)! 4n 4n ，因此 ( ) = Ω ( ) ，对于每一种方案， = ≈ f n 2 n1.5 n 4 π n1.5 n − 1 n((n − 1)!)
找到数量乘法的次数还需要 Θ(n) 时间，因此总的时间复杂度为
∑∑∑ c = c((n − 1) ×1 + (n − 1) × 2 + + (n − (n − 1)) × (n − 1))
d =1 i =1 k =1
n −1 n − d d
= c(n × (1 + 2 + + (n − 1)) − (1×1 + 2 × 2 + (n − 1) × (n − 1))) n 2 × (n − 1) n × (n − 1) × (2n − 1) = c( − ) 2 6 cn 3 − cn = = Θ( n 3 ) 6 三、实验内容及要求 1. 编写程序使用动态规划算法 MATCHAIN 求解 n 个矩阵连乘所需最找数 量乘法次数，并用实际数据对算法进行测试。 2. 要求对算法 MATCHAIN 加以改进，不仅能够输出数量乘法次数，还要 能输出最佳乘法方案，如(M1M2)((M3M4)M5)。 四、实验步骤
1. 编写函数 MATCHAIN 求解矩阵链相乘问题，函数头为： int MATCHAIN(int r[], int n) r 为数组名， r[i]和 r[j]分别表示矩阵 Mi 的行数和列数， n 表示连乘矩阵的个数。 2. 在 main 函数中使用给定数组{4,5,3,6,4,5}测试 MATCHAIN 函数， 效果如下图所示。
= rn max( pi + rn −i )
1≤ i ≤ n
根据此公式，可按照长度为 0,1,2,…,n 的顺序逐步求解最优切割方案。（注意： 程序中不需要使用递归调用）
实验二 动态规划法
一、实验目的 1．理解动态规划法的方法； 2. 掌握使用动态规划法解决一般问题的步骤； 3. 掌握动态规划算法求解矩阵连续相乘的方法。 二、实验原理 假设有 M1，M2，M3 这三个矩阵，这三个矩阵的维数分别是 2×10，10×2 和 2×10，要求他们的乘积 M1M2M3。如果先将 M1 和 M2 相乘，然后将结果和 M3 相乘，那么要进行 2×10×2+2×2×10=80 次乘法。如果先用 M2 和 M3 相 乘，然后将结果和 M1 相乘，那么要进行 10×2×10+2×10×10=400 次乘法。 显然，矩阵乘法的顺序不同会导致乘法次数的不同。 一般来说，n 个矩阵 M1M2…Mn 链乘法的耗费，取决于 n-1 个乘法执行的 顺序。如果使用满立法计算每一种可能顺序的数量乘法次数。设 f(n)是求 n 个 矩阵乘积可能的顺序数，假定要进行以下乘法(M1M2…Mk)(Mk+1Mk+2…Mn)，那 么，对于前 k 个矩阵有 f(k)种方案，对于每一种方案，对余下的 n-k 个矩阵有 f(n-k)种方案，因此总共有 f(k)f(n-k)种方案。因此，n 个矩阵相乘总的方案数 为 f (n) = ∑k =1 f (k ) f (n − k ) 种，经计算可以证明
C[2,2]
C[2,3]Leabharlann C[2,4]C[2,5]
C[3,3]
C[3,4]
C[3,5]
C[4,4]
C[4,5]
C[5,5]
代码第 1 行~第 3 行填充对角线 d=0， 第 4 行的循环用来填充对角线 d=1 到 d=n-1，第 5 行循环用于填充对角线 d=i 的项目，第 8 行~第 10 行用于计 算 C[i,j]，函数的返回值在第 13 行给出，为 C[1,n]，即矩阵 M1M2…Mn 链相 乘所需最少乘法的次数。 算法的时间复杂度分析如下：
8. for k←i+1 to j 9. C[i,j]←min{C[i,j],C[i,k-1]+C[k,j]+r[i]r[k]r[j+1]} 10. end for 11. end for 12.end for 13.return C[1,n]
C[1,1]
C[1,2]
C[1,3]
C[1,4]
C[1,5]
f (n) = Ω(4 n / n ) ，随着 n 的增大，f(n)的增长速度惊人。
采取动态规划法的思想，对于 n 个矩阵 M1M2…Mn，其中矩阵 Mi 的行数和 列数分别用 ri 和 ri+1 来表示，因此需要一个 n+1 维的矩阵存储 n 个矩阵的行数 和列数。令 Mi,j 为 M1M2…Mn 的成绩，计其乘法所耗费的数量乘法的次数为 C[i,j]，则有以下递推式：
五、思考和作业 1. 对 MATCHAIN 算法加以改进，使算法能够输出乘法方案，效果如下图 所示。
提示： (1) 用一个数组 brackets 记录矩阵链乘法方案括号的数目， 数组 brackets 的大小为 2n，brackets[0]和 brackets[1]分别表示矩阵 1 的左括号和右括号 数目。 (2) 设定辅助矩阵 flag，其大小和矩阵 C 等同，flag[i,j]表示求解 C[i,j] 时所得到的最佳分割 k 值，如计算 C[2,5]时，使 C[2,5]值最小的 k 的值为 4， 则 flag[2,5]=4，利用 flag 数组可以计算 brackets 数组的值。 (3) 根据 brackets 数组输出最终方案。 2. 钢条切割问题 给定一段长度为 n 的钢条和一个价格表 pi(i=1,2,…,n)，求切割钢条方案， 使得销售收益 rn 最大。 提示：要求长度为 n 的钢条的最好切割方案，可以使用以下递归求解方法： 将钢条从左边切割下来长度为 i 的一段，对右边剩下长度为 n-i 的一段继续进行 切割（递归求解），对左边一段不再进行切割。