『动态规划』矩阵连乘

这篇具有很好参考价值的文章主要介绍了『动态规划』矩阵连乘。希望对大家有所帮助。如果存在错误或未考虑完全的地方,请大家不吝赐教,您也可以点击"举报违法"按钮提交疑问。

活动地址:CSDN21天学习挑战赛
👨‍🎓作者简介:一位喜欢写作,计科专业大三菜鸟

🏡个人主页:starry陆离

🕒首发日期:2022年8月16日星期二

🌌上期文章:『动态规划』动态规划概述

📚订阅专栏:『算法分析与设计』
如果文章有帮到你的话记得点赞👍+收藏💗支持一下哦

『动态规划』矩阵连乘

1.完全加括号的矩阵连乘积

完全加括号的矩阵连乘积可递归地定义为:

  • 单个矩阵是完全加括号的
  • 矩阵连乘积A是完全加括号的,则A可表示为2个完全加括号的矩阵连乘积B和C 的乘积并加括号,即A=(BC)

设有四个矩阵A, B, C, D ,它们的维数分别是:

A = 50*10 B = 10*40 C = 40*30 D = 30*5

总共有五种完全加括号的方式:

『动态规划』矩阵连乘

2.矩阵连乘问题

  • 给定n个矩阵{A1,A2,…,An},其中Ai和Ai+1是可乘的,i=1,2,…,n-1

  • 考察n个矩阵的连乘积

    A1 A2 … An

  • 矩阵乘法满足结合律->计算矩阵的连乘可以有许多不同的计算次序->计算次 序可以用加括号的方式来确定

  • 若一个矩阵连乘积的计算次序完全确定(该连乘积已完全加括号)->可依此 次序反复调用2个矩阵相乘的标准算法计算出矩阵连乘积

问?? 如何确定计算矩阵连乘积的计算次序,使得依此次序计算矩阵连乘积需要的 数乘次数最少

2.2穷举法

列举出所有可能的计算次序,并计算出每一种计算次序相应需要的数乘 次数,从中找出一种数乘次数最少的计算次序

算法复杂度分析: 对于n个矩阵的连乘积,设其不同的计算次序为P(n)。 由于每种加括号方式都可以分解为两个子矩阵的加括号问题:

(A1 ...Ak )(Ak+1…An )可以得到关于P(n)的递推式如下:

『动态规划』矩阵连乘

2.3动态规划

2.3.1问题分析

将矩阵连乘积 AiAi+1......Aj,简记为A[i:j],i≤j

考察计算A[i:j]的最优计算次序:设这个计算次序在矩阵AkAk+1之间将矩阵 链断开,i≤k<j,则其相应完全加括号方式为

『动态规划』矩阵连乘

计算量:A[i:k]的计算量加上A[k+1:j]的计算量,再加上A[i:k]和A[k+1:j]相 乘的计算量(三部分组成)

2.3.2分析最优解的结构

特征:计算A[i:j]的最优次序所包含的计算矩阵子链A[i:k]A[k+1:j]的次序也是也是最优的

矩阵连乘计算次序问题的最优解包含着其子问题的最优解->因此具备最优子结构

『动态规划』矩阵连乘

2.3.3建立递归关系

计算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时,m[i,j]=m[i,k]+m[k+1,j]+ Pi-1 · Pk · Pj

Ai的维数为Pi-1 · Pi

可以递归地定义m[i,j]为:

『动态规划』矩阵连乘

2.3.4计算最优值

对于1≤i≤j≤n不同的有序对(i,j)对应于不同的子问题。不同子问题的个数最多只 有:O(n^2)

在递归计算时,许多子问题被重复计算多次->重叠子问题

  • 用动态规划算法解此问题,可依据其递归式以自底向上的方式进行计算,在计算过程中,保存已解决的子问题答案
  • 每个子问题只计算一次,而在后面需要时只要简单查一下,从而避免大量的重 复计算,最终得到多项式时间的算法

『动态规划』矩阵连乘

2.3.5用动态规划求解最优解

『动态规划』矩阵连乘文章来源地址https://www.toymoban.com/news/detail-467753.html

3.算法实现

3.1备忘录法

/*
int n;//输入的数的个数
int[] num;//储存数
int[][] m;//动态规划数组,保存当前最优解
int[][] s;//用于构造最优解
*/

import java.util.Scanner;
 
public class Main {
    public static void main(String[] args) {
        Scanner scanner=new Scanner(System.in);
        int n;
        int[] num;
        int[][] m;
        int[][] s;
        while(scanner.hasNext()) {
            n=scanner.nextInt();
            num=new int[n];
            m=new int[n][n];
            p=new int[n];
            s=new int[n][n];
            for(int i=0;i<n;++i) {
                num[i]=scanner.nextInt();
            }
            int ans=Solve(1,n-1,m,num,s);
            System.out.println(ans);
        }
    }
    private static int Solve(int i, int j,int[][] m,int[] num,int[][] s) {
        if(m[i][j]>0)return m[i][j];                      
        if(i==j)return 0;
        int u=Solve(i+1, j, m,num,s)+num[i-1]*num[i]*num[j];
        s[i][j]=i;
        for(int k=i+1;k<j;++k) {
            int t=Solve(i, k, m, num, s)+Solve(k+1, j, m, num, s)+num[i-1]*num[k]*num[j];
            if(t<u) {
                u=t;s[i][j]=k;
            }
            m[i][j]=u;
        }
        return u;
    }
}

3.2动态规划

import java.util.Scanner;
 
public class Main {
 
    public static void main(String[] args) {
        Scanner scanner=new Scanner(System.in);
        int n;
        int[] num;
        int[][] m;
        int[][] s;
        while(scanner.hasNext()) {
            n=scanner.nextInt();
            num=new int[n+1];
            m=new int[n+1][n+1];
            s=new int[n+1][n+1];
            for(int i=0;i<n;++i) {
                num[i]=scanner.nextInt();
            }
            n=n-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+1][j]+num[i-1]*num[i]*num[j];
                    s[i][j]=i;
                    for(int k=i+1;k<j;k++) {
                        int t=m[i][k]+m[k+1][j]+num[i-1]*num[k]*num[j];
                        if(t<m[i][j]) {
                            m[i][j]=t;
                            s[i][j]=k;
                        }
                    }
                }
            }
            traceback(s,1,n);
            //System.out.println(m[1][n]);
        }
    }
 
    private static void traceback(int[][] s, int i, int j) {
        if(i==j)return;
        traceback(s, i, s[i][j]);
        traceback(s, s[i][j]+1, j);
        System.out.println("A["+i+":"+s[i][j]+"] * A["+(s[i][j]+1)+":"+j+"]");
         
    }
 
}

到了这里,关于『动态规划』矩阵连乘的文章就介绍完了。如果您还想了解更多内容,请在右上角搜索TOY模板网以前的文章或继续浏览下面的相关文章,希望大家以后多多支持TOY模板网!

本文来自互联网用户投稿,该文观点仅代表作者本人,不代表本站立场。本站仅提供信息存储空间服务,不拥有所有权,不承担相关法律责任。如若转载,请注明出处: 如若内容造成侵权/违法违规/事实不符,请点击违法举报进行投诉反馈,一经查实,立即删除!

领支付宝红包 赞助服务器费用

相关文章

  • 动态规划:矩阵连乘问题,字节跳动今日学习内容

    分析: 二.问题分析 由于矩阵乘法满足结合律,所以计算矩阵连乘的连乘积可以与许多不同的计算计算次序,这种计算次序可以用加括号的方式来确定。若一个矩阵连乘积的计算次序完全确定,也就是说连乘积已完全加括号,那么可以依此次序反复调用2个矩阵相乘的标准算法

    2024年04月11日
    浏览(55)
  • 动态规划:矩阵连乘问题(文末附有手写版例题)

    A是一个p × q矩阵,B是一个q × r矩阵,AB相乘,得到的矩阵元素个数为p × r,每个元素由q次乘法得到,因此所需乘法次数为p × q × r。 在计算矩阵连乘积时,加括号的方式对计算量有影响。 例如有三个矩阵A1,A2,Ag连乘,它们的维数分别为 10x100,100×5,5×50。用第一种加括号方

    2024年02月04日
    浏览(43)
  • 动态规划2:算法考试矩阵连乘问题(超详细手写过程)

                                      更多期末复习笔记欢迎访问我的博客: Miuuu · 语雀​​​​​​​ 动态规划理论基础:(6条消息) 动态规划1:动态规划的入门初学理论基础_黑色柳丁Angel的博客-CSDN博客 矩阵连乘问题是我在算法课接触的第一个动态规划问题

    2023年04月08日
    浏览(40)
  • 动态规划算法学习一:DP的重要知识点、矩阵连乘算法

    三部曲如下三步: 基本原则:“空间换时间” 存储重复子问题的解,减少运算时间 底层运算:“表格操作” 用表格存储子问题的解 实现路线:“子问题划分、自底向上求解” 利用表格中存储的子问题的解,求上一层子问题的解。 矩阵连乘计算次序 可以用 加括号的方式

    2024年02月09日
    浏览(41)
  • 矩阵连乘问题

    【问题】:矩阵链乘问题 : 给定n个矩阵{A1,A2,...,An},其中Ai与Ai+1是可乘的,i=1,2...,n-1。如何确定计算矩阵连乘积的计算次序,使得依此次序计算矩阵连乘积需要的数乘次数最少。 1、按设计动态规划算法的步骤解题。 (1)找出最优解的性质,并刻划其结构特征。 (2)递归

    2024年02月06日
    浏览(36)
  • 矩阵连乘问题C语言实现

    给定n个矩阵{A1,A2,…,An},其中Ai与Ai+1是可乘的,i=1,2…,n-1。如何确定计算矩阵连乘积的计算次序,使得依此次序计算矩阵连乘积需要的数乘次数最少。如数据文件input.txt为: 6(矩阵个数) 30 35 15 5 10 20 25

    2024年02月06日
    浏览(88)
  • 动态规划--矩阵链相乘问题

    明确原始问题A[1:n]: 计算矩阵链 所需的 最小乘法次数。 (1)是否满足最优子结构,问题的解是否包含子问题的优化解? 若计算A[1:n]的优化顺序在 k 处断开矩阵链,即A[1:n]=A[1:k]×A[k+1:n],则在A[1:n]的优化顺序中,对应于子问题A[1:k]的解必须是A[1:k]的优化解,对应A[k+1:n]的解必

    2024年01月25日
    浏览(46)
  • 矩阵链相乘(动态规划法)

    矩阵链乘法是耳熟能详的问题了,有很多矩阵,排列成矩阵链,矩阵链的要求是相邻的两个是可以相乘的,可以相乘是有条件的,两个矩阵能够相乘的条件就是行、列之间是有关系的,两个矩阵如果能够相乘,就是前面矩阵的列号和后面矩阵的行号是一致的。 如何确定矩阵的

    2024年02月09日
    浏览(50)
  • [动态规划]矩阵取数游戏

    题目描述 帅帅经常跟同学玩一个矩阵取数游戏:对于一个给定的n行*m列的矩阵,矩阵中的每个元素aij均为非负整数。游戏规则如下: 1. 每次取数时须从每行各取走一个元素,共n个。m次后取完矩阵所有的元素; 2. 每次取走的各个元素只能是该元素所在行的行首或行尾; 3. 每

    2024年02月04日
    浏览(35)
  • 动态规划问题——矩阵的最小路径和

    题目: 给定一个矩阵m,从左上角开始每次只能向右或者向下走,最后到达右下角的位置,路径上所有的数字累加起来就是路径和,返回所有路径中最小的路径和。 示例: 给定的m如下: 1        3         5        9 8        1        3        4  5        0        6 

    2023年04月08日
    浏览(51)

觉得文章有用就打赏一下文章作者

支付宝扫一扫打赏

博客赞助

微信扫一扫打赏

请作者喝杯咖啡吧~博客赞助

支付宝扫一扫领取红包,优惠每天领

二维码1

领取红包

二维码2

领红包