算法分析与设计第4章.

动态规划一、适用条件多阶段决策过程实际问题中,常有这样一类活动,它们的活动过程可以分为若干个阶段，而且在任一阶段i后的行为都依赖于i阶段的过程状态，而与i阶段之前的过程如何达到这种状态的方式无关。当各个阶段决策确定后，就组成了一个决策序列，因而也就确定了整个过程的一条活动路线。这种把一个问题看作是一个前后关联的具有链状结构的多阶段过程被称为多阶段决策过程.满足最优性原理第四章动态规划4．1方法概述状态0决策1决策2……决策n状态n状态1状态n-1状态2动态规划最优性原理：过程的最优决策序列具有如下性质：无论过程的初始状态和初始决策是什么，其余的决策都必须相对于初始决策所产生的状态构成一个最优决策序列。如果所求解问题的最优性原理成立，则说明用动态规划方法有可能解决该问题。因为只有满足最优性原理，才能使用各阶段的递推公式求解。二、最优性原理在多阶段决策过程的每一阶段，都可能有多种可供选择的决策，但必须从中选取一种决策。一旦各个阶段的决策选定之后，就构成了解决这一问题的一个决策序列，决策序列不同，所导致的问题的结果也不同。动态规划的目标就是要在所有容许选择的决策序列中选取一个会获得问题最优解的决策序列，即最优决策序列。动态规划三、动态规划方法的关键关键在于获取各阶段间的递推关系式。四、可解决的问题最短路径问题、设备更新问题、资源分配问题、货物装运排序、生产计划等。五、应用实例分析动态规划例4.1[多段图问题]多段图G=（V，E）是一个有向图。它具有如下特性：图中的结点被划分成k≥2个不相交的集合Vi,1≤i≤k，其中V1和Vk分别有一个结点s（源点）和t（汇点）。图中所有的边(u,v)均具有如下性质：若u∈Vi，则v∈Vi+1，1≤i＜k-1,且每条边(u,v)均附有成本c(u,v)。从s到t的一条路径成本是这条路径上边的成本和。多段图问题是求由s到t的最小成本路径。每个集合Vi定义图中的一段。由于E的约束，每条从s到t的路径都是从第1段开始，在第k段终止。图4.1所示的就是一个5段图。动态规划123456789101112ts973222711118154356425461V2V3V4V5V动态规划对于每一条由s到t的路径，可以把它看成在k-2个阶段中作出的某个决策序列的相应结果。第i次决策就是确定Vi+1中的哪个结点在这条路径上，1≤i≤k-2。下面证明最优性原理对多段图成立。假设s,v2,v3,…,vk-1,t是一条由s到t的最短路径，还假定从源点s（初始状态）开始，已作出了到结点v2的决策（初始决策），因此v2就是初始决策所产生的状态。如果把v2看成是原问题的一个子问题的初始状态，解这个子问题就是找出一条由v2到t的最短路径。这条最短路径显然是v2,v3,…,vk-1,t，如若不然，设v2,q3,…,qk-1,t是一条由v2到t的更短路径，则s,v2,q3,…,qk-1,t是一条比路径s,v2,v3,…,vk-1,t更短的由s到t的路径。与假设矛盾，故最优性原理成立。因此它为使用动态规划方法来解决多段图问题提供了可能。动态规划六、动态规划方法的形式化描述能用动态规划求解的问题的最优化决策序列可表示如下。设S0是问题的初始状态。假定需要作n次决策xi,1≤i≤n。设X1={r1,1,r1,2,…,r1,p1}是X1的可能决策值的集合，而S1,1是在选取决策值r1,j1以后所产生的状态,1≤j1≤p1。又设是相应于状态S1,j1的最优决策序列。那末，相应于S0的最优决策序列就是{|1≤j1≤p1}中最优的序列，记为OPT{}=。如果已作了k-1次决策，1≤k-1＜n。设x1,…,xk-1的最优决策值是r1,…,rk-1，它们所产生的状态为S1,…,Sk-1。又设111,j1,jr11r111,j1,jr11,j动态规划是xk的可能值的集合。是选取决策值后所产生的状态，1≤jk≤pk。是相应于的最优决策序列。因此，相应于Sk-1的最优决策序列是。于是相应于S0的最优决策序列为r1,…,rk-1，rk，。kkk,1k,pX={r,r}kk,jSkk,jrkk,jSkk,jk七、两种求解方法（1）向前处理法：从最后阶段开始，以逐步向前递推的方式列出求前一阶段决策值的递推关系式，即根据xi+1,…,xn的那些最优决策序列来列出求取xi决策值的关系式，即：xi=f(xi+1,xi+2,…,xn)kkjkjkpjrrOPTkkkk}{,,1动态规划例子：在k段图问题中，设又设是由到t的最短路径，则s到t的最短路径是中最短的那条路径。若设是s到t的一条最短路径，是路径上的中间结点，则就应分别是由s到vi和由vi到t的最短路径。iv22,Vj22,vj222,2,222|,1VjjsvVjp21,,,,,iksvvvt21,,,,,iksvvvt（2）向后处理法：根据x1,…,xi-1的那些最优决策序列列出求xi的递推关系式。即：xi=f(x1,x2,…,xi-1).下例是说明向前处理法在多段图中的使用见黑板;,1,22222,22pVpjVvj动态规划小结：无论是使用向前处理法还是使用向后处理法，都将所有子问题的最优解保存下来。这样做的目的是为了便于逐步递推得到原问题的最优解并避免对它们的重复计算。由枚举法可知，不同决策序列的总数就其所取决策值而言是指数级的（如果决策序列由n次决策构成，而每次决策有p种选择，那末可能的决策序列就有pn个），而动态规划算法则可能有多项式的复杂度。八、动态规划算法的求解步骤(1)段化；(2)自顶向下的分析，测试问题本身是否满足最优化原理；(3)从底向上的计算，实现动态规划过程。动态规划一、问题的描述例4.1给出了多段图的定义，并且指出一个k段图的每一条由源点s到汇点t的路径可以看成是在k-2个阶段中作出的某个决策序列的相应结果。第i次决策就是确定Vi+1中的哪个结点在这条路径上，1≤i≤k-2。进而还证明了最优性原理对多段图成立，因此用动态规划方法有可能找到由s到t的最小成本路径。4.2多段图动态规划二、问题分析：使用向前处理法求各阶段的递推关系式：（1）（2）若j,t∈E，有COST(k-1,j)=c(j,t)，若j,tE，有COST(k-1,j)=∞，设：P(i,j)是一条从Vi中的结点j到汇点t的最小成本路径，COST(i,j)是这条路的成本。)},1(),({min),(,1liCOSTljcjiCOSTEljiVl关键动态规划例子：对图4.1的5段图给出具体实现这一系列计算的步骤：COST(3,6)=min{6+COST(4,9),5+COST(4,10)}=7COST(3,7)=min{4+COST(4,9),3+COST(4,10)}=5COST(3,8)=7COST(2,2)=min{4+COST(3,6),2+COST(3,7),1+COST(3,8)}=7COST(2,3)=9，COST(2,4)=18，COST(2,5)=15COST(1,1)=min{9+COST(2,2),7+COST(2,3),3+COST(2,4),2+COST(2,5)}=16123456789101112ts97322271111815435642546123456789101112ts97322271111815435642546动态规划于是由s到t的最小成本路径的成本为16。如果在计算每一个COST(i,j)的同时，记下每个状态（结点j）所作的决策（即，使c(j,l)+COST(i+1,l)取最小值的l值），设它为D(i,j)，则可容易地求出这条最小成本路径。对于图4.1所示的，可得到D(3,6)=10D(3,7)=10D(3,8)=10D(2,2)=7D(2,3)=6D(2,4)=8D(2,5)=8D(1,1)=2设这条最小成本路径是s=1,v2,v3,…,vk-1,t=12。立即可知，v2=D(1,1)=2,v3=D(2,D(1,1))=7和v4=D(3,D(2,D(1,1)))=D(3,7)=10。动态规划三、算法设计对结点集V的结点按下述方式排序：首先将s结点编成1号，然后对V2中的结点编号，V3的结点接着V2中的最后一个编号继续往下编……最后将t编成n号。经过这样编号，Vi+1中结点的编号均大于Vi中结点的编号（见图4.1）。于是，COST和D都可按n-1,n-2,…1的次序计算，而无需考虑COST，P和D中标识结点所在段数的第一个下标，因此它们的第一个下标可在算法中略去。所导出的算法是过程FGRAPH。动态规划算法4.1多段图的向前处理算法FGRAPH(ElemtypeE[],intk,intn,ElemtypeP[k])//输入是按段的顺序给结点编号的，有n个结点的k段图。E是边集，c[i][j]是边i,j的成本。P[k]是最小成本路径//输入：多段图的顶点编号表，各顶点的边表和各边的成本函数c(i，j)的表。输出：从s到t的一条最小成本路径上的各顶点以及成本COST(l，s)。动态规划1COST[n]0;2forjn-1to1by-1//计算COST[j]；3do{设r是这样一个结点，j,r且使c[j][r]+COST[r]取最小值；4COST[j]c[j][r]+COST[r];5D[j]r;6}//找一条最小成本路径；7P[1]1；P[k]n;8forj2tok-1//找路径上的第j个结点。9do{10P[j]D[P[j-1]];11}E问题：D[j],P[j]分别存的是什么数据？123456789101112ts97322271111815435642546动态规划四、算法分析过程FGRAPH的复杂分析相当简单。如果G用邻接表表示，那末第4行的r可以在与结点j的度成正比的时间内算出。因此，如果G有e条边，则第3-6行的for循环的时间是(n+e)，第9-11行的for循环时间是。总的计算时间在以内。除了输入所需要的空间外，还需要给COST，D和P的空间。也可以使用向后处理法，请自学。()k()ne动态规划五、多段图的应用—资源分配问题把n个资源分配给r个项目的问题。如果把j个资源，0≤j≤n,分配给项目i，所获得的净利是N(i,j)。要求按使得总净利达到最大值的方法把资源分配给这r个项目。这个问题可用一个r+1段图来表示。其中1到r之间的段i代表项目i。源点s=V(1,0)，汇点t=V(r+1,n)。段i为2到r时，每段都有n+1个结点V(i,j),0≤j≤n。N(i,j)表示把j个资源（0≤j≤n）,分配给项目i，所获得的净利。动态规划每个结点V(i,j)表示共把j个资源分配给了项目1，2，…,i-1。当j≤1且1≤i＜r时，边V(i,j)，V(i+1,1)赋予N(i,1-j)的成本值.当j≤n且i=r即边具有V(r,j)，V(r+1,n)的形式时，每一条这样的边被赋予max{N(r,p)}的成本值。动态规划见黑板动态规划一、问题的描述某货郎要到若个城市去推销物品，各城市之间的路程是已知的，货郎从其所在城市出发，到其他的城市一次且仅一次，然后返回其所在城市，问他应选择怎样的路线才能使所走的总路程最短？可以用一个有向图G=V,E描述，该图是具有边成本Cij的有向图，Cij的定义为：对于所有的i,j,有Cij0,若i,jE，则Cij=.设|V|=n，并假定n1，G的一条周游路线是包含V中每个结点的一个有向环。货郎担问题就是求取具有最小成本的周游路线。4.3货郎担问题动态规划二、问题的分析1.是否是多阶段决策问题;2.其最优决策序列是否满足最优性原理。三、各阶段之间的递推关系式112),()3(})}{,({min),()2(})},1{,({min})1{,1()1(iijSjknkcigjSjgcSigkVkgcVg其中g(i,S)由结点i出发，通过S中的所有结点，在结点1终止的一条最短路径长度。动态规划四、例子例子：