矩阵连乘问题（动态规划）报告.doc

需积分: 24 69 浏览量更新于2023-03-16 5 收藏 148KB DOC 举报

算法设计与分析实验报告，附已通过源码，供学习参考，共勉♪ 目录摘要如下： 1.问题描述 2.实验目的 3.实验原理 4.实验设计（包括输入格式、算法、输出格式） 5.实验结果与分析（除了截图外，实验结果还用图表进行了分析） 6.结论 7.程序源码

实验五：矩阵连乘问题（动态规划）报告

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.计算最优值

下载后可阅读完整内容，剩余6页未读，立即下载

qq_42236488