矩阵链相乘

矩阵链相乘

动态规划

  • 什么是动态规划
    • 通过把复杂的原问题分解为相对简单的子问题的方法
  • 动态规则有哪些特征
    • 重叠子问题:子问题重复出现
    • 最优子结构:一个问题的最优解包含其子问题的最优解
    • 无后效性:某阶段的状态一旦确定,则此后过程的演变不再受此前各种状态及决策的影响
  • 动态规则问题的解决步骤
    • 确定子问题
    • 确定状态转移方程
    • 确定边界条件

题目

  • 给定n个矩阵序列:(A1,A2,A3,...,An)。计算他们的乘积,使得乘法次数最小
  • 矩阵相乘满足结合律,两个矩阵相乘它们的乘法次数是固定的
    • AabAbc矩阵相乘最小乘法次数:a * b * c

分析

  • 例如:p=[5,10,3,12,5],A1->5 * 10(A1矩阵5行10列,以下同理),A2->10 * 3,A3->3 * 12,A4->12 * 5,矩阵相乘的计算代价为405,最优方案为((A1A2)(A3A4))
  • 共有4种计算方式:A1A2A3A4,A1(A2A3)A4,A1A2(A3A4),A1(A2(A3A4))
  • 列出下表,其中m[i,j]表示Ai~j的最小乘法次数
A1A2A3A4 A1(A2A3)A4 A1A2(A3A4) A1(A2(A3A4))
第一步 A1A2 A2A3 A3A3 A3A3
第二步 m[1,2]*A3 A1*m[2,3] A1A2 A2*m[3,4]
第三步 m[1,3]*A4 m[1,3]*A4 m[1,2]*m[3,4] A1*m[2,4]
  • 符号定义:

  • 用动态规划的步骤解决上面的问题

  • 子问题分析,用二维数组做为存储结构,则矩阵间相乘的最优次数如下:

矩阵个数 1 2 3 4
1 0 m[1,2] m[1,3] m[1,4]
2 0 0 m[2,3] m[2,4]
3 0 0 0 m[3,4]
4 0 0 0 0
  • 在此数组中,最终目标是求出m[1,4],也就是A1A2A3A4四个矩阵相乘的最优乘法次数。设想可以通过已经得出的结果求出最终结果,在数组中利用对角线的顺序求解,如下图所示:

    • 第一次求出第一条对角线上的结果:m[1,2]、m[2,3]、m[3,4]

    • 第二次求出第二条对角线上的结果:m[1,3]、m[2,4]

    • 第三次求出第三条对角线上的结果:m[1,4]

  • 第一条对角线上的结果是都需要求的,第二条和第三条可以根据已经得出的值进行计算,例如:

    • m[2,4] = min(m[2,2]+m[3,4]+p1 * p2 * p4, m[2,3]+m[4,4]+p1 * p3 * p4)
    • m[1,4] = min(m[1,1]+m[2,4]+p0 * p1 * p4,m[1,2]+m[3,4]+p0 * p2 * p4,m[1,3]+m[4,4]+p0 * p3 * p4)
  • 用i表示行,j表示列,d表示对角线,

    • j = d + i
    • i的最小范围为1,最大范围 = 矩阵个数-d
    • d的范围 = 1 ~ 矩阵个数-1

代码实现

  // 最小乘法次数
function MatrixChain(p){
    let num = p.length-1// 矩阵的个数
    let m = [] // 用来存储m[i,j],表示Ai~j的最小乘法次数
    let s = [] // 存储矩阵下标
    let d //对角线
    let template // 相乘次数

    for(let i = 1; i <= num; i++){
        m[i] = []
        m[i][i] = 0

        s[i] = []
        s[i][i] = 0
    }

    for(d = 1; d <= num-1; d++){  // d的范围 = 1 ~ 矩阵个数-1
        for(let i = 1; i <= num - d; i++){ // i的最小范围为1,最大范围 = 矩阵个数-d
            j = i + d // j = d + i
            m[i][j] = Number.MAX_SAFE_INTEGER; 
            for(let k = i; k <= j - 1; k++){
                template = m[i][k] + m[k+1][j] + p[i-1]*p[k]*p[j]; 
                if(template < m[i][j]){
                    m[i][j] = template
                    s[i][j] = k
                }
            }
        }
    }
    printOrder(s, 1, num); 
    return m[1][num]
}

// 最优解的括号顺序
function printOrder(s,i,j){
    if (i == j) {
        console.log("A[" + i + "]");
    } else {
        console.log("(");
        printOrder(s, i, s[i][j]);
        printOrder(s, s[i][j] + 1, j);
        console.log(")");
    } 
}

let p=[10, 100, 5, 50]
console.log('最小乘法次数:',MatrixChain(p))

复杂度

  • 时间复杂度
    • 计算代价的时间 O(n^3)
    • 构造最优解的时间 O(n)
    • 总的时间复杂度 O(n^3)
  • 空间复杂度 O(n^2)

参考资料

  • javascript数据结构与算法
  • 出自:原址
原文链接:juejin.im

上一篇:[从零实践03-后台] 自定义hooks
下一篇:Vue源码解析:模板编译Parse(一)

相关推荐

  • 关于矩阵的理解(不定时补充)

    这里通过数学的角度理解一下矩阵的平移,缩放和旋转 假设一个向量为vec=(x,y,z,w), 其中w=1表示向量,w=0表示方向 如果w=0,那么平移就没有意义,也就是说平移一个方向没有意义,为何可以...

    2 年前
  • 使用状态机解决两个leetcode螺旋矩阵问题[54,59]

    第一题:顺时针输出螺旋矩阵: 螺旋矩阵 在本题中,这个状态就是当前的矩阵坐标和运行方向,而状态的转移遵循题目的限制规则: 顺时针旋转走位,这表示 如果当前是向右行走,那么接下来只能是向右或...

    21 天前
  • 一个超级炫的矩阵运动库,了解一下?

    DEMO DEMO jsfiddle 原理说明 用 Matrix 生成一个二维矩阵,通过规定的运动形式,确定出需要运动的点,触发特定事件,在特定时间后进行下一轮的运动,确定运动点,触发事件,直到所有的...

    2 年前
  • 【刷算法】顺时针打印矩阵

    题目描述 输入一个矩阵,按照从外向里以顺时针的顺序依次打印出每一个数字,例如,如果输入如下矩阵: 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 ...

    2 年前
  • 【leetcode】#542.01 给定一个由 0 和 1 组成的矩阵,找出每个元素到最近的 0 的距离

    题目描述: 给定一个由 0 和 1 组成的矩阵,找出每个元素到最近的 0 的距离。两个相邻元素间的距离为 1 。 示例 1: 输入: 0 0 0 0 1 0 0 0 0输出: 0 0 0 0 ...

    7 个月前
  • 《前端图形学从入门到放弃》002 教练我想学矩阵

    本文大纲矩阵和线性变换是什么?webgl如何实现缩放和旋转?平移不是线性变换,那该怎么办?webgl如何实现平移?今天的主菜是“矩阵”在上一篇中我们已经实现了使用webgl绘制图形这个小目标《前端图形...

    3 个月前
  • js实现大数相乘

    昨晚用js写了个大数相乘的函数,模拟写竖式计算,但性能太低,算得很慢。后来在leetCode看了高票答案,赞叹算法的神奇。传送门=&gt;LeetCode-Multiply Strings 引用高票答...

    2 年前
  • jQuery模拟黑客帝国矩阵效果实例

    本文实例讲述了jQuery模拟黑客帝国矩阵效果的方法。分享给大家供大家参考。具体实现方法如下: html部分如下: &lt;div id="container"&gt; &lt;div style...

    4 年前
  • canvas 中的变换矩阵

    上一期的《canvas 基础及实现贝塞尔曲线动画》,我们回顾了 canvas 的基础操作和贝塞尔曲线实现原理;这一次,我们来补充下前一篇遗留下来的基础知识点之一:transform 变换矩阵。

    9 个月前
  • WebGL学习06-投影,视图和模型矩阵

    前言 为了更好的模拟3D真实场景,引入了投影矩阵(Projection),视图矩阵(View),模型矩阵(Model)3个概念,通过在Vertex Shader中使用透视矩阵 * 视图矩阵 * 模型矩...

    1 个月前

官方社区

扫码加入 JavaScript 社区