动态规划之矩阵连乘问题Python实现方法

本文实例讲述了动态规划之矩阵连乘问题Python实现方法。分享给大家供大家参考，具体如下：

给定n个矩阵｛A1,A2,…,An｝，其中Ai与Ai+1是可乘的，i=1,2 ,…,n-1。如何确定计算矩阵连乘积的计算次序，使得依此次序计算矩阵连乘积需要的数乘次数最少。

例如：

A1={30x35} ; A2={35x15} ;A3={15x5} ;A4={5x10} ;A5={10x20} ;A6={20x25} ;

结果为：((A1(A2A3))((A4A5)A6))  最小的乘次为15125。

原问题为n个矩阵连乘，将原问题分解为子问题，即当n等于1,2,3.....时。
n==1时，单一矩阵，不需要计算。最小乘次为0
n==2时，根据n==1时的结果，遍历计算出每相邻两个矩阵的最小乘次
n==3时，根据n==1和n==2时的结果，此时已经求出每相邻1个、2个矩阵的最小乘次，遍历计算出该相邻三个矩阵的最小乘次
依次类推……
当n==n时，根据n==1、2、……n-1时的结果，此时已经求出每相邻1个、2个、3个……n-1个矩阵的最小乘次，由此求出n==n时的最小乘次

每当n增加1时，就利用已求出的子结构来求解此时的最优值。

数学描述如下：

设矩阵Ai的维数为Pi × Pi+1。
设A[i:j]为矩阵AiAi+1....Aj的连乘积，即从Ai到Aj的连乘积，其中，0 <= i <= j <= n-1
设m[i][j]为计算A[i:j]的最小乘次，所以原问题的最优值为m[0][n-1]。
当 i==j 时，单一矩阵，无需计算。m[i][i]=0，i=0,1，....n-1
当 i < j 时，利用最优子结构，计算m[i][j]。即寻找断开位置k(i <= k < j)，使得m[i][k]+m[k+1][j]+Pi*Pk+1*Pj+1最小。

该算法的python实现：

# coding=gbk
# 矩阵连乘问题
__author__ = 'ice'
# row_num 每个矩阵的行数
class Matrix:
  def __init__(self, row_num=0, col_num=0, matrix=None):
    if matrix != None:
      self.row_num = len(matrix)
      self.col_num = len(matrix[0])
    else:
      self.row_num = row_num
      self.col_num = col_num
    self.matrix = matrix
def matrix_chain(matrixs):
  matrix_num = len(matrixs)
  count = [[0 for j in range(matrix_num)] for i in range(matrix_num)]
  flag = [[0 for j in range(matrix_num)] for i in range(matrix_num)]
  for interval in range(1, matrix_num + 1):
    for i in range(matrix_num - interval):
      j = i + interval
      count[i][j] = count[i][i] + count[i + 1][j] + matrixs[i].row_num * matrixs[i + 1].row_num * matrixs[j].col_num
      flag[i][j] = i
      for k in range(i + 1, j):
        temp = count[i][k] + count[k + 1][j] + matrixs[i].row_num * matrixs[k + 1].row_num * matrixs[j].col_num
        if temp < count[i][j]:
          count[i][j] = temp
          flag[i][j] = k
  traceback(0, matrix_num - 1, flag)
  return count[0][matrix_num - 1]
def traceback(i, j, flag):
  if i == j:
    return
  if j - i > 1:
    print(str(i + 1) + '~' + str(j + 1), end=': ')
    print(str(i + 1) + ":" + str(flag[i][j] + 1), end=',')
    print(str(flag[i][j] + 2) + ":" + str(j + 1))
  traceback(i, flag[i][j], flag)
  traceback(flag[i][j] + 1, j, flag)
matrixs = [Matrix(30, 35), Matrix(35, 15), Matrix(15, 5), Matrix(5, 10), Matrix(10, 20), Matrix(20, 25)]
result = matrix_chain(matrixs)
print(result)
# 1~6: 1:3,4:6
# 1~3: 1:1,2:3
# 4~6: 4:5,6:6
# 15125

更多关于Python相关内容感兴趣的读者可查看本站专题：《Python数据结构与算法教程》、《Python加密解密算法与技巧总结》、《Python编码操作技巧总结》、《Python函数使用技巧总结》、《Python字符串操作技巧汇总》及《Python入门与进阶经典教程》

希望本文所述对大家Python程序设计有所帮助。

赞 (0)

相关推荐

  • Python使用稀疏矩阵节省内存实例

    推荐系统中经常需要处理类似user_id, item_id, rating这样的数据,其实就是数学里面的稀疏矩阵,scipy中提供了sparse模块来解决这个问题,但scipy.sparse有很多问题不太合用: 1.不能很好的同时支持data[i, ...].data[..., j].data[i, j]快速切片: 2.由于数据保存在内存中,不能很好的支持海量数据处理. 要支持data[i, ...].data[..., j]的快速切片,需要i或者j的数据集中存储:同时,为了保存海量的数据,也需

  • python使用邻接矩阵构造图代码示例

    问题 如何使用list构造图 邻接矩阵的方式 Python代码示例 # !/usr/bin/env python # -*-encoding: utf-8-*- # author:LiYanwei # version:0.1 # 邻接矩阵 ''' a---b\ | | \ | | c | | / e---d/ 对于无向图顶点之间存在边,则为1,反之则为0 a b c d e a 0 1 0 0 1 b 1 0 1 1 0 c 0 1 0 1 0 d 0 1 1 0 1 e 1 0 0 1 0 观

  • Python 稀疏矩阵-sparse 存储和转换

    Python 稀疏矩阵-sparse 存储和转换

    稀疏矩阵-sparsep from scipy import sparse 稀疏矩阵的储存形式 在科学与工程领域中求解线性模型时经常出现许多大型的矩阵,这些矩阵中大部分的元素都为0,被称为稀疏矩阵.用NumPy的ndarray数组保存这样的矩阵,将很浪费内存,由于矩阵的稀疏特性,可以通过只保存非零元素的相关信息,从而节约内存的使用.此外,针对这种特殊结构的矩阵编写运算函数,也可以提高矩阵的运算速度. scipy.sparse库中提供了多种表示稀疏矩阵的格式,每种格式都有不同的用处,其中dok_m

  • python实现稀疏矩阵示例代码

    python实现稀疏矩阵示例代码

    工程实践中,多数情况下,大矩阵一般都为稀疏矩阵,所以如何处理稀疏矩阵在实际中就非常重要.本文以Python里中的实现为例,首先来探讨一下稀疏矩阵是如何存储表示的. 1.sparse模块初探 python中scipy模块中,有一个模块叫sparse模块,就是专门为了解决稀疏矩阵而生.本文的大部分内容,其实就是基于sparse模块而来的. 第一步自然就是导入sparse模块 >>> from scipy import sparse 然后help一把,先来看个大概 >>> h

  • Python实现打印螺旋矩阵功能的方法

    Python实现打印螺旋矩阵功能的方法

    本文实例讲述了Python实现打印螺旋矩阵功能的方法.分享给大家供大家参考,具体如下: 一.问题描述 输入N, 打印 N*N 螺旋矩阵 比如 N = 3,打印: 1 2 3 8 9 4 7 6 5 N = 4,打印: 1 2 3 4 12 13 14 5 11 16 15 6 10 9 8 7 二.思路 常规法是不断的对数据边界进行判断会很复杂,不妨考虑通过递归的解决每一层的数字. 三.代码 #coding:utf-8 n = int(raw_input('>')) #初始化数组 arr = [

  • Python矩阵常见运算操作实例总结

    本文实例讲述了Python矩阵常见运算操作.分享给大家供大家参考,具体如下: python的numpy库提供矩阵运算的功能,因此我们在需要矩阵运算的时候,需要导入numpy的包. 一.numpy的导入和使用 from numpy import *;#导入numpy的库函数 import numpy as np; #这个方式使用numpy的函数时,需要以np.开头. 二.矩阵的创建 由一维或二维数据创建矩阵 from numpy import *; a1=array([1,2,3]); a1=ma

  • Python实现矩阵转置的方法分析

    Python实现矩阵转置的方法分析

    本文实例讲述了Python实现矩阵转置的方法.分享给大家供大家参考,具体如下: 前几天群里有同学提出了一个问题:手头现在有个列表,列表里面两个元素,比如[1, 2],之后不断的添加新的列表,往原来相应位置添加.例如添加[3, 4]使原列表扩充为[[1, 3], [2, 4]],再添加[5, 6]扩充为[[1, 3, 5], [2, 4, 6]]等等. 其实不动脑筋的话,用个二重循环很容易写出来: def trans(m): a = [[] for i in m[0]] for i in m: f

  • Python创建对称矩阵的方法示例【基于numpy模块】

    Python创建对称矩阵的方法示例【基于numpy模块】

    本文实例讲述了Python创建对称矩阵的方法.分享给大家供大家参考,具体如下: 对称(实对称)矩阵也即: step 1:创建一个方阵 >>> import numpy as np >>> X = np.random.rand(5**2).reshape(5, 5) >>> X array([[ 0.26984148, 0.25408384, 0.12428487, 0.0194565 , 0.91287708], [ 0.31837673, 0.354

  • python实现矩阵乘法的方法

    本文实例讲述了python实现矩阵乘法的方法.分享给大家供大家参考.具体实现方法如下: def matrixMul(A, B): res = [[0] * len(B[0]) for i in range(len(A))] for i in range(len(A)): for j in range(len(B[0])): for k in range(len(B)): res[i][j] += A[i][k] * B[k][j] return res def matrixMul2(A, B):

  • 动态规划之矩阵连乘问题Python实现方法

    动态规划之矩阵连乘问题Python实现方法

    本文实例讲述了动态规划之矩阵连乘问题Python实现方法.分享给大家供大家参考,具体如下: 给定n个矩阵{A1,A2,-,An},其中Ai与Ai+1是可乘的,i=1,2 ,-,n-1.如何确定计算矩阵连乘积的计算次序,使得依此次序计算矩阵连乘积需要的数乘次数最少. 例如: A1={30x35} ; A2={35x15} ;A3={15x5} ;A4={5x10} ;A5={10x20} ;A6={20x25} ; 结果为:((A1(A2A3))((A4A5)A6))  最小的乘次为15125.

  • Python的numpy库中将矩阵转换为列表等函数的方法

    这篇文章主要介绍Python的numpy库中的一些函数,做备份,以便查找. (1)将矩阵转换为列表的函数:numpy.matrix.tolist() 返回list列表 Examples >>> >>> x = np.matrix(np.arange(12).reshape((3,4))); x matrix([[ 0, 1, 2, 3], [ 4, 5, 6, 7], [ 8, 9, 10, 11]]) >>> x.tolist() [[0, 1, 2

  • Python使用min、max函数查找二维数据矩阵中最小、最大值的方法

    本文实例讲述了Python使用min.max函数查找二维数据矩阵中最小.最大值的方法.分享给大家供大家参考,具体如下: 简单使用min.max函数来得到二维数据矩阵中的最大最小值,很简单,这是因为工作需要用到一个东西所以先简单来写了一下: #!usr/bin/env python #encoding:utf-8 ''''' __Author__:沂水寒城 功能:找出来随机生成矩阵中的最大.最小值 ''' import time import random def random_matrix_ge

  • LeetCode 动态规划之矩阵区域和详情

    目录 题目 题解 解题分析 解题代码 题目 矩阵区域和 给你一个 m x n 的矩阵 mat 和一个整数 k ,请你返回一个矩阵 answer ,其中每个 answer[i][j] 是所有满足下述条件的元素 mat[r][c] 的和: i - k <= r <= i + k,j - k <= c <= j + k 且(r, c) 在矩阵内. 示例 1: 输入:mat = [[1,2,3],[4,5,6],[7,8,9]], k = 1输出:[[12,21,16],[27,45,33

  • TF-IDF算法解析与Python实现方法详解

    TF-IDF算法解析与Python实现方法详解

    TF-IDF(term frequency–inverse document frequency)是一种用于信息检索(information retrieval)与文本挖掘(text mining)的常用加权技术.比较容易理解的一个应用场景是当我们手头有一些文章时,我们希望计算机能够自动地进行关键词提取.而TF-IDF就是可以帮我们完成这项任务的一种统计方法.它能够用于评估一个词语对于一个文集或一个语料库中的其中一份文档的重要程度. 在一份给定的文件里,词频 (term frequency, T

  • 机器学习之KNN算法原理及Python实现方法详解

    本文实例讲述了机器学习之KNN算法原理及Python实现方法.分享给大家供大家参考,具体如下: 文中代码出自<机器学习实战>CH02,可参考本站: 机器学习实战 (Peter Harrington著) 中文版 机器学习实战 (Peter Harrington著) 英文原版 [附源代码] KNN算法介绍 KNN是一种监督学习算法,通过计算新数据与训练数据特征值之间的距离,然后选取K(K>=1)个距离最近的邻居进行分类判(投票法)或者回归.若K=1,新数据被简单分配给其近邻的类. KNN算法

  • 总结Java调用Python程序方法

    如何使用Java调用Python程序 本文为大家介绍如何java调用python方法,供大家参考. 实际工程项目中可能会用到Java和python两种语言结合进行,这样就会涉及到一个问题,就是怎么用Java程序来调用已经写好的python脚本呢,一共有三种方法可以实现,具体方法分别为大家介绍: 1. 在java类中直接执行python语句 此方法需要引用org.python包,需要下载Jpython.在这里先介绍一下Jpython.下面引入百科的解释: Jython是一种完整的语言,而不是一个J

  • python多线程方法详解

    处理多个数据和多文件时,使用for循环的速度非常慢,此时需要用多线程来加速运行进度,常用的模块为multiprocess和joblib,下面对两种包我常用的方法进行说明. 1.模块安装 pip install multiprocessing pip install joblib 2.以分块计算NDVI为例 首先导入需要的包 import numpy as np from osgeo import gdal import time from multiprocessing import cpu_c

  • linux下编译boost.python简单方法

    最近项目使用c++操作Python脚本,选用boost.python库.在window下编译安装很顺利,但是在Linux下一直编译不通过,总是提示找不到头文件.linux版本为rhel5.7.后来询问同事,原来是同事将原来系统自带的python2.4删除掉了,然后手动编译安装了python3.3. 换到另外一台机器,重新下载boost,使用以下命令,顺利编译成功 ./bootstrap.sh --with-python=/usr/bin/python ./bjam --build-type=mi

  • Python绑定方法与非绑定方法详解

    本文实例为大家分享了Python绑定方法与非绑定方法,供大家参考,具体内容如下 定义: 绑定方法(绑定给谁,谁来调用就自动将它本身当作第一个参数传入): 1. 绑定到类的方法:用classmethod装饰器装饰的方法. 为类量身定制 类.boud_method(),自动将类当作第一个参数传入 (其实对象也可调用,但仍将类当作第一个参数传入) 2. 绑定到对象的方法:没有被任何装饰器装饰的方法. 为对象量身定制 对象.boud_method(),自动将对象当作第一个参数传入 (属于类的函数,类可以

随机推荐