acm竞赛备战资料精选--动态规划之矩阵连乘

《acm竞赛备战资料精选--动态规划之矩阵连乘》由会员上传分享，免费在线阅读，更多相关内容在行业资料-天天文库。

1、动态规划之矩阵连乘新一篇: 动态创建二维数组作者：liguisenBlog：http://blog.csdn.net/liguisen以下内容参考（摘抄）《算法设计与分析》，王晓东编著，清华大学出版社2003年1月第1版。给定n个矩阵{A1,A2,…,An}，其中Ai与Ai+1是可乘的，i=1,2,…,n-1。考察这n个矩阵的连乘积A1A2…An。由于矩阵乘法满足结合律，故计算矩阵的连乘积可以有许多不同的计算次序，这种计算次序可以用加括号的方式来确定。若一个矩阵连乘积的计算次序完全确定，则可以依此次序反复调用2个矩阵相乘的标准算法（有改进的方法，这里不考虑）计算出矩阵连乘积

2、。若A是一个p×q矩阵，B是一个q×r矩阵，则计算其乘积C=AB的标准算法中，需要进行pqr次数乘。矩阵连乘积的计算次序不同，计算量也不同，举例如下：先考察3个矩阵{A1,A2,A3}连乘，设这三个矩阵的维数分别为10×100，100×5，5×50。若按（（A1A2）A3）方式需要的数乘次数为10×100×5＋10×5×50＝7500，若按（A1（A2A3））方式需要的数乘次数为100×5×50＋10×100×50＝75000。下面使用动态规划法找出矩阵连乘积的最优计算次序。1， 设矩阵连乘积AiAi+1…Aj简记为A[i:j]，设最优计算次序在Ak和Ak+1之间断开，则加

3、括号方式为：（（AiAi+1…Ak）（Ak+1…Aj））则依照这个次序，先计算A[i:k]和A[K+1:j]然后再将计算结果相乘，计算量是：A[i:k]的计算量加上A[K+1:j]的计算量再加上它们相乘的计算量。问题的一个关键是：计算A[i:j]的最优次序所包含的两个子过程（计算A[i:k]和A[K+1:j]）也是最优次序。2， 设计算A[i:j]所需的最少数乘次数为m[i][j]。i=j时为单一矩阵，则m[i][i]=0，i

4、A0到A5共6个数组（为了C语言的描述方便，下标从0开始），他们表示如下：//p[0]:第一个矩阵的行数//p[1]:第一个矩阵的列数，第二个矩阵的行数//p[2]:第二个矩阵的列数，第三个矩阵的行数k此时并未确定，需要从i到j-1遍历以寻找一个最小的m[i][j]。我们把这个最小的k放在s[i][j]。 以下是完整实现代码，以一个具体的例子实现，稍加修改即可通用。#includeusingnamespacestd;//////////////////////////////////////////////////////////////////////

5、//////////MatrixChain计算m[i][j]所需的最少数乘次数//并记录断开位置s[i][j]//////////////////////////////////////////////////////////////////////////////voidMatrixChain(int*p,intn,int**m,int**s){for(inti=0;i

6、2435//031425//0415//05//下面行的计算结果将会直接用到上面的结果。例如要计算，就会用到，或者，或者，或者，等等for(intr=1;r

7、p[i]*p[k+1]*p[j+1];if(t