第3章动态规划法.

算法设计与分析1第三章动态规划学习要点理解动态规划算法的概念。掌握动态规划算法的基本要素（1）最优子结构性质（2）重叠子问题性质理解动态规划算法与贪心算法的差异掌握设计动态规划算法的步骤。通过下面的应用范例学习动态规划算法设计策略（1）最短路径（2）矩阵连乘（3）凸多边形最优三角剖分（4）最长公共子序列算法设计与分析2算法设计与分析3问题的分解将待求解问题分解为若干子问题，通过子问题的解得到原问题的解，这是问题求解的有效途径。但是如何实施分解？分治策略的基本思想是将规模为n的问题分解为k个规模较小的子问题，各子问题相互独立但与原问题求解策略相同。并不是所有问题都可以这样处理。问题分解的另一个途径是将求解过程分解为若干阶段（级），依次求解每个阶段即得到原问题的解。通过分解得到的各子阶段不要求相互独立，但希望它们具有相同类型，而且前一阶段的输出可以作为下一阶段的输入。这种策略特别适合求解具有某种最优性质的问题。贪心法属于这类求解策略：对问题P(n)，其求解过程中各贪心选择步骤构成决策序列D=D1,D2,..Dk。Di的最优性仅依赖于D1,D2,..Di-1。贪心法不保证决策序列D最后求出解的最优性。算法设计与分析4动态规划动态规划也是一个分阶段判定决策过程，其问题求解策略的基础是决策过程的最优原理：为达到某问题的最优目标T，需要依次作出决策序列D=D1,…Dk。如果D是最优的，则对任意i(1≤ik)，决策子序列Di+1,…Dk也是最优的，即当前决策的最优性取决于其后续决策序列的是否最优。由此追溯至目标，再由最终目标决策向上回溯，导出决策序列D=D1,…Dk，因此动态规划方法可以保证问题求解是全局最优的。也可以这样理解：如果求最优解的问题可以划分成若干段（级），那么最后求得的最优解是由各个部分解所组成，而这些部分解一定是对应阶段的最优解。算法设计与分析5最短路径给定简单有向连通赋权图G=V,E,w，w(i,j)是G中边i,j的权。顶点集V可以划分为k+1个两两不交的子集Vi，i=0,1,2,..k。其中V0={s}，Vk={t}。对G中任一边u,v，存在Vi、Vi+1，使得u属于Vi，v属于Vi+1，其中0≤ik。称G为k段图，s点为起点，t为终点。在G中求s出发到t的最短路径。这里最短是指s到t的路径上各边权的和最小。算法设计与分析6一个多段图例子记D(u,v)是G中起点为u,终点为v的最短路径，C(u,v)是该路径上各边权的和。设D(s,t)=s,vi1,vi2…vik-1,t，vir属于Vr（r=1,2..k-1），则D(vi1,t)=vi1,vi2,…vik-1,t是从vi1出发到t的最短路径，D(vi2,t)=vi2,…vik-1,t是从vi2出发到t的最短路径等等。设u属于Vi，有：C(u,t)=min{w(u,v)+C(v,t)}(4.1)v∈Vi+1阶段4:C(7,t)=w(7,t)=8，C(8,t)=w(8,t)=4阶段3:C(4,t)=min{w(4,7)+C(7,t),w(4,8)+C(8,t)}=12C(5,t)=min{w(5,7)+C(7,t),w(5,8)+C(8,t)}=10C(6,t)=min{w(6,7)+C(7,t),w(6,8)+C(8,t)}=8阶段2:C(1,t)=min{w(1,4)+C(4,t),w(1,5)+C(5,t)}=19C(2,t)=min{w(2,4)+C(4,t),w(2,5)+C(5,t),w(2,6)+C(6,t)}=17C(3,t)=min{w(3,5)+C(5,t),w(3,6)+C(6,t)}=13阶段1:C(s,t)=min{w(s,1)+C(1,t),w(s,2)+C(2,t),w(s,3)+C(3,t)}=16沿求解中带下划线的项回溯，得最短路径解：D(s,t)=s,3,5,8,t算法设计与分析7问题解决关键求解过程中起到关键作用的是公式(4.1)，它给出了求该问题最优解的基本性质：原始问题最优解与子问题的最优解存在递归关系，称这种关系为问题的最优子结构。最优子结构为构造求解问题的最优决策序列提供了重要线索，它提示可以自底向上的方式逐次由子问题最优解构造原始问题的最优解。公式(4.1)还有一个重要特征：由给出的自顶向下的递归分解中，每次产生的子问题求解的关键（例如，求C(v,t)）与原问题是类似的，只是在相对较小的子问题空间中考虑问题的解，因此子问题与原始问题存在相似性。而且这些子问题的解在不同的上一级问题中都需要用到，这种特征可以称为子问题重叠。算法设计与分析8采用邻接矩阵表示图G，其中wij为G中边i,j的权，如果i,j不是G的边,则wij=∞。G的节点集V={0,1,2,…n}，其中V0={0}是起始点集，Vk={n}是终点集，{V0,V1,…Vk}中各子集非空、两两不交。设V1={1，2，..r1}，V2={r1+1，r1+2，…r2}，…Vk-1={rk-2+1，rk-2+2，..(n-1)}。【算法3-1】MultiStage_GraphS1:初始化：j=n-1；对i=0,1,…n，ci=0；//ci为节点i到终点n的最短路径长S2:求节点r，使得wjr+cr=min{wji+ci|j,i是G的边};//按照{V0,V1,…Vk}对节点的标记，ji。S3:cj=wjr+cr,Dj=r;//Dj=r表示边j,r是从j出发到n的最短路径上第1条边S4:j=j-1;S5:如果j≥0则转S2;S6:输出从源点0出发的最短路径长c0；p0=0,pk=n;S7:对j=1,2,…k，pj=Dpj-1;//最短路径Path=p0,p1,…pk算法设计与分析9MultiStage_Graph算法复杂度G用邻接矩阵表示，对于S2到S5的主循环执行n次。为求满足wjr+cr=min{wji+ci|j,i是G的边}的r，最多要求n-1次比较。因此时间复杂性为O(n2)。除输入G，输出P外，要求附加存储空间c、D。如果G采用邻接表表示，求满足最小性的节点r仅对属于G的边j,r访问一次，此算法的时间复杂性应该为O(n+e)（e为G的边数）。一般地，为避免递归过程中的重复计算，每个子问题首次处理时将结果保存以备查。在上面的过程中，每一次求得的cj都必须记录下来。算法设计与分析10从源点往后推算法4-1完全是从汇点往前推，实际上我们也可以用同样的思想，从源点出发往后推。阶段1:C(s,1)=w(s,1)=4，C(s,2)=w(s,2)=2,C(s,3)=w(s,3)=3阶段2:C(s,4)=min{w(1,4)+C(s,1),w(2,4)+C(s,2)}=min{14,8}=8C(s,5)=min{w(1,5)+C(s,1),w(2,5)+C(s,2),w(3,5)+C(s,3)}=min{13,9,6}=6C(s,6)=min{w(2,6)+C(s,2),w(3,6)+C(s,3)}=min{12,11}=11阶段3:C(s,7)=min{w(4,7)+C(s,4),w(5,7)+C(s,5),w(6,7)+C(s,6)}=min{12,15,16}=12C(s,8)=min{w(4,8)+C(s,4),w(5,8)+C(s,5),w(6,8)+C(s,6)}=min{16,12,15}=12阶段4:C(s,t)=min{w(7,t)+C(s,7),w(8,t)+C(s,8)}=min{20,16}=16算法设计与分析11MultiStage_Graph2(){/*用Ck来记录到达每一个结点的最短距离,m是划分的段数,Vk表示到达了哪一段*/C0[1]=0;for(k=1;k=m;k++){for(i=1;i=Vk中结点的数目;i++)/*本循环求第K段中所有顶点到S的最短路径*/{current=MAX;/*对于K段中的一个点i，求出K-1段中所有的点到它的距离，记录下从原点出发最短的那一个*/for(j=1;j=Vk-1中结点的数目;j++){r=d(Vk[i],Vk-1[j])+Ck-1[j];if(rcurrent){rec=j;current=r;}}Ck[i]=current;将结点Vk[i]指向结点结点Vk-1[rec];}}从T到S沿VK逆向输出；}算法设计与分析12图中任意两点间的最短距离如果上面的图不是分段图，仍然可以用此方法来求图中任意两点间的最短路径，这就是大名鼎鼎的Floyd算法。程序段如下：for(k=1;k=vtxnum;k++)for(i=1;i=vtxnum;i++)for(j=1;j=vtxnum;j++)if(length[i][k]+length[k][j]length[i][j]){length[i][j]=length[i][k]+length[k][j];path[i,j]=path[i,k]+path[k,j];}算法设计与分析13矩阵连乘问题给定n个矩阵：A1,A2,…,An，其中Ai与Ai+1是可乘的。确定一种连乘的顺序，使得矩阵连乘的计算量为最小。设A和B分别是p×q和q×r的两个矩阵，则乘积C=AB为p×r的矩阵，计算量为pqr次数乘。但是对于多于2个以上的矩阵连乘，连乘的顺序却非常重要，因为不同的顺序的总计算量将会有很大的差别。算法设计与分析14不同计算顺序的差别设矩阵A1,A2和A3分别为10×100,100×5和5×50的矩阵，现要计算A1A2A3。若按((A1A2)A3)来计算，则需要的数乘次数为10×100×5+10×5×50=7500若按(A1(A2A3))来计算，则需要的数乘次数为100×5×50+10×100×50=75000后一种计算顺序的计算量竟是前者的10倍！所以，求多个矩阵的连乘积时，计算的结合顺序是十分重要的。算法设计与分析15不同计算顺序的数量设n个矩阵的连乘积有P(n)个不同的计算顺序。先在第k个和第k+1个矩阵之间将原矩阵序列分成两个矩阵子序列，k=1,…,n；再分别对两个子序列完全加括号，最后对结果加括号，便得到原序列的一种完全加括号方式。由此可得出关于P(n)的递归式：P(n)=1n=1n–1∑P(k)P(n–k)n＞1k=1解此递归方程可得P(n)=C(n–1)，其中C(n)=1n+12nn=Ω(4n/n3/2)所以P(n)随n的增长呈指数增长。因而穷举搜索法不是有效的算法。算法设计与分析16分解最优解的结构将矩阵连乘积AiAi+1…Aj记为A[i:j]。若A[1:n]的一个最优解是在矩阵Ak和Ak+1处断开的，即A[1:n]=(A[1:k]A[k+1:n])，则A[1:k]和A[k+1:n]也分别是最优解。事实上，若A[1:k]的一个计算次序所需计算量更少的话，则用此计算次序替换原来的次序，则得到A[1:n]一个更少的计算量，这是一个矛盾。同理A[k+1:n]也是最优解。最优子结构性质：最优解的子结构也最优的。算法设计与分析17建立递归关系令m[i][j],1≤i,j≤n，为计算A[i,j]的最少数乘次数，则原问题为m[1][n]。当i=j时，A[i,j]为单一矩阵，m[i][j]=0；当i＜j时，利用最优子结构性质有：m[i][j]=min{m[i][k]+m[k+1][j]+pi–1pkpj}i≤k＜j其中矩阵Ai(1≤i≤n)的维数为pi–1×pi。根据此递归式就可以直接用递归程序来实现。算法设计与分析18直接递归的时间复杂性根据前面的递归式不难得出的时间复杂性为n–1∑(T(k)+T(n–k)+1)k=1T(n)≥n–1=(n–1)+∑(T(k)+T(n–k))k=1n–1n–1=(n-1)+∑T(k)+∑T(n–k)k=1k=1可用数学归纳法证明T(n)≥2n–1=Ω(2n)。直接递归算法的时间复杂性随n的指数增长。n–1=n+2∑T(k)k=1算法设计与分析19直接递归