动态规划之矩阵连乘问题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,3.....时。 每当n增加1时,就利用已求出的子结构来求解此时的最优值。 数学描述如下: 设矩阵Ai的维数为Pi × Pi+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,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程序设计有所帮助。 (编辑:李大同) 【声明】本站内容均来自网络,其相关言论仅代表作者个人观点,不代表本站立场。若无意侵犯到您的权利,请及时与联系站长删除相关内容! |