实验五:矩阵连乘问题(动态规划)报告
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