专栏首页Flaneur的文章分享python动态规划解决矩阵连乘

python动态规划解决矩阵连乘

前言

动态规划,自顶向下分解,自底向上求解。

动态规划

        动态规划算法与分治法类似,其基本思想也就是将待求解的问题分解成若干个子问题,先求解子问题,然后从这些子问题的解得到原问题的解,简单概括为自顶向下分解,自底向上求解。         与分治法不同的是,适合于用动态规划法求解的问题,经分解得到的子问题往往不是相互独立的,换句话说,就是前面解决过的子问题,在后面的子问题中又碰到了前面解决过的子问题,子问题之间是有联系的。如果用分治法,有些同样的子问题会被重复计算几次,这样就很浪费时间了。所以动态规划是为了解决分治法的弊端而提出的,动态规划的基本思想就是,用一个表来记录所有已经解决过的子问题的答案,不管该子问题在以后是否会被用到,只要它被计算过,就将其结果填入表中,以后碰到同样的子问题,就可以从表中直接调用该子问题的答案,而不需要再计算一次。具体的动态规划的算法多种多样,但他们都具有相同的填表式。         动态规划的适用场合,一般适用于解最优化问题,例如矩阵连乘问题、最长公共子序列、背包问题等等。

矩阵连乘问题描述

        给定n个矩阵:A1,A2,…,An,其中Ai与Ai+1是可乘的,i=1,2…,n-1。确定计算矩阵连乘积的计算次序,使得依此次序计算矩阵连乘积需要的数乘次数最少。输入数据为矩阵个数和每个矩阵规模,输出结果为计算矩阵连乘积的计算次序和最少数乘次数。         若A是一个p × q的矩阵,B是一个q × r的矩阵,则其乘积C=AB是一个p × r的矩阵。数乘次数是p × q × r.

疑问

A(3 × 5)A(5 × 7)A(7 × 2)的连乘次数和括号划分有关系吗?

(A(3 × 5)A(5 × 7))A(7 × 2) 相乘次数: (3 × 5 7)+(3 × 7 × 2) = 147 A(3 × 5)(A(5 × 7)A(7 × 2)) 相乘次数: (5 × 7 2)+(3 × 5 × 2) = 100

答案很明显是有关系的。

分析

求 A1A2A3…An 定义 AiAi+1…Ak…Aj-1Aj 子列, 可看成是Ai…Ak,Ak…Aj 确定k的位置,然后按照递归的思想来逐步解决 求得结果后,使i=1,j=n原问题即可求解。

建立递归关系(状态转移方程)

设 Ai…Aj相乘 的最小数乘次数存储于m[i][j]中。 S[i][j]存储最佳断开位置。 A1:P0 × P1 A2:P1 × P2 A3:P2 × P3 … Ai:Pi-1 × Pi Ai+1:Pi × Pi+1 … An:Pn-1 × Pn P0 × P1 × P2 … × Pn——n+1个

当i=j时,m[i][j] = 0; 当i<j时,m[i][j] = m[i][k]+m[k+1][j]+Pi-1PkPj k在i,j之间取值,取值范围为i<=k<j 有递推关系如下:

动态规划的最优子结构性质是:

问题的最优解包含了其子问题的最优解。 最优子结构性质是问题可用动态规划法求解的显著特征。 Ai…Ak,Ak+1…Aj的最优划分也包含在Ai…Aj的最优划分中

在计算出最优值m[i][j]后,可递归地由s[i][j]构造出相应的最优解。

python代码实现

import random
from pandas import *
 
input = int(input("输入矩阵数:"))
matrix = [[0] * 2 for i in range(input)]
for i in range(input):                         #生成矩阵
    if i == 0:
        matrix[i][0] = random.randrange(100)
        matrix[i][1] = random.randrange(100)
    else:
        matrix[i][0] = matrix[i-1][1]
        matrix[i][1] = random.randrange(100)
m = [[0] * input for i in range(input)]         #记录连乘次数
s = [[0] * input for j in range(input)]         #记录括号位置
def MatrixMultiplication(inp):
    for i in range(inp):
        m[i][i] = 0
    for r in range(1, inp):
        for i in range(inp-r):
            j = i + r
            m[i][j] = m[i+1][j] + matrix[i][0] * matrix[i][1] * matrix[j][1]
            s[i][j] = i+1
            for k in range(i+1, j):
                judge = m[i][k] + m[k+1][j] + matrix[i][0] * matrix[k][1] * matrix[j][1]
                if judge < m[i][j]:
                    m[i][j] = judge
                    s[i][j] = k+1
def printmatrix(left, right):
    if left == right:
        print("A"+str(left+1), end='')
    else:
        print("(", end='')
        printmatrix(left, s[left][right]-1)
        printmatrix(s[left][right], right)
        print(")", end='')
MatrixMultiplication(input)
dm = DataFrame(m, index=list(range(1, input+1)), columns=list(range(1, input+1)))
ds = DataFrame(s, index=list(range(1, input+1)), columns=list(range(1, input+1)))
print(matrix)
print("数乘次数:\n", dm)
print("括号位置:\n", ds)
print("最终结果:")
printmatrix(0, input-1)

本文参与腾讯云自媒体分享计划,欢迎正在阅读的你也加入,一起分享。

我来说两句

0 条评论
登录 后参与评论

相关文章

  • 推荐系统之矩阵分解(MF)及其python实现

            目前推荐系统中用的最多的就是矩阵分解方法,在Netflix Prize推荐系统大赛中取得突出效果。以用户-项目评分矩阵为例,矩阵分解就是预测出评...

    Flaneur
  • 浅谈机器学习-回归与分类的区别

            机器学习的主要任务便是聚焦于两个问题:分类和回归。本文将浅谈下两者的区别。

    Flaneur
  • 数据集的划分--训练集、验证集和测试集

            在机器学习中,经常提到训练集和测试集,验证集似有似无。感觉挺好奇的,就仔细查找了文献。以下谈谈训练集、验证集和测试集。

    Flaneur
  • java:多字节数据类型数组(double,float,int,long)数组与byte数组的相互转换

    多字节数据类型数组(double,float,int,long)数组数组和byte数组的相互转换都可以基于java.nio.Buffer实现. java.ni...

    用户1148648
  • Python 刷题笔记:随缘题目

    给定一个 m x n 的字符矩阵和字符串 s,在矩阵中每次只能横向、纵向移动一步,不能超出矩阵范围,问:是否可以由矩阵中拼接出 s?

    TTTEED
  • 深入Mybatis源码——执行流程

    上一篇分析Mybatis是如何加载解析XML文件的,本篇紧接上文,分析Mybatis的剩余两个阶段:代理封装和SQL执行。

    夜勿语
  • 微信小程序处理pages的函数比app.js先执行

    我需要先执行app.js里wx.login获取到参数再赋值给页面接口, 问题 页面函数比app.js要先执行 使用promise app.js wxR...

    任我行RQ
  • 必要掌握!Window、WindowManager !

    Window是View的管理者,当我们说创建Window时,一方面指实例化这个管理者,一方面指 用WindowManager.addView()添加view,以...

    胡飞洋
  • 人工智能在保险领域应用的三个重要趋势

    改变正在发生,未来会有更多。保险市场由大型的国有企业和传统产品主导,这些产品几十年来还没有实质性改变。听起来有点耳熟? 人们已经下注了。风险投资家普遍认为保险...

    点滴科技资讯
  • 微信小程序封装api接口

    任我行RQ

扫码关注云+社区

领取腾讯云代金券