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)腾讯云开发者
