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

编辑：rootadmin

推荐整理分享动态规划之矩阵连乘问题Python实现方法(动态规划之矩阵连乘)，希望有所帮助，仅作参考，欢迎阅读内容。

文章相关热门搜索词:动态规划矩阵连乘问题时间复杂度,动态规划矩阵连乘问题时间复杂度,动态规划矩阵连乘,动态规划矩阵连乘问题例题,动态规划之矩阵连乘,动态规划之矩阵连乘问题,动态规划矩阵连乘问题,动态规划矩阵连乘,内容如对您有帮助，希望把文章链接给更多的朋友！

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

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

例如：

A1={x} ; A2={x} ;A3={x5} ;A4={5x} ;A5={x} ;A6={x} ;

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

原问题为n个矩阵连乘，将原问题分解为子问题，即当n等于1,2,3.....时。n==1时，单一矩阵，不需要计算。最小乘次为0n==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实现：

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

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

python输入错误密码用户锁定实现方法小编给大家带来了用python实现用户多次密码输入错误后，用户锁定的实现方式，以及具体的流程，让大家更好的理解运行的过程。1.新建一个文件，用以

Python搜索引擎实现原理和方法如何在庞大的数据中高效的检索自己需要的东西？本篇内容介绍了Python做出一个大数据搜索引擎的原理和方法，以及中间进行数据分析的原理也给大家

Python中用psycopg2模块操作PostgreSQL方法其实在Python中可以用来连接PostgreSQL的模块很多，这里比较推荐psycopg2。psycopg2安装起来非常的简单（pipinstallpsycopg2），这里主要重点介绍下如何使用。安