/* description:
*
* 动态规划算法之矩阵连乘问题
* 1)矩阵Ai*Ai+1*...*Aj简记为A[i:j],所需的最小计算次数为m[i][j].
* 2)当i=j时,m[i][j] = 0
* 3)当 i<j时,假设使m[i][j]最小的最优次序是在Ak和Ak+1之间断开,
* 则m[i][j] = m[i][k]+m[k+1][j]+p[i-1]*p[k]*p[j],其中k的位置可以是:i, i+1, ..., j-1,
* 数组p[]存储各个矩阵的维数,s[i][j]标记m[i][j]的断开位置k.
*
* auther: cm
* date: 2010/11/16
*/
public class MatrixChain
{
private static final int MAX_VALUE = Integer.MAX_VALUE;
public static void matrixChain(int[] p, int[][] m, int[][] s)
{
int n = p.length - 1;
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] = MAX_VALUE;
for (int k = i; k < j; k++)
{
int temp = m[i][k] + m[k + 1][j] + p[i - 1] * p[k] * p[j];
if (temp < m[i][j])
{
m[i][j] = temp;
s[i][j] = k;
}
}
}
}
System.out.println("The lowest compute times:" + m[1][n]);
}
//输出A[i:j]的最优计算次序
public static void traceback(int[][] s, int i, int j)
{
if (i == j)
{
System.out.print("A" + i);
}
if (i < j)
{
System.out.print("(");
traceback(s,i,s[i][j]);
traceback(s, s[i][j] + 1, j);
System.out.print(")");
}
}
//输出矩阵
public static void printMatrix(int[][] m)
{
for (int i = 1, length = m.length; i < length; i++)
{
System.out.println();
for (int j = 1, l = m[i].length; j < l; j++)
{
System.out.print(m[i][j] + " ");
}
}
}
public static void main(String[] args)
{
int[] p = {30, 35, 15, 5, 10, 20, 25};
int[][] m = new int[7][7];
int[][] s = new int[7][7];
MatrixChain.matrixChain(p, m, s);
//MatrixChain.printMatrix(m);
//MatrixChain.printMatrix(s);
MatrixChain.traceback(s, 1, 6);
}
}
共有六个矩阵,维数分别为:
30*35
35*15
15*5
5*`10
10*20
20*25
运行结果为:
The lowest compute times:15125
((A1(A2A3))((A4A5)A6))
分享到:
相关推荐
c++实现矩阵连乘问题,通过动态规划法的思想求得。
动态规划方法解决矩阵连乘问题,即寻求多个矩阵连乘时的最好的加括号方式使得总的乘法两最小; 可以设定矩阵个数,手动输入矩阵的阶,显示动态规划算法的表格,即乘法量和括号信息; 多文档,C++6.0
算法设计与分析,使用动态规划法解决矩阵连乘问题。内有MatrixChain、TraceBack、RecurMatrixChain-递归解决矩阵连乘问题等程序,非常超值啊!
主要介绍了Java矩阵连乘问题(动态规划)算法,结合实例形式分析了java实现矩阵连乘的算法原理与相关实现技巧,需要的朋友可以参考下
矩阵连乘问题算法描述 矩阵连乘问题的算法实现 矩阵连乘问题的算法实现
c/c++语言解决矩阵连乘文题,几个矩阵相乘求最佳结合顺序
矩阵连乘问题分析和实现用于动态规划 最佳加括号方式-动态规划算法
用Java来解决算法 矩阵连乘问题。实例6个二维矩阵相乘,求找到最优计算次序。
如何确定计算矩阵连乘积的计算次序,使得依此次序计算矩阵连乘积需要的数乘次数最少。 Input 输入包含多组测试数据。第一行为一个整数C,表示有C组测试数据,接下来有2*C行数据,每组测试数据占2行,每组测试...
动态规划思想的介绍(矩阵连乘问题,最长公共子序列,流水线作业调度问题,0-1背包问题)。算法课使用的ppt,可结合我的博客算法专栏一起看。有详细代码。
实现计算多个矩阵连乘的最终结果并且对时间复杂度进行了优化
算法设计与分析实验报告,附已通过源码,...1.问题描述 2.实验目的 3.实验原理 4.实验设计 (包括输入格式、算法、输出格式) 5.实验结果与分析 (除了截图外,实验结果还用图表进行了分析) 6.结论 7.程序源码
用动态规划思想解决矩阵连乘的问题。………………………………
【问题描述】使用动态规划算法解矩阵连乘问题,具体来说就是,依据其递归式自底向上的方式进行计算,在计算过程中,保存已子问题答案,每个子问题只解决一次,在后面计算需要时只要简单查一下得到其结果,从而避免...
详细叙述了矩阵连乘的法则,解释的清楚。而且有算法实现,真的是不错的东东