`
128kj
  • 浏览: 604403 次
  • 来自: ...
社区版块
存档分类
最新评论

动态规划算法学习十例之八

阅读更多
矩阵链乘法最优结合问题
一、《问题的引出》

   看下面一个例子,计算三个矩阵连乘{A1,A2,A3};维数分别为10*100 , 100*5 , 5*50

按此顺序计算需要的次数((A1*A2)*A3):10X100X5+10X5X50=7500次

按此顺序计算需要的次数(A1*(A2*A3)):10X5X50+10X100X50=75000次

所以问题是:如何确定运算顺序,可以使计算量达到最小化。


二、问题描述
  已知:给定n个矩阵构成的一个矩阵链(A1, A2, ..., An),矩阵Ai的维数为pi-1×pi

  求:决定该矩阵链的乘法结合顺序(即加括号),使得矩阵链乘法的运行时间最短


三、几个前提概念
   矩阵链乘法的运行时间将以乘法(单行×单列)的次数来衡量
   A是p×q矩阵,B是q×r矩阵,则A×B的运行时间为pqr
   矩阵乘法满足结合律




四、首先判断是否具有最优子结构
    假设Ai...Aj的矩阵链乘法的最优解是在Ak与Ak+1之间分开的,即(Ai...Ak)(Ak+1...Aj),则子序列也必须是矩阵链乘法的最优解。

由此可知,问题的最优解包含子问题的最优解,满足最优子结构

五、递归表达式
设m[i, j]为矩阵链Ai...Aj的乘法的最短运行时间,m[1, n]即为问题所求的最优解的值
设s[i, j]为运行时间为m[i, j]时的k值,此函数用于递归构造最优解
递归表达式如下



其中矩阵Ai的维数为pi-1 x pi


六、然后进行自底向上的求解

矩阵m是一个上三角矩阵(不需要考虑i>j的情况),且对角线上的元素值均为0

由上面的递归表达式知,m[i, j]的值只取决于m[i, k]和m[k+1, j](k≥i且k<j),
因此自底向上的求解过程实际是按子序列的长度递增来进行的


最后构造最优解

在推导过程中记录s[i, j]的值,用于递归构造最优解(即矩阵链的圆括号添加顺序)

import java.util.Scanner; 
public class MatrixChain {
   private int[] p;
   private long[][] m;
   private int[][] s;

    public MatrixChain(int[] p,long[][] m,int[][] s){
       this.p=p;
       this.m=m;
       this.s=s;
    }

    public long matrixChain() {

        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] = m[i][i]+m[i + 1][j] + p[i - 1] * p[i] * p[j];
                s[i][j] = i;
                for (int k = i + 1; k < j; k++) {
                    long 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;
                    }
                }
           }
       }
      return m[1][n];
    }
   
   public  void printResult(int i,int j)//输出最优加括号方式
{
         if(i==j)
          System.out.print("A"+i);
         else{
          System.out.print("(");
          printResult(i,s[i][j]);
          printResult(s[i][j]+1,j);
          System.out.print(")");
         }
   }
       


    public static void main(String[] args) {

        Scanner in=new Scanner(System.in);
        int n=in.nextInt()+1;//矩阵个数
        int p[]=new int[n];
        for(int i=0;i<n;i++)
          p[i]=in.nextInt();//矩阵维数
    
        long m[][] = new long[n][n];
        int s[][] = new int[n][n];

         MatrixChain mc = new MatrixChain(p,m,s);
        System.out.println("最短运行时间="+mc.matrixChain());

         for (int i = 1; i < n; i++) {
            for (int j = 1; j < n; j++) {
                System.out.print(m[i][j] + "     ");
            }
           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();

        }
       System.out.println("最好的结合顺序");
       mc.printResult(1,n-1);
     }

}  

 


两次运行:
C:\test>java  MatrixChain
4
50 10 40 30 5
最短运行时间=10500
0     20000     27000     10500
0     0     12000     8000
0     0     0     6000
0     0     0     0

0  1  1  1
0  0  2  2
0  0  0  3
0  0  0  0
最好的结合顺序
(A1(A2(A3A4)))


C:\test>java  MatrixChain
6
30 35 15 5 10 20 25
最短运行时间=15125
0     15750     7875     9375     11875     15125
0     0     2625     4375     7125     10500
0     0     0     750     2500     5375
0     0     0     0     1000     3500
0     0     0     0     0     5000
0     0     0     0     0     0

0  1  1  3  3  3
0  0  2  3  3  3
0  0  0  3  3  3
0  0  0  0  4  5
0  0  0  0  0  5
0  0  0  0  0  0
最好的结合顺序
((A1(A2A3))((A4A5)A6))

下载源码:
  • 大小: 1.8 KB
分享到:
评论

相关推荐

    动态规划算法学习十例之七

    在这个“动态规划算法学习十例之七”的主题中,我们将聚焦于一个具体的动态规划问题——最长公共子序列(Longest Common Subsequence,简称LCS)。这个问题在计算机科学中具有很高的实用价值,尤其是在比较和分析...

    动态规划算法学习十例之九

    在这个“动态规划算法学习十例之九”的主题中,我们将聚焦于如何通过DP来解决实际问题。尽管描述部分没有提供具体的实例,但从标题来看,我们可以推测这是一个关于动态规划应用的系列教程的第九个例子。 动态规划的...

    动态规划算法学习十例之六

    在这个主题“动态规划算法学习十例之六”中,我们将探讨如何利用动态规划方法来解决实际问题。博文链接虽然未提供具体内容,但我们可以根据提供的文件名推测讨论的是一个具体的编程实例。 `Main.java`通常是一个...

    动态规划算法学习十例之五

    标题中的“动态规划算法学习十例之五”表明这篇内容主要关注的是计算机科学中的动态规划算法,这是一种在解决复杂问题时非常有效的优化方法。动态规划通常用于处理具有重叠子问题和最优子结构的问题,通过将大问题...

    动态规划算法学习十例之四

    在这个“动态规划算法学习十例之四”的主题中,我们将专注于背包问题的解决方案。背包问题是一个经典的计算机科学问题,它通常涉及在给定容量的背包中选择物品以最大化总价值。 首先,我们来了解动态规划的基本思想...

    动态规划算法学习十例之一

    在这个“动态规划算法学习十例之一”的主题中,我们将会探讨动态规划的基本概念和一个具体的实例,通过分析`Test.java`源码来深入理解。 首先,动态规划的核心思想是将一个大问题分解为相互重叠的小问题,并通过...

    动态规划算法学习十例之二

    在这个"动态规划算法学习十例之二"中,我们很可能会探讨两个具体的动态规划应用:一个可能涉及二项式系数计算,另一个可能是斐波那契数列的求解。下面,我们将深入这两个主题,理解它们背后的动态规划策略。 首先,...

    动态规划算法学习十例之三

    动态规划是一种重要的算法思想,广泛应用于解决复杂问题的优化,如最短路径、背包问题、最长公共子序列等。在本篇文章中,我们将探讨动态规划的精髓,并通过具体实例进行深入学习。博客链接提供了详细的解析,虽然...

    近似串匹配的动态规划算法

    在压缩包中的"近似串匹配问题"文件可能包含了这样的C语言实现,可以作为学习和理解近似串匹配动态规划算法的一个实例。 总结一下,近似串匹配的动态规划算法是一种高效的方法,通过Levenshtein距离或Hamming距离...

    国际大学生程序设计竞赛例题解.三:图论、动态规划算法、综合题专集

    三:图论、动态规划算法、综合题专集》是一本专门针对编程竞赛中的重要算法与问题解决策略的书籍。它涵盖了图论、动态规划以及综合题型,这些都是在竞赛中经常遇到并且至关重要的主题。下面将对这三个方面进行详细的...

    基于Python语言的“算法分析”课程设计——以动态规划算法为例.pdf

    在课程设计过程中,学生还将学习如何分析动态规划算法的时间复杂度和空间复杂度。例如,大多数动态规划解决方案的时间复杂度为O(n*W),其中n是物品数量,W是背包容量,而空间复杂度通常是O(n*W)或者更优,取决于是否...

    初识动态规划算法doc

    动态规划算法以其卓越的能力,成为应对这类问题的首选工具。它通过把复杂问题分解成更小、更易于管理的子问题,以递归的方式进行解决。这种方法不仅效率高,而且在很多情况下比其他算法(如贪婪算法或分治算法)更优...

    动态规划算法.

    在实际编程中,理解和掌握动态规划算法对于提高问题解决能力至关重要,因为它能够优雅地处理复杂度高且具有结构重叠的优化问题。在学习动态规划时,推荐阅读如《Introduction to Algorithms》等经典教材,它们深入浅...

    算法参考资料国际大学生程序设计竞赛例题解3图论·动态规划算法·综合题专集

    标题中提到的是“算法参考资料国际大学生程序设计竞赛例题解3 图论·动态规划算法·综合题专集”。这份资料集中的标题揭示了内容的几个关键点,即它是一份专门为解决算法问题而编写的参考资料,特别针对国际大学生...

    算法动态规划 专题 算法动态规划 专题 ppt

    **算法动态规划专题** 动态规划(Dynamic Programming,简称DP)是一种在计算机科学中解决最优化问题的算法技术,尤其在解决复杂度较高的多阶段决策问题时表现得尤为出色。它通过将大问题分解为小问题,并存储子...

    学习常用算法之(7)动态规划

    动态规划算法通常包含以下几个步骤: 1. 定义状态:识别问题中的关键状态,它们通常是问题的某个阶段的特性描述。 2. 状态转移方程:建立从一个状态到下一个状态的转换规则,这个方程描述了如何根据先前的状态计算...

    基于岭回归机器学习算法的项目成本预测研究——以A风景园林规划研究院规划设计项目为例.pdf

    "基于岭回归机器学习算法的项目成本预测研究——以A风景园林规划研究院规划设计项目为例.pdf" 本文研究主要集中在基于岭回归机器学习算法的项目成本预测研究,以A风景园林规划研究院规划设计项目为例。该研究的目的...

    编程语言算法100例

    本资源包含的100例算法涵盖了排序、搜索、图论、动态规划、递归等多个重要类别。 1. **排序算法**:包括冒泡排序、选择排序、插入排序、快速排序、归并排序、堆排序等。排序算法是数据处理的基础,用于将一组无序的...

Global site tag (gtag.js) - Google Analytics