Java矩阵连乘问题(动态规划)算法实例分析
作者:萌神哆啦A梦 发布时间:2022-05-04 21:50:54
本文实例讲述了Java矩阵连乘问题(动态规划)算法。分享给大家供大家参考,具体如下:
问题描述:给定n个矩阵:A1,A2,...,An,其中Ai与Ai+1是可乘的,i=1,2...,n-1。确定计算矩阵连乘积的计算次序,使得依此次序计算矩阵连乘积需要的数乘次数最少。输入数据为矩阵个数和每个矩阵规模,输出结果为计算矩阵连乘积的计算次序和最少数乘次数。
问题解析:由于矩阵乘法满足结合律,故计算矩阵的连乘积可以有许多不同的计算次序。这种计算次序可以用加括号的方式来确定。若一个矩阵连乘积的计算次序完全确定,也就是说该连乘积已完全加括号,则可以依此次序反复调用2个矩阵相乘的标准算法计算出矩阵连乘积。
完全加括号的矩阵连乘积可递归地定义为:
(1)单个矩阵是完全加括号的;
(2)矩阵连乘积A是完全加括号的,则A可表示为2个完全加括号的矩阵连乘积B和C的乘积并加括号,即A=(BC)
例如,矩阵连乘积A1A2A3A4有5种不同的完全加括号的方式:(A1(A2(A3A4))),(A1((A2A3)A4)),((A1A2)(A3A4)),((A1(A2A3))A4),(((A1A2)A3)A4)。每一种完全加括号的方式对应于一个矩阵连乘积的计算次序,这决定着作乘积所需要的计算量。
看下面一个例子,计算三个矩阵连乘{A1,A2,A3};维数分别为10*100 , 100*5 , 5*50 按此顺序计算需要的次数((A1*A2)*A3):10X100X5+10X5X50=7500次,按此顺序计算需要的次数(A1*(A2*A3)):10*5*50+10*100*50=75000次
所以问题是:如何确定运算顺序,可以使计算量达到最小化。
算法思路:
例:设要计算矩阵连乘乘积A1A2A3A4A5A6,其中各矩阵的维数分别是:
A1:30*35; A2:35*15; A3:15*5; A4:5*10; A5:10*20; A6:20*25
递推关系:
设计算A[i:j],1≤i≤j≤n,所需要的最少数乘次数m[i,j],则原问题的最优值为m[1,n]。
当i=j时,A[i:j]=Ai,因此,m[i][i]=0,i=1,2,…,n
当i<j时,若A[i:j]的最优次序在Ak和Ak+1之间断开,i<=k<j,则:m[i][j]=m[i][k]+m[k+1][j]+pi-1pkpj。由于在计算是并不知道断开点k的位置,所以k还未定。不过k的位置只有j-i个可能。因此,k是这j-i个位置使计算量达到最小的那个位置。
综上,有递推关系如下:
构造最优解:
若将对应m[i][j]的断开位置k记为s[i][j],在计算出最优值m[i][j]后,可递归地由s[i][j]构造出相应的最优解。s[i][j]中的数表明,计算矩阵链A[i:j]的最佳方式应在矩阵Ak和Ak+1之间断开,即最优的加括号方式应为(A[i:k])(A[k+1:j)。因此,从s[1][n]记录的信息可知计算A[1:n]的最优加括号方式为(A[1:s[1][n]])(A[s[1][n]+1:n]),进一步递推,A[1:s[1][n]]的最优加括号方式为(A[1:s[1][s[1][n]]])(A[s[1][s[1][n]]+1:s[1][s[1][n]]])。同理可以确定A[s[1][n]+1:n]的最优加括号方式在s[s[1][n]+1][n]处断开...照此递推下去,最终可以确定A[1:n]的最优完全加括号方式,及构造出问题的一个最优解。
package Matrix;
public class Matrix {
public static void MatrixChain(int[] p,int n, int[][] m, int[][] s) {
for (int i = 1; i <= n; i++) {
m[i][i] = 0;
}
for(int r = 2;r <= n; r++ ) {
for(int i = 1; i <= n-r+1; i++) {
int j = i+r-1;
m[i][j] = m[i+1][j] + p[i-1]*p[i]*p[j];
s[i][j] = i;
for(int k = i+1; k < j; k++) {
int t = m[i][k] + m[k+1][j] + p[i-1]*p[k]*p[j];
if(t < m[i][j]) {
m[i][j] = t;
s[i][j] = k;
}
}
}
}
}
public static void Traceback(int i, int j, int[][] s) {
if(i == j) return;
Traceback(i,s[i][j],s);
Traceback(s[i][j] + 1,j,s);
System.out.println("Multiply A" + i + "," + s[i][j] + "and A" + (s[i][j] + 1) + "," + j);
}
public static void main(String[] args) {
System.out.println("脚本之家测试结果:");
Matrix mc = new Matrix();
int n = 7;
int p[] = { 30, 35, 15, 5, 10, 20, 25 };
int m[][] = new int[n][n];
int s[][] = new int[n][n];
int l = p.length-1;
mc.MatrixChain(p, l,m, s);
for (int i = 1; i < n; i++) {
for (int j = 1; j < n; j++) {
System.out.print(m[i][j] + "\t");
}
System.out.println();
}
System.out.println();
for (int i = 1; i < n; i++) {
for (int j = 1; j < n; j++) {
System.out.print(s[i][j]+" ");
}
System.out.println();
}
mc.Traceback( 1, 6, s);
}
}
运行结果:
希望本文所述对大家java程序设计有所帮助。
来源:http://blog.csdn.net/u014755255/article/details/50571173


猜你喜欢
- 一、OutputStreamWriter流 API说明:OutputStreamWriter是从字符流到
- 前面几篇文章分别讨论了Activity和Service,本文就来讨论BroastcastReceiver,Broastcast是应用程序间通
- 本文实例为大家分享了Android Studio实现简单计算器功能的具体代码,供大家参考,具体内容如下程序步骤:(1)在布局文件定义一些计算
- 一、定时任务1、cron表达式语法:秒 分 时 日 月 周 年(其中“年”Spring不支持,也就是说在spring定时任务中只能设置:秒
- 前言日常开发中,特别是音视频开发,需要在界面上渲染视频,比如制作一个播放器、或者视频编辑工具、以及视频会议客户端。通常拿到的是像素格式数据,
- 一、推迟执行动作可以使用timer+map方法实现.代码如下:Observable.timer(5, TimeUnit.MILLISECON
- 在Android开发中,我们不光可以使用已有的实现方式,而且,我们还可以利用Android这个智能手机平台,实现一些比较有特色的功能。本篇文
- Android 中Volley二次封装并实现网络请求缓存Android目前很多同学使用Volley请求网络数据,但是Volley没有对请求过
- 前言我们在配置Spring Xml配置文件的时候,可以在文件路径字符串中加入 ${} 占位符,Spring会自动帮我们解析占位符,这么神奇的
- SQLite 介绍SQLite,是一款轻型的数据库,用于本地的数据储存。先说说优点,它占用资源非常的低,在嵌入式设备中需要几百K的内存就够了
- 前言身在孤岛有很多无奈,比如说程序员属于比较偏门的职业。尤其是早些年,在行业里跳过几次槽后,可能你就已经认识整个圈子的人了。然后,再跳槽很可
- 最近一直在写c#的时候一直遇到这个报错,看的我心烦。。。准备记下来以备后续只需。参考博客:https://segmentfault.com/
- 使用System.Environment获取电脑的相关属性,入门案例,具体内容如下static void Main(string[] arg
- 前言我们一说到spring,可能第一个想到的是 IOC(控制反转) 和 AOP(面向切面编程)。没错,它们是spring的基石,得益于它们的
- 一、概述有序数组中常常用到二分查找,能提高查找的速度。今天,我们用顺序查找和二分查找实现数组的增删改查。二、有序数组的优缺点优点:查找速度比
- Mybatis有什么用前两天跟阿里的大牛聊天,他讲到对于性能要求高,需求变化多的互联网项目来说,用在sql优化上的开发时间是大头,有时候代码
- 先说一句:密码是无法解密的。大家也不要再问松哥微人事项目中的密码怎么解密了!密码无法解密,还是为了确保系统安全。今天松哥就来和大家聊一聊,密
- 一 Flow使用注意事项多个Flow不能放到一个lifecycleScope.launch里去collect{},因为进入collect{}
- 本文实例讲述了C#实现导入CSV文件到Excel工作簿的方法。分享给大家供大家参考。具体如下:你必须在项目中添加对 Microsoft.Of
- Android中判断网络是否连接实例详解在android中,如何监测网络的状态呢,这个有的时候也是十分重要的,方法如下:public cla