实验五：矩阵连乘问题（动态规划）报告
2017061111 李静娴
1．问题描述
给定 n 个矩阵：A1,A2,...,An，其中 Ai 与 Ai+1 是可乘的，i=1，2...，n-1。确定计算矩阵
连乘积的计算次序，使得依此次序计算矩阵连乘积需要的数乘次数最少。输入数据为矩阵
个数和每个矩阵规模，输出结果为计算矩阵连乘积的计算次序和最少数乘次数。
2．实验目的
（1）熟悉动态规划算法，并学以致用
（2）熟练掌握矩阵连乘算法
3．实验原理
1.分析最优解的结构
首先，为方便起见，将矩阵连乘积 简记为 A[i:j]。考查计算 A[1:n]的最优计算次
序。这个问题的一个关键特征是：计算 A[1:n]的最优次序所包含的计算矩阵子链 A[1:k]和
A[k+1:n]的次序也是最优的。因此，矩阵连乘积计算次序问题的最优解包含着其子问题的最
优解。
2.建立递归关系
对于矩阵连乘积的最优计算次序问题，设计算 A[i:j],1≤i≤j≤n，所需的最少数乘次数为 m[i]
[j]，则原问题的最优值为 m[1][n]。
当 i=j 时，A[i:j]= 为单一矩阵，无需计算，因此，m[i][j]=0，i=1,2,…,n。
当 i<j 时，可利用最优子结构性质计算 m[i][j]。事实上，若计算 A[i:j]的最优次序在 和
之间断开，i≤k<j，则 m[i][j]=m[i][k]+m[k+1][j]+ × × 。由于在计算时并不知道断
开点 k 的位置，所以 k 还未定。不过 k 的位置只有 j-i 种可能，即 k∈{i,i+1,…,j-1}。因此，k 是
这 j-i 个位置中使计算量达到最小的那个位置。从而 m[i][j]可以递归的定义为：
m[i][j]给出了最优值，即计算 A[i:j]所需的最少数乘次数。同时还确定了计算 A[i:j]的最优次
序中的断开位置 k，也就是说，对于这个 k 有
m[i][j]=m[i][k]+m[k+1][j]+
若将对应于 m[i][j]的断开位置 k 记为 s[i][j]，在计算出最优值 m[i][j]后，可递归地由 s[i][j]构
造出相应的最优解。
3.计算最优值
评论0