前往小程序,Get更优阅读体验!
立即前往
首页
学习
活动
专区
工具
TVP
发布
社区首页 >专栏 >[动态规划] 矩阵链乘法问题

[动态规划] 矩阵链乘法问题

作者头像
racaljk
发布2018-08-31 11:04:34
1.8K0
发布2018-08-31 11:04:34
举报
文章被收录于专栏:racaljk

什么是矩阵链乘法(Matrix Chain Multiplication)

矩阵链乘法问题是指给定一串矩阵序列M₁M2..Mn,求至少需要进行多少次乘法运算才能求得结果

比如对于这个M₁M₂M₃的矩阵链, 

我们可以先计算M₁M₂然后结果乘以M₃,也可以M₂M₃先算,然后乘以M₁,为了表达方便,可以用括号表示计算顺序。 矩阵链M₁M₂M₃有两种计算顺序:((M₁M₂)M₃)和(M₁(M₂M₃))。 那么不同计算顺序有什么区别? 对于((M₁M₂)M₃): 

对于(M₁(M₂M₃)): 

我们要做的就是找到让乘法运算最少的计算顺序,换言之就是找一种加括号方式,使得最后乘法运算最少

状态转移方程

现用 optimal(M₁M₂) 表示M₁M₂最优计算成本 cost(M₁M₂) 表示M₁M₂计算成本optimal(M₁M₂)=optimal(M₁)+optimal(M₂)+cost(M₁M₂)

optimal(M₁)和optimal(M₂)均为零;同理

optimal(M₂M₃)=optimal(M₂)+optimal(M₃)+cost(M₂M₃)

(M₁M₂M₃)有两种加括号方式, 它的最优计算成本是这两种加括号方式中最优的那个,即:optimal(M₁M₂M₃)=min{optimal((M₁M₂)M₃),optimal(M₁(M₂M₃))}

显然,这里说的正是动态规划思想:我们从局部最优解出发,逐渐构造出大问题(同时局部最优解还有重叠,可以保存计算结果免去后面计算)。状态方程已经构造出来了,下面就是实际的实现

实现

代码语言:javascript
复制
#include <iostream>
#include <algorithm>
#include <climits>

int dp[1024][1024] = { 0 };

struct Matrix {
    int row;
    int column;
};

int matrixChainCost(Matrix *ms, int n) {
    for (int scale = 2; scale <= n; scale++) {
        for (int i = 0; i <= n - scale; i++) {
            int j = i + scale - 1;
            dp[i][j] = INT_MAX;
            for (int k = i; k < j; k++) {
                dp[i][j] = std::min(dp[i][j], dp[i][k] + dp[k+1][j] + (ms[i].row*ms[k].column*ms[j].column));
            }
        }
    }
    return dp[0][n - 1];
}

int main() {
    int n;
    std::cin >> n;  //n个矩阵组成的矩阵链
    Matrix *ms = new Matrix[n];
    for (int i = 0; i<n; i++) {
        std::cin >> ms[i].row;      //第i个矩阵的行数
        std::cin >> ms[i].column;   //第i个矩阵的列数
    }
    std::cout << matrixChainCost(ms, n);
    system("pause");
    return 0;
}
本文参与 腾讯云自媒体同步曝光计划,分享自作者个人站点/博客。
原始发表:2018-01-30 ,如有侵权请联系 cloudcommunity@tencent.com 删除

本文分享自 作者个人站点/博客 前往查看

如有侵权,请联系 cloudcommunity@tencent.com 删除。

本文参与 腾讯云自媒体同步曝光计划  ,欢迎热爱写作的你一起参与!

评论
登录后参与评论
0 条评论
热度
最新
推荐阅读
目录
  • 什么是矩阵链乘法(Matrix Chain Multiplication)
  • 状态转移方程
  • 实现
领券
问题归档专栏文章快讯文章归档关键词归档开发者手册归档开发者手册 Section 归档