经典DP题&详细解析

203第六章动态规划Chapter6DynamicProgramming§6.1引例例6.1最短路径问题图6.1表示从起点A到终点E之间各点的距离。求A到E的最短路径。如果用穷举法，则从A到E一共有3×3×2=18条不同的路径，逐个计算每条路径的长度，总共需要进行4×18=72次加法计算；对18条路径的长度做两两比较，找出其中最短的一条，总共要进行18－1=17次比较。如果从A到E的站点有k个，则总共有3k-1×2条路径，用穷举法求最短路径总共要进行(k+1)3k-1×2次加法，3k-1×2-1次比较。当k的值增加时，需要进行的加法和比较的次数将迅速增加。例如当k=10时，加法次数为433026次，比较39365次。以上求从A到E的最短路径问题，可以转化为三个性质完全相同，但规模较小的子问题，即分别从B1、B2、B3到E的最短路径问题。记从Bi(i=1,2,3)到E的最短路径为S(Bi)，则从A到E的最短距离S(A)可以表示为：C1C3D1AB1B3B2D2EC22511214106104131112396581052图6.1第六章动态规划204)B(S1)B(S5)B(S2min)B(SAB)B(SAB)B(SABmin)A(S321332211同样，计算S(B1)又可以归结为性质完全相同，但规模更小的问题，即分别求C1，C2，C3到E的最短路径问题S(Ci)(i=1,2,3)，而求S(Ci)又可以归结为求S(D1)和S(D2)这两个子问题。从图1.1.1可以看出，在这个问题中，S(D1)和S(D2)是以知的，它们分别是：S(D1)=5，S(D2)=2因而，可以从这两个值开始，逆向递归计算S(A)的值。计算过程如下：11212211111DC,82953min)D(S9)D(S3min)D(SDC)D(SDCmin)C(S22212221122DC,72556min)D(S5)D(S6min)D(SDC)D(SDCmin)C(S23212231133DC,1221058min)D(S10)D(S8min)D(SDC)D(SDCmin)C(S即S(C1)=8且如果到达C1，则下一站应到达D1；S(C2)=7且如果到达C2，则下一站应到达D2；S(C3)=12且如果到达C3，则下一站应到达D2；由此，可以计算S(Bi)：113213312211111CB,201210714812min)C(S10)C(S14)C(S12min)C(SCB)C(SCB)C(SCBmin)B(S123213322221122CB,1412471086min)C(S4)C(S10)C(S6min)C(SCB)C(SCB)C(SCBmin)B(S233213332231133CB,191211712813min)C(S11)C(S12)C(S13min)C(SCB)C(SCB)C(SCBmin)B(S即S(B1)=20且如果到达B1，则下一站应到达C1；第六章动态规划205S(B2)=14且如果到达B2，则下一站应到达C1；S(B3)=19且如果到达B3，则下一站应到达C2；由此，可以计算S(A)：2321332211BA,19191145202min)B(S1)B(S5)B(S2min)B(SAB)B(SAB)B(SABmin)A(S最后，可以得到：从A到E的最短路径为AB2C1D1E以上计算过程及结果，可用图6.2表示，可以看到，以上方法不仅得到了从A到D的最短路径，同时，也得到了从图中任一点到E的最短路径。以上过程，仅用了18次加法，11次比较，计算效率远高于穷举法。820052712141919C1C3D1AB1B3B2D2EC22511214106104131112396581052图6.2第六章动态规划206§6.2动态规划的基本概念最短路径问题由例6.1可以看出，动态规划问题具有以下基本特征：1、问题具有多阶段决策的特征。阶段可以按时间划分，也可以按空间划分。2、每一阶段都有相应的“状态”与之对应，描述状态的量称为“状态变量”。3、每一阶段都面临一个决策，选择不同的决策将会导致下一阶段不同的状态，同时，不同的决策将会导致这一阶段不同的目标函数值。4、每一阶段的最优解问题可以递归地归结为下一阶段各个可能状态的最优解问题，各子问题与原问题具有完全相同的结构。能否构造这样的递推归结，是解决动态规划问题的关键。这种递推归结的过程，称为“不变嵌入”。为了将以上特征形式化，我们提出以下动态规划的基本概念。阶段k：表示决策顺序的离散的量，阶段可以按时间或空间划分。状态Sk：能确定地表示决策过程决策过程当前特征的量。状态可以是数量，也可以是字符，数量状态可以是连续的，也可以是离散的。状态变量xk：表示每一状态可以取不同值的变量。决策（Decision）dk：从某一状态向下一状态过度时所做的选择。决策是所在状态的函数，记为dk(xk)。决策允许集合Dk(xk)：在状态xk下，允许采取决策的全体。状态转移方程xk+1=T(xk,dk)：某一状态以及该状态下的决策，与下一状态之间的函数关系。阶段指标函数vk(xk,dk)：从状态xk出发，选择决策dk所产生的第k阶段指标。过程指标函数V(xk,dk,dk+1,…,dn)：从状态xk出发，选择决策dk,dk+1,…,dn所产生的过程指标。动态规划要求过程指标具有可分离性，即Vk,n(xk,dk,dk+1,…,dn)=vk(xk,dk)+Vk+1(xk+1,dk+1,…,dn)称指标具有可加性，或Vk,n(xk,dk,dk+1,…,dn)=vk(xk,dk)×Vk+1(xk+1,dk+1,…,dn)第六章动态规划207C1C3D1AB1B3B2D2EC2称指标具有可乘性。最优指标函数fk(xk)：从状态xk出发，对所有的策略Pk,n，过程指标Vk,n的最优值，即)}P,x(V{max(min))x(fn,kkn,k)x(Ddkkkkk对于可加性指标函数，上式可以写为n,,2,1k)}x(f}d,x(v{max(min))x(f1k1kkkk)x(Ddkkkkk对于可乘性指标函数，上式可以写为n,,2,1k)}x(f}d,x(v{max(min))x(f1k1kkkk)x(Ddkkkkk以上式子称为动态规划最优指标的递推方程，是动态规划的基本方程。终端条件：为了使以上的递推方程有递推的起点，必须要设定最优指标的终端条件，即确定最后一个状态n下最优指标fn(xn)的值。例6.2利用以上基本概念，重新求解例6.1。将问题分成五个阶段，第k阶段到达的具体地点用状态变量xk表示，例如：x2=B3表示第二阶段到达位置B3，等等。这里状态变量取字符值而不是数值。将决策定义为到达下一站所选择的路径，例如目前的状态是x2=B3，这时决策允许集合包含三个决策，它们是2511214106104131112396581052图6.3阶段1阶段2阶段3阶段4阶段5第六章动态规划208D2(x2)=D2(B3)={B3C1,B3C2,B3C3}最优指标函数fk(xk)表示从目前状态到E的最短路径。终端条件为f5(x5)=f5(E)=0其含义是从E到E的最短路径为0。第四阶段的递推方程为：fxvxdfxdDx4444455444()min{(,)()}()从f5(x5)到f4(x4)的递推过程用下表表示：x4D4(x4)x5v4(x4,d4)v4(x4,d4)+f5(x5)f4(x4)最优决策d4*D1D1EE55+0=5*5D1ED2D2EE22+0=2*2D2E其中*表示最优值，在上表中，由于决策允许集合D4(x4)中的决策是唯一的，因此这个值就是最优值。由此得到f4(x4)的表达式。由于这是一个离散的函数，取值用列表表示：f4(x4)的表达式x4f4(x4)最优决策d4*D15D1ED22D2E第三阶段的递推方程为：fxvxdfxdDx3333344333()min{(,)()}()从f4(x4)到f3(x3)的递推过程用表格表示如下：x3D3(x3)x4v3(x3,d3)v3(x3,d3)+f4(x4)f3(x3)最优决策d3*C1C1D1C1D2D1D2393+5=8*9+2=118C1D1C2C2D1C2D2D1D2656+5=115+2=7*7C2D2C3C3D1C3D2D1D28108+5=1310+2=12*12C3D2第六章动态规划209由此得到f3(x3)的表达式：x3f3(x3)最优决策d3*C18C1D1C27C2D2C312C3D2第二阶段的递推方程为：fxvxdfxdDx2222233222()min{(,)()}()从f3(x3)到f2(x2)的递推过程用表格表示如下：x2D2(x2)x3v2(x2,d2)v2(x2,d2)+f3(x3)f2(x2)最优决策d2*B1B1C1B1C2B1C3C1C2C312141012+8=20*14+7=2110+12=2220B1C1B2B2C1B2C2B2C3C1C2C361046+8=14*10+7=174+12=1614B2C1B3B3C1B3C2B3C3C1C2C313121113+8=2112+7=19*11+12=2319B3C2由此得到f2(x2)的表达式：x2f2(x2)最优决策d2*B120B1C1B214B2C1B319B3C2第一阶段的递推方程为：fxvxdfxdDx1111122111()min{(,)()}()从f2(x2)到f1(x1)的递推过程用表格表示如下：x1D1(x1)x2v1(x1,d1)v1(x1,d1)+f2(x2)f1(x1)最优决策d1*AAB1AB2AB3B1B2B32512+20=225+14=19*1+19=2019AB2由此得到f1(x1)的表达式：第六章动态规划210x1f1(x1)最优决策d1*A19AB2从表达式f1(x1)可以看出，从A到E的最短路径长度为19。由f1(x1)向f4(x4)回朔，得到最短路径为：AB2C1D1E第六章动态规划211§6.3资源分配问题例6.3有资金4万元，投资A、B、C三个项目，每个项目的投资效益与投入该项目的资金有关。三个项目A、B、C的投资效益（万吨）和投入资金（万元）的关系见下表：求对三个项目的最优投资分配，使总投资效益最大。阶段k：每投资一个项目作为一个阶段；状态变量xk：投资第k个项目前的资金数；决策变量dk：第k个项目的投资；决策允许集合：0≤dk≤xk状态转移方程：xk+1=xk-dk阶段指标：vk(xk,dk)见表中所示；递推方程：fk(xk)=max{vk(xk,dk)+fk+1(xk+1)}终端条件：f4(x4)=0k=4，f4(x4)=0k=3，0≤d3≤x3，x4=x3-d3x3D3(x3)x4v3(x3,d3)v3(x3,d3)+f4(x4)f3(x3)d3*00000+0=00010100+0=0111101111+0=11*20200+0=0302111111+0=11203030+0=30*30300+0=0453121111+0=11213030+0=30304545+0=45*40400+0=05841311