浅谈矩阵乘法在优化动态规划中的运用

《浅谈矩阵乘法在优化动态规划中的运用》由会员上传分享，免费在线阅读，更多相关内容在工程资料-天天文库。

1、浅谈矩阵乘法在优化动态规划中的运用信息科姜祥瑜摘要矩阵在数学中应用很广，而在信息学中同样冇很广的应用。木文将阐述矩阵的乘法这一运算在优化动态规划中的运用。关键字快速幕矩阵乘法优化动态规划近儿天，做了一•下PKU3420,对矩阵乘法的应用做了一些探索。题目如下：QuadTilingDescriptionTiredoftheTriTilinggamefinally,Michaelturnstoamorechallengeablegame,QuadTiling:Inhowmanywayscanyoutilea4XN(1WNW

2、IO9)rectanglewith2X1dominoes?Fortheanswerwouldbeverybig,outputtheanswermoduloM(0

3、put11000031000051000000SampleOutput111一、常规算法：1、数学方法利用数学方法，可以找出递推关系式，做出此题。但这不是本文论述的重点，这里略去。2、裸搜裸搜，连测试数据都过不了，而且写起程序來并不简单。3、深搜+位压缩仔细分析题冃发现，虽然n的取值范围很大，但是每行长度一定，只冇4,所以可以用二进制压缩來压缩每一行的状态，优化搜索。虽然搜索得到了优化，但是时间复杂度一样非常的高。4、基于状态压缩的动态规划利用二进制压缩，把每行的状态进行压缩，定义f[i,k]表示前i-1行以前完全覆盖

4、，第i行状态为k的时候的方案总数。F[i,k]=EF[i・l,k[。其中，状态k”可以变为状态k。这个求解过程，一般用dfs实现。F用滚动数组实现，节省内存。时间复杂度为O(nK),K为一个常数。尽管如此，由于N有109Z大,所以即便是0(n)的吋间复杂度，也难以在吋限Z内给出答案。于是，我们必须想方法来对这个动态规划进疔优化。二、矩阵乘法的应用对动态规划的优化，一般有两种方法。一是对状态进行优化，一是对状态转移进行优化。本题的状态表述已经相当优秀，难以再优化了。(其实还是可以优化的，但那涉及到数学，这里不详细说明)于

5、是，我们着眼于对状态转移方程的优化。我们回过头来，看看这个状态转移方程：F[i,k]=EF[i-l,k,]o其中，状态可以变为状态k。这个方程的主要耗时在于，对于每一行，我们都必须用一个dfs过程，来求出对于每个k对应的所冇k-o我们能不能用i种方法，把这个过程省掉呢？这里，我们引入矩阵乘法。1、矩阵的基本知识:所谓矩阵，就是一个的数表，其中n、m都是正整数。如下是一个2*3的矩阵：1234115671一般用A[i,j]表示第i行第j个数。2、矩阵的乘法:定义矩阵A,B,A和B能相乘当且仅当A的大小是a*b,B的大小是

6、b*c,其中a、b、c均为正整数。设矩阵C=AB,则C的大小是a*c,且有：而且，矩阵乘法虽然不满足交换律，但是满足结合律。证明略。直接按照定义进行矩阵乘法吋间复杂度是O(abc),其中a;b;c分别表示两个矩阵大小是a£b以及b£c。将两个N£N的矩阵相乘，朴素算法的时I'可复杂度为O(NT)。其他有一些算法有更低的复杂度，例如Strassen算法时间复杂度约为O(NA2.81)o而现有的算法中理论复杂度最低的是Coppersmith—Winograd算法，时间复杂度约为0(NA2.36)o3、快速幕平吋，我们计算内

7、时，可以利用递归的方式，在O(log2t)的时间复朵度内求出at方法是，先求出t/2/L」二k,若a是偶数,则a"="2,否则存匸"2*a。递归求解，就能在很短的时间内求出沙了。这种方法叫做快速幕。由于短阵乘法满足结合律，所以也町以使用快速幕的方法，在O(log2t)的时间复杂度内求出一个n*n的矩阵的t次幕。4、对动态规划的优化我们将每个F[i]看做一个1*16的矩阵，设法构造一个矩阵A,使得F[i+1]=珂i]*A。这样的矩阵A,我们称为状态转移矩阵。只要我们构造出了这样一个矩阵，再用快速幕求出A5,再用第F[0]

8、去乘，就能得到F[n]To构造状态转移矩阵的方法不难，只需要在之前的DFS过程屮稍加修改就行了。只要深刻理解了矩阵乘法的意义，不难想出DFS的改法。这里留给读者自己思考，可以参考标程。这样，时间复杂度降到了O(log2(),加上滚动数组，空间复杂度也很低，完美解决了这道题冃。typearr=array[O..16,0..16]of