实验五：矩阵连乘问题（动态规划）报告
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
- 粉丝: 4
- 资源: 17
我的内容管理
展开
最新资源
- 彩虹rain bow point鼠标指针压缩包使用指南
- C#开发的C++作业自动批改系统
- Java实战项目：城市公交查询系统及部署教程
- 深入掌握Spring Boot基础技巧与实践
- 基于SSM+Mysql的校园通讯录信息管理系统毕业设计源码
- 精选简历模板分享：简约大气，适用于应届生与在校生
- 个性化Windows桌面：自制图标大全指南
- 51单片机超声波测距项目源码解析
- 掌握SpringBoot实战：深度学习笔记解析
- 掌握Java基础语法的关键知识点
- SSM+mysql邮件管理系统毕业设计源码免费下载
- wkhtmltox下载困难？找到正确的安装包攻略
- Python全栈开发项目资源包 - 功能复刻与开发支持
- 即时消息分发系统架构设计：以tio为基础
- 基于SSM框架和MySQL的在线书城项目源码
- 认知OFDM技术在802.11标准中的项目实践
资源上传下载、课程学习等过程中有任何疑问或建议，欢迎提出宝贵意见哦~我们会及时处理！
点击此处反馈
