动态规划之矩阵连乘问题Python实现方法
作者:欠扁的小篮子 发布时间:2022-04-08 02:07:38
本文实例讲述了动态规划之矩阵连乘问题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程序设计有所帮助。
来源:http://www.cnblogs.com/z941030/p/4922118.html
猜你喜欢
- DJANGO_SETTINGS_MODULE使用Django时要通知Django当前使用的是哪个配置文件。可以改变环境变量 DJANGO_S
- 人一旦习惯了某些东西就很难去改,以及各种各样的原因,新的浏览器越来越多,而老的总淘汰不了。增长总是快于消亡导致了浏览器兼容是成了谈不完的话题
- 本文实例讲述了wxPython中listbox用法。分享给大家供大家参考。具体如下:# load a listbox with names,
- 有的时候,我们为了保持网页的美观,需要将较长的文字在一定长度时截断。比如我们希望在列表中显示文章标题的前15个字,那么一个这样的标题:“rs
- zip函数接受任意多个(包括0个和1个)序列作为参数,返回一个tuple列表。具体意思不好用文字来表述,直接看示例:1.示例1:x = [1
- 一,粘包问题详情 1,只有TCP有粘包现象,UDP永远不会粘包你的程序实际上无权直接操作网卡的,你操作网卡都是通过操作系统给用户程序暴露出来
- 最近发现数据库服务器压力很大,CPU经常达到100%。查看进程,发现有大量的sp_cursorclose;1进程信息。网上查了下,出现sp_
- 将数据写入Excel文件中,用python实现起来非常的简单,下面一步步地教大家。一、导入excel表格文件处理函数import xlwt注
- 现在流行的静态博客/网站生成工具有很多,比如 Jekyll, Pelican, Middleman, Hyde 等等,StaticGen 列
- 目前很多公司业务已经上云,使用了大量的云主机。当前大多数云厂商的云主机公网都是采用的eip,也就是内网和外网使用的同一张网卡,所以流量全部经
- 1. 不使用全局变量,适当封装2. 兼容性还行~~3. 代码短,可读性凑合~~呵呵~~~~~a. 拖动效果,16行JS<!DOCTYP
- 格式getopt(args, options[, long_options])1.args表示要解析的参数. 2.options表示脚本要识
- 今天用FrontPage2003,无意中发现一个bug,稍加研究,基本发现这个bug的规律了首先是我的系统版本和Frontpage版本:我的
- 通过本篇内容给大家介绍一下Python实现金融数据可视化中两列数据的提取、分别画、双坐标轴、双图、两种不同的图等代码写法和思路总结。impo
- 1.物体识别本案例实现对特殊颜色物体的识别,并实现根据物体位置的改变进行控制跟随。import cv2 as cv# 定义结构元素kerne
- SQL语句更改表所有者SQL语句更改表所有者单个修改所有者sql语句如下:查询分析器输入:EXEC sp_changeobject
- Filed under 数据库技术Leave a commentSQL Server命令行导数据两种方式bcp和sqlcmd先说一下bcp:
- 在做视觉设计时,如何高效地使用图标是一门学问:该使用什么样的图标?图标该放在哪里?大小如何?图标的使用是否帮助用户更好更快的理解内容,亦或是
- 下面介绍在Linux上利用python获取本机ip的方法.经过网上调查, 发现大致有两种方法, 一种是调用shell脚本,另一种是利用pyt
- Create a Simple API Using Django REST Framework in PythonWHAT IS AN AP