矩阵链乘法的动态规划算法_1

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

矩阵链乘法的动态规划算法(Matrix Chain Multiplication)

上次我们学习了rod-cutting 问题的动态规划算法,初步了解求解动态规划过程的CRCC步骤,此步骤对于可以运用动态优化的问题非常有用,类似给大家提供了一套思维模板,让我们能更系统的思考和解决问题。本次我们将讨论矩阵链乘法的动态规划算法。

矩阵乘法

在讨论矩阵链乘法之前,我们先了解一下矩阵乘法的基本要素,对于矩阵乘法C(i,k)=A(i,j) * B(j,k), 如果两个矩阵可以相乘,那么A矩阵的列数(j)必须等于B矩阵的行数(j),否则我们成为两个矩阵乘法不相容,相乘的结果为矩阵C, 它的行等于A矩阵的行数,列数等于B矩阵的列数,对于两个矩阵的乘法,我们一般采用标量相乘然后求和即可。对于A*B相乘,给出一般的算法如下,我们注意到,标量相乘的m3->data[i] [j]+=(m1->data[i] [k]) * (m2->data[k] [j])的执行次数对程序的效率影响非常大,对于两个矩阵相乘,其循环的次数已经固定,无法优化。

typedef struct matrix
{
    int row;//row 矩阵行数
    int col;//col 矩阵列数
    int **data; //矩阵实际储存数据,本次探讨的为二维矩阵
}matrix, *matrix_ptr;

/**
	m3=m1*m3, 相乘后返回 指向矩阵 的指针,使矩阵运算统一化
*/
matrix_ptr matrix_multiply(matrix_ptr m1, matrix_ptr m2)
{
    matrix_ptr m3;
    int i;
    int j;
    int k;

    m3=(matrix_ptr)malloc(sizeof(matrix)*1);
    m3->row=m1->row;
    m3->col=m2->col;

    m3->data=(int **)malloc(sizeof(int *)*m3->row);

    for(i=0;i<m3->row;i++)
    {
        *(m3->data+i)=(int *)malloc(sizeof(int)*m3->col);
    }

    for(i=0;i<m1->row;i++)
    {
        for(j=0;j<m2->col;j++)
        {
            m3->data[i][j]=0;
            for(k=0;k<m1->col;k++)
            {
                m3->data[i][j]+=(m1->data[i][k])*(m2->data[k][j]);
            }
        }
    }

    return m3;
}

矩阵链乘法

那么矩阵链的乘法如何定义呢,我们假定存在矩阵<A1, A2, A3…An>,其之间相乘互容,那么此时标量相乘的次数就可以随着不同矩阵之间的结合而发生变化,列举简单示例来阐述这个观点,为了方便,我们假定有3个矩阵相乘(A1,A2,A3),假定A1的行数=6,列数=7; A2的行数=7,列数=3; A3的行数=3,列数=1。

由于矩阵之间相互相容,此时就有两种途径来解决问题:

  • C=(A1 * A2) * A3, 标量相乘的次数=6 * 7 * 3 + 6 * 3 * 1=144
  • C=(A1 * (A2 * A3)), 标量相乘的次数=6 * 7 * 1 + 7 * 3 * 1 = 63

我们很容易发现,第二种方法的标量相乘次数仅有第一种算法的一半不到,示例中仅有三个矩阵相乘,如果矩阵数量增加,找到合适的矩阵相结合可以明显降低计算的次数,这将非常显著地提升矩阵链乘法的效率。

矩阵链乘法的动态规划

本文主要探讨如何按照合适的次序对矩阵进行相乘,取得最小的标量相乘次数,需要注意的是,我们并不需要实际对矩阵做乘法运算,仅仅求解矩阵链相乘某个最优次序,使得标量相乘的次数最少。首先确认此问题属于最优化问题的范畴,这有再这个前提之下,我们才能着手开展动态规划算法。

我们接下来按照动态规划的CRCC步骤依次对此问题进行剖析,最终求得动态规划的各个条件。

a) Characterize the structure of the optimal solution, 表征最优问题的基本结构

我们要找到基本结构,最重要的事情是能找到不同层次的子结构,并且其求解具有相似性,这样才能满足后面的递归或者迭代的计算条件。让我们假定矩阵链的下标可以用数组p来表示p[]=<p0,p1,p2,p3…pn>,此数组中包含了A=<A1,A2,A3…An>所有的下标的集合。为了方便阐述问题,本文的研究对象就转化为求解p数组内部标量运算的次数的最小值的某一序列(可以用括号划分和嵌套,表示矩阵之间乘法运算的优先级,从而使标量运算的总次数最小)。

假定我们把矩阵链<A1,A2,A3…An>划分为两个子问题,<A1,A2,A3…Ak>和<Ak+1,Ak+2,Ak+3…An>,我们就会发现第一个子问题和第二个子问题的表示形式存在差异,因为第一个子问题的前段是固定的,永远都是A1;与此同时,第二个子问题的后段是固定的,永远都为An,显然这两个子结构不相同。

接下来我们继续尝试,把矩阵链<A1,A2,A3…An>划分为<A1,A2,A3…Ak>和<Ak+1,Ak+2,Ak+3…Aj>两个子问题,我们就会发现两个子问题仍然不同,第一个子问题的左端仍然固定,第二个子问题两端可以进行变化,如果我们总能保证k=j-1,那么问题也可以划分成这类形式,因为第二个问题的标量运算总是0,因为第二个子问题会退化为< Aj>的单个矩阵的形式,从而可以直接递归返回,再往下看,实际上就退化为一个子问题,显然这与实际情况不相符合。

最后,通过前述的尝试,我们如果把矩阵链划分为<Ai,Ai+1…Ak>和<Ak+1,Ak+2,…Aj>两个子问题,那么问题就迎刃而解,此问题可以描述为,如果要求解<Ai,Ai+1,…Ak-1,Ak>的标量运算的总数的最小值,我们需要把此问题分解为两个子问题<Ai,Ai+1…Ak>和<Ak+1,Ak+2,…Aj>。如果<Ai,Ai+1,…Ak-1,Ak>取得最优解,那么其两个子问题一定是最优解,也即<Ai,Ai+1…Ak>和<Ak+1,Ak+2,…Aj>此时也是最优解。此时就具备了递归的雏形,可以再接下来一步总来定义递归表达式的值得求解。

可能我们会有疑惑,为什么在<Ai,Ai+1,…Ak-1,Ak>获得标量运算次数最小的时候,它的两个子问题也同时具备运算次数最小呢? 其实这个问题就回归到 原问题和子问题的逻辑关系,可以用反正法来证明,如果子问题不具备最优的解,那么一定在这个子问题中找到最优解,那么此时原问题的最优解就不是最优解,这与事实相矛盾。

b) Recursively define the value of the optimal solution-递归定义最优解的值

这一步是后续程序实现的关键,如果能顺利递归定义表达式,那么后面的递归程序就是水到渠成的事情了。让我们继续回到问题的本身,为了方便问题描述,我们引入 m[i,j]数组,此数组表示矩阵链A i:j 标量运算次数的最小值,引入m[i,j]数组以后,我们就会发现当i=j的时候,实际上是递归的m[i,j]=0, 这个结论非常重要,它其实肩负着递归的终止点和迭代的起始点的角色,没有i=j的判断,我们的递归将无限循环,同时如果采用迭代也无法定义起点。我们接着分析i<j的情况,这时候我们可以使用递归公式:

m[i,j]=m[i,k]+m[k+1,j]+p[i-1] * p[k] * p[j];

如果我们要找到某个k值,使其m[i,j]最小,综合上述的分析,此表达式可以进一步表述为:

矩阵连乘积的动态规划算法,算法,矩阵,动态规划
这时候你可以选择使用普通递归(接近暴力算法),top-down形式的memo递归 或者 bottom-up形式的迭代,都可以对此问题作出合理的解答。

c) Compute the value of the optimal solution - 计算最优值

我们上述完成递归定义的最优解,也有人称之为状态转移方程,意味着问题从某个子状态(底层)转移到父状态(上一层),这个定义是求解所有动态规划问题核心中的核心,如果无法完成上述定义,那么后续的计算最优解和构造解的详细信息就无法完成。

为了获得矩阵链的分割位置,我们可以定义式split数组s[i,j]来记录过程中的k值,k值便是Ai:Aj范围内的最优化的分割点。

c-1) 迭代(bottom-up)计算方法的伪代码

矩阵连乘积的动态规划算法,算法,矩阵,动态规划
在bottom-up问题计算过程中,我们按照长度从小到大进行排列,也就是先从“小”的子问题开始计算,然后再计算较大的子问题,确保每次迭代之前,计算某个问题的前置子问题的解已经求出,从而可以计算当前的某个问题。所以l从小到大求值非常关键。另外就规模和长度而言,子问题都要小于父问题,比如m[i,k]和m[k+1,j]两个子问题长度都小于m[i,j],这就保证了问题求解的前置性可以得到很好满足。

c-2) 递归top-down(带Memo)计算方法的伪代码

矩阵连乘积的动态规划算法,算法,矩阵,动态规划
在这个过程当中,我们特别需要注意的是递归的终点,递归的终点为i=j, 同时可以看到,除了递归本身内部的循环,找到合适的k值外,里面还有两个递归函数,每个递归函数的复杂度为O(n),两个递归函数嵌套调用,其复杂度为O(n2),如果再考虑k=i to j-1的复杂度为O(n),那么整个递归运算的复杂度就为O(n3),与前述的迭代运算复杂度相同。

d) Construct the the optimal solution from computed information 构建最优解的具体信息

很多情况下,动态规划要解决的问题时候都涉及到相应的选择,本例中就涉及到矩阵的划分位置,我们在递归或迭代过程中采用了s[i,j]数组进行了记录,根据s[i,j]的基本信息,我们可以通过循环或者递归构建出最优解的具体方案。就本问题而言,我们构建最优解的伪代码表述为。
矩阵连乘积的动态规划算法,算法,矩阵,动态规划
总结

我们采用了《算法导论》介绍的CRCC步骤对矩阵链的乘法运算的最小标量运算次数进行了分析,这个过程涉及到两个子问题的求解过程。

通过学习,进一步理解了更复杂动态规划的过程以及求解的具体步骤。

参考资料文章来源地址https://www.toymoban.com/news/detail-802960.html

  1. 《Introduction to Algorithm, 4ed, edition》

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

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

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

相关文章

  • 动态规划 | 乘积最大

    原题链接 今年是国际数学联盟确定的“2000——世界数学年”,又恰逢我国著名数学家华罗庚先生诞辰 90 周年。在华罗庚先生的家乡江苏金坛,组织了一场别开生面的数学智力竞赛的活动,你的一个好朋友 XZ 也有幸得以参加。活动中,主持人给所有参加活动的选手出了这样一

    2024年02月03日
    浏览(47)
  • 乘积最大子数组--动态规划

    乘积最大子数组 思路: 看到这个题的时候 要用DP的想法去做这道题 想到遍历到前面的值能不能为后面所用 假设有n个值 我们可以记录一下 第i个值的最大值是什么 怎么用到前面的值取判断 第i个值 可能正数 也可能是负数 如果是正数 那么我们乘以后面第i-1位的最大值 可以得

    2024年02月11日
    浏览(41)
  • 算法 矩阵最长递增路径-(递归回溯+动态规划)

    牛客网: BM61 求矩阵的最长递增路径 解题思路: 1. 遍历二维矩阵每个位置,max求出所有位置分别为终点时的最长路径 2. 求某个位置为终点的最长路径时,使用动态规划dp对已经计算出的位置进行记录 3. 处理某个位置的最长路径时,如果dp[i][j]位置已有值,则直接返回即可,否则

    2024年02月07日
    浏览(41)
  • 【学会动态规划】乘积为正数的最长子数组长度(21)

    目录 动态规划怎么学? 1. 题目解析 2. 算法原理 1. 状态表示 2. 状态转移方程 3. 初始化 4. 填表顺序 5. 返回值 3. 代码编写 写在最后: 学习一个算法没有捷径,更何况是学习动态规划, 跟我一起刷动态规划算法题,一起学会动态规划!  题目链接:1567. 乘积为正数的最长子数

    2024年02月12日
    浏览(41)
  • 动态规划之连续乘积最大子数组 & 连续和最大子数组

    给你一个整数数组 nums ,请你找出一个具有最大和的连续子数组(子数组最少包含一个元素),返回其最大和。 子数组 是数组中的一个连续部分。 示例 1: 输入:nums = [-2,1,-3,4,-1,2,1,-5,4] 输出:6 解释:连续子数组 [4,-1,2,1] 的和最大,为 6 。 示例 2: 输入:nums = [1] 输出:

    2024年02月10日
    浏览(46)
  • 【动态规划】【 矩阵】【逆向思考】C++算法174地下城游戏

    视频算法专题 动态规划汇总 矩阵 逆向思考 恶魔们抓住了公主并将她关在了地下城 dungeon 的 右下角 。地下城是由 m x n 个房间组成的二维网格。我们英勇的骑士最初被安置在 左上角 的房间里,他必须穿过地下城并通过对抗恶魔来拯救公主。 骑士的初始健康点数为一个正整数

    2024年02月03日
    浏览(46)
  • 【组合数学】【动态规划】【前缀和】1735生成乘积数组的方案数

    【动态规划】【状态压缩】【2次选择】【广度搜索】1494. 并行课程 II 动态规划汇总 C++算法:前缀和、前缀乘积、前缀异或的原理、源码及测试用例 包括课程视频 组合数学 给你一个二维整数数组 queries ,其中 queries[i] = [ni, ki] 。第 i 个查询 queries[i] 要求构造长度为 ni 、每个

    2024年02月19日
    浏览(50)
  • 《算法导论》学习(十八)----动态规划之矩阵链乘(C语言)

    本文主要讲解了动态规划中的矩阵链乘问题:给定一个矩阵链,得到它的最小代价计算次序。给出了动态规划方案的分析,并且给出了C语言实现。 给定一个n个矩阵的序列(矩阵链) A 1 , A 2 , A 3 , A 4 , . . . , A n A_1,A_2,A_3,A_4,...,A_n A 1 ​ , A 2 ​ , A 3 ​ , A 4 ​ , ... , A n ​ ,现在

    2024年02月06日
    浏览(44)
  • 动态规划算法学习一:DP的重要知识点、矩阵连乘算法

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

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

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

    2023年04月08日
    浏览(38)

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

支付宝扫一扫打赏

博客赞助

微信扫一扫打赏

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

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

二维码1

领取红包

二维码2

领红包