算法分析讲课大纲动态规划之求矩阵连乘积问题

1、 第一小节 动态规划问题最短路径问题 一 在正式提出动态规划法前我们先看一个数学例子： 例1：在 x+x2+x3+xn =a是约束条件下，求的极大值.令 ( 0 ) 令 且可得a-x=x, 所以 x=a/2故 同理 令 所以 a-x=2x , x=a/3所以 f3(a)=用数学归纳法可以证明：fn(a) = , x1=x2=x3=xn=证明：1：n=1 2：设fn(a) = , x1=x2=x3=xn= 成立，则fn+1(a)=max(+fn(a-x)=max( )令 y= y=所以 nx=a-x ,(n+1)x=a x= fn+1(a)=+n=我们刚才的解题策略是：“摸着石头过河”，f2 利

2、用f1的结果，f3又利用f2的结果。类似于游戏中的一个勇士打败了一些敌人后得到一件武器，然后去打败另一个强大一些的对手，得到一件更好的武器，接着打败更强大的敌人。最后取得胜利。 在实际生活中，有这么一类问题，它们的活动过程可分为若干个阶段，而且在任一阶段 后的行为仅依赖于第I阶段的过程状态，而与I阶段之前的过程如何达到这种过程如何达到这种状态的方式无关，这样的过程就构成了一个多阶段决策过程。在50年代，贝尔曼（Richard Bellman）等人根据这类问题的多阶段决策的特性，提出了解决问题的“最优性原理”从而创建了最优化问题的一种最新的算法设计方法动态规划。分治法和动态规划法的比较动态规划算

3、法与分治法类似，其根本思想也是将待求解问题分解成若干个子问题，先求解子问题，然后从这些子问题的解得到原问题的解，与分治法不同的是，适合于用动态规划法求解的问题，经分解得到的子问题往往不是互相独立的.以从16个数据中找出最大者为例，说明 分治法的“静”和动态规划法的“动”的区别。下面我们以具体的例子来说明如何运用动态规划算法来求解问题，并分析可用动态规划算法解的问题的所应具备的一般特征。对教材68页上的里子给予简要说明（因为书上的文字叙述有些含混晦涩，对符号的说明不清晰） y1OAF 2 K 3 P 1 S 2 U 下面精讲一个例子 2 1 2 2 3C 2 G 3 L 4 Q 5 T 3 4

4、1 2 3 D H M R 2 2 1 3 4 3 2 31. 介绍这个图的特点.从而说明从O到A的最短路径必由7段而不是更多或更少段组成。其行进路线必然是x和y单调递增的（非严格单调）。从O(0,0)到U（4，3）点的每一条路径对应于由4个x上的和3个y上的字符构成的字符串，这种字符串的数目为C=35.如果采用穷举法进行搜索，需要进行35*6=210次加法，34次比较。2. 下面我们采用动态规划法来解决这一问题。令O为起点到U的最短距离为Do，以A为起点到U的最短距离为DA - - - ,用dij表示（i , j）边的长度。 显然Ds=dsu=2,Dt=dTU=3,DQ=min2+2,5+3

5、=4DP=1+Ds=1+2=3DR=3+DT=3+3=6DL=minDlq+DQ,dLP+DP=min4+DQ,2+Dp=min4+4,2+3=5Dk=3+Dp=3+3=6DM= min2+DQ,4+DR=min2+4,4+6=6DN=4+DR=4+6=10DF=2+DK=2+6=8DG=min1+DK,3+DL=min1+6,3+5=7DH=min1+5,1+6=6DJ=min3+DM,3+DN=min3+6,3+10=9DC=min2+DF,2+DG=min2+8,2+7=9DD=min4+DG,2+DH=min4+7,2+6=8DE=min1+DH,2+DJ=min1+6,2+9=7DA

6、=min3+DC, 2+DD=min3+9,2+8=10DB=min2+DD,3+DE=min2+8,3+7=10Do=min1+DB,2+DA=min1+10,2+10=11共进行了29次加法，12次比较。由Do=1+DB=11回溯，可得到最短路径为O>B-àD->HàL>P-àS-àUO-àB-àE-àH-àL-àP-àS-àU推广到x轴m段y轴n段的情形：用动态规划法需要做2mn+（m+n-2）次加法，mm次比较；而如果用穷举法，需要次加法， 次比较。若m=n,

7、 动态规划法要做2n2 +2n-2次加法，n2 次比较，因此复杂度为O(n2) ;而穷举法需要次加法， 次比较 ，>O(n2n+1)。第二小节 动态规划问题货郎担问题 1. 动态规划方法的思想- 动态规划是一种将问题实例分解为更小的、相似的子问题，并存储子问题的解而避免计算重复的子问题，以解决最优化问题的算法策略。2. 货郎担问题：- 某售货员要到若干个村庄售货，各村庄之间的路程是已知的，为了提高效率，售货员决定从所在商店出发，到每个村庄售一次货然后返回商店，问他应选择一条什么路线才能使所走的总路程最短？实质 - 从某点出发,遍历其余点,再回到原点,求总路径消耗最少的路线.例设共有4个要

8、经过的点- -1，2，3，4-各个点之间的花费如下： 1->2 : 10; 1->3 : 15; 1->4 : 20; 2->1 : 5; 2- >3 : 9; 2- >4 : 10; 3->1 : 6; 3- >2 : 13; 3- >4 : 12; 4->1 : 8; 4- >2 : 8; 4- >3 : 9; （最短路径 ：1- >2->4->3->1） 1 2 3 42456758587853.问题的解决1.) 问题的描述:l T(V1; V) - 表示从V1出发,经过顶点集合V中的点各一次

9、,再回到点 V1的最短路径. 2.) 动态规划函数: T(vi; V) = mindij + T(vj ; V-vj) (vj 属于 V)l T(vi; V):就是 从V中任何一点vi出发, 经过V中的点各一次,再回到 点 vi的最短路径.l Dij:表示从点vi出发,到某点vj的耗费(有方向性).l 注:这是一个递归定义的函数,关键是每次的函数T(vi; V)它所处理的点 集逐渐减少.3.)实例:(如上图)求从v1出发的货郎担问题. 解: T(v1; V)= T(v1; v1, v2, v3, v4)= min d12 + T(v2; v3, v4),d13 + T(v3; v2, v4),

10、 d14 + T(v4; v2, v3) /实例意义:初始的货郎担问题是从点v1出发,涉及其余3点v2,v3,v4;那按照动态规划“分而治之”的思想(这里就是把问题规模缩小,而问题的数量可多一些),我们可先计算分别从v2, v3, v4出发,涉及(v2, v3, v4)三点的三条货郎担路线的路耗,再各自加上相应的dij,这样,最后就得到3个总路耗,再做一个min运算,就可求出初始问题的解.T(v2; v3, v4)= min d23 + T(v3; v4), d24 + T(v4;v3)T(v3; v4)= d34 + T(v4, )T(v4; v3)= d43 + T(v3, )T(v4,

11、)= d41T(v3, )= d31T(v3; v4)= d34+ d41=6+9=15T(v4; v3)= d43+ d31=8+8=16T(v2; v3, v4)= min d23 + d34+ d41, d24 + d43+ d31= min 7+6+9, 6+8+8=22同理:T(v3; v2, v4)= min d32 + d24+ d41, d34 + d42+ d21= min 5+6+9, 6+5+4=15T(v4; v2, v3)= min d42 + d23+ d31, d43 + d32+ d21= min 5+7+8, 8+5+4=17则最后: T(v1; v1, v2

12、, v3, v4)= min d12 + T(v2; v3, v4),d13 + T(v3; v2, v4), d14 + T(v4; v2, v3) = min 2+22,5+15,8+17 =20所选的路线是:1->3->4->2->1第三小节 动态规划问题投资问题一 问题描述：投资问题就是考虑如何把有限资源分配给若干个工程的问题。二 给定条件：1.资源总数（设为a） 2.工程个数（设为n） 3.每项工程投资的利润（不同数目的投资所获得的利润不同），用向量Gi (1in)表示。 n三 问题求解：求出一个a的分划x1, x2,., xn,0xia, 且 xi a,使得

13、以下式表示的利润为最大： i=1 n G(a)= Gi (xj) 0xja i=1 其中Gi (xj)是把资源xj分配给第I项工程能获得的最大利润。四 问题分析： i）若Gi 是x的线性函数，则为线性规划问题。ii）若Gi 不是线性函数，则要用动态规划求最佳分配。用总量为a的资金在n个项目上进行投资以取得最大的利润，可以转化为下述的问题：将总量资金a分为两部分z(0za)及a-z，分别用在第n个项目及剩下的n-1个项目上进行投资，获得的最大利润G(a)=max(第n个项目上资金量为z的利润与用a-z的资金在n-1个项目上投资的最大利润之和)。这样问题就转化为”求用a-z的资金在n-1个项目上投

14、资的最大利润”，与我们的原问题” 求总量为a的资金在n个项目上进行投资以取得最大的利润”性质完全一致，仅仅是问题的规模比原问题少了一个项目，如此将问题的规模细化下去，一直到项目数为1为止，则问题迎刃而解。我们在对原问题进行”分而治之”的过程当中，最终实现了最优化的求解。五 问题解决方案：设fi(x)：前i个项目共投资资金x所产生的最大利润；di(x)：产生fi(x)在项目i上的资金数。由上分析可给出投资问题的动态规划函数方程：f1(x)= G1(x);d1(x)=x x=0,1afi(x)=maxGi(z)+ fi-1(x-z) z=0,1x; x=0,1adi(x)=产生fi(x)的z值 i

15、=2,3.n;六 问题举例：设有8（万元）的投资可分给3个项目，每个项目的利润函数如下表（一）所示： 表（一）利润函数表x0 1 2 3 4 5 6 7 8 G1(x)G2(x)G3(x)0 5 15 40 80 90 95 98 1000 5 15 40 60 70 73 74 750 4 26 40 45 50 51 52 53解题步骤：第1步：设项目1是可用于投资的唯一项目，把x万元投资到项目1，利润为 f1(x)= G1(x) 这就得到表（二）的最后一行的值，投资到项目1的最优数量为 d1(x)=x x=0,18；第二步：设资金8万元可投资到项目1和项目2。由第1步已知任意数量的资源投

16、资到项目1所产生的最优，所以下到各种和式中的最大值就是目前情况下的最大利润： G2(0)+ f1(8)=0+100=100 G2(1)+ f1(7)=5+98=103 G2(2)+ f1(6)=15+95=110G2(3)+ f1(5)=40+90=130 G2(4)+ f1(4)=80+60=140G2(5)+ f1(3)=70+40=110 G2(6)+ f1(2)=73+15=88G2(7)+ f1(1)=74+5=79 G2(8)+ f1(0)=75+0=75 可见将8万元投资于项目1和2 ，所能获得的最大利润f2(8)及投资到项目2的最优数量分别为：f2(8)=maxG2(z)+ f

17、1(8-z)=140 z=0,18d2(8)=4；第三步：假设以任意x(8)万元投资到项目1和2，对每个x值，计算从项目1和2所产生的最优利润，即：f2(x)=maxG2(z)+ f1(x-z) z=0,1x;投资到项目2的数量为d2(x)=产生f2(x)的z值。得到所表（二）的结果。第四步：将8万元投资于3个项目，这就是原问题。则f3(8)应取下述各量的最大值： G3(0)+ f2(8)=0+140=140 G3(1)+ f2(7)=4+120=124 G3(2)+ f2(6)=26+96=126G3(3)+ f2(5)=40+90=130 G3(4)+ f2(4)=45+80=125G3(

18、5)+ f2(3)=50+40=90 G3(6)+ f2(2)=51+15=66G3(7)+ f2(1)=52+5=57 G3(8)+ f2(0)=53+0=53 因此将8万元以最优方式投资到3个项目时所获得的最大利润及投资到项目3的分别为： f3(8) =G3(0)+ f2(8)=140 d3(8)=0； 表（二）向项目1，2投资所到的利润表x0 1 2 3 4 5 6 7 8 f1(x)d1(x)f2(x)d2(x)0 5 15 40 80 90 95 98 1000 1 2 3 4 5 6 7 8 0 5 15 40 80 90 95 120 1400 1 2 3 0 0 0 3 4 因

19、为d3(8)=0；故剩下8万元要最优的投资到项目1和2中。由表（二）易知，当项目1和2 可用时，d2(8)=4表示 投资到项目2的最优数量，因此项目1应投资剩下的4万元。第四小节 动态规划问题矩阵连乘积问题一、求矩阵的连乘积1、一个实际的例子（体现了乘积顺序对矩阵连乘的重要性）a) 例子 在讲这个问题之前先举个例子MA *B *C ，其中A=( aij)10*100 B=( bij)100*5 C=( cij)5*50根据矩阵乘法的结合律，则有M（A *B ）*C和MA *（B*C）两个方案但是可以发现他们所做的乘法的次数是不相同的以M（A *B ）*C为例令AB=M=(mij)10*5，因此

20、mij（其中,I=1,210；j1，25）故计算AB共进行了10*5*100=5000次乘法M= MC（其中,I=1,210；j1，250）故计算MC共进行了10*5*50=2500次乘法总共需要 500025007500次乘法同理，MA *（B*C）方案需要 100*5*50+10*100*50=25000+50000=75000次乘法，两者相差近十倍！B）结论不难得出，矩阵相乘的结合方式对计算结果所需要的乘法操作总数有很大的影响。但是M相乘的个数增多至n个，求出所有的可能结合方式的乘法操作次数，再从中找出操作次数最小的结合方式，其工作量是惊人的! 对于n个矩阵的连乘积，设有P（n）个不同的

21、计算次序。由于我们可以先在第k和k1个矩阵之间将原矩阵序列分为两个矩阵子序列，k1，2，n1。然后分别对这两个矩阵子序列完全加括号。最后对所得结果加括号，得到原矩阵序列得一种完全加括号方式。由此，可以得到关于P（n）得递归式如下：P（n）=1 , n=1时P（n） ，n>1时解此递归方程可得，P（n）C（n1）其中，C（n）P（n）=P(1)P(n-1)+P(2)P(n-2)+P（n1）P（1）P（2）1P（n）这样的话这种枚举的方法实际上是不可能的。这里用动态规划的方法可以提供一种O（n3）的算法。如果可以找出乘法次数最少的的结合方式来计算的话，那么就减少了不少工作量。2、动态规划法求

22、解的方案（还是以一个实际的例子来讲动态规划法的算法）a） 算法分析举例最佳的乘积方案是（A1A2Ai）（AI1AI2An ）则A1A2Ai和AI1AI2An必须达到最佳。令mij为计算乘积AIAI1Aj的最少乘法数，显然有mij mii0， I，j1，2n其中mik是求AIAI1Ak乘积时最佳方案的乘积数目，m会1；j是求Ak1Ak2Aj乘积时的最佳方案的乘积数，AIAI1Ak是ri*rk+1阶矩阵，Ak1Ak2Aj是rk+1*rj+1矩阵，rirk+1 rj+1是求（AIAI1Ak）（Ak1Ak2Aj）所需的乘数法利用上式将之变为多段判决即可以计算以下4个矩阵为例A130*35，A235*1

23、5，A315*5，A45*10 n4为例m1230*35*15=1575030*35*15=15750m2335*15*5=2625m3415*5*10=750m13min m12+30*15*5, m23+30*35*5= min 15750+2250, 2625+5250=7875m24min m23+30*5*10, m34+35*15*10= min 2625+1750, 750+5250=4375m14min m12+ m34+30*15*10, m24+30*35*10, m13+30*5*10= min 15750+4500,4375+10500, 7875+30*5*10=93

24、75故最佳方案为：（A1（A2 A3）A4）J=1 2 3 4I=1 2 34 0m12m13m140m23m240m340B） 算法时间空间复杂性分析计算顺序是沿着对角线进行的。如果编程的话，程序如下（！c程序只供参考，不作为讲课内容）void MatrixChain (int p, int n, int n*m, int *s) for (int r=2; r<=n; r+) for (int i=1; i<=n-r+1; i=i+) int j=I+r-1; mij=mi+1j+Pi-1*pi*pj; sij=I; for (int k=i+1; k<j; K+) in

25、t t=mik+mk+1j+pI-1*pk*pj; if (t<mij mij=t; sIj=k; 计算量主要取决于程序中对r，I，k的三重循环。循环体内的计算量为O（1），而三重循环的总次数为O(n3),由此该算法的计算时间上界为O(n3)，算法所占用的空间显然为 O(n2)，显然比穷举搜索法有效的多。二、动态规划的基本要素（综合讲过的几个例子,总结算法的基本要素）从以上的最优计算次序的动态规划算法可以看出，这些算法的有效性依赖于问题本身所具有的两个重要性质：最优子结构性质和子问题重叠性质。从一般意义上讲，问题所具有的这两个重要的性质是该问题可用动态算法求解的基本要素。1最优子结构设计

26、动态规划算法的第一步通常是要刻画最优解的结构。当问题的最优解包含了其子问题的最优解时，称该问题具有最优子结构性质。问题的最优解子结构性质提供了该问题可用动态规划求解的重要线索。比如，在矩阵连乘积最优解计算次序问题中，我们注意到，若A1、A2An的最优完全加括号方式在Ak和AK1之间将矩阵链断开，则由此确定的子链A1、A2Ak和AK1、AK2An得完全加括号方式也最优。即该问题具有最优解子结构性质。在分析该问题得最优解导出得其子问题得解不是最优的，然后再设法说明在这个假设下可构造出一个比原问题最优解更好的解，从而导致矛盾。在动态规划算法中，问题的最优子结构性质使我们能够自底向上的方法递归的从子问题地最优解逐步构造出整个问题地最优解。同时，它也使我们能在相对小的子问题空间中考虑问题。例如，在矩阵连乘积最优解次序问题中，子问题空间是输入地矩阵链的所有不同子链组成的。所有不同子链的个数为O（n2），因而子空间规模为O（n2）2重叠子问题可用动态规划算法求解问题应具备地另一基本要素是子问题地重叠性质。在用递归算法自顶向下解此问题时。每次产生地子问题并不总是新问题，有些子问题被反复计算多次。多态规划算法正式利用了这种子问题地重叠性质，对每个问题只解一次，尔后将其解保存在一