6算法第六章动态规划.

1第六章动态规划2目录6.1一般方法6.2多段图6.3每对节点之间的最短路径(略)6.4最优二分检索树6.50/1背包问题6.6可靠性设计6.7货郎担问题6.8流水线调度问题36.1一般方法多阶段决策问题动态规划的求解思想最优性原理及其证明最优化决策序列的表示递推关系式的设计方法4多阶段决策过程在现实生活中，有这样一类活动过程，它可以被分成若干个互相联系的阶段:每一阶段都需要作出决策i阶段的决策仅依赖于i阶段当前的状态,而与i阶段之前的过程无关这样就构成了一个多阶段决策过程。当各个阶段决策确定后，就确定了整个过程的一条活动路线。5多阶段决策问题这种能够看作是多阶段决策过程(multistepdecisionprocess)的问题就称为多阶段决策问题一旦为多阶段决策过程的各阶段选定决策，就构成了解决这一问题的一个决策序列多阶段决策问题的目标：在所有允许选择的决策序列中，选取一个会获得问题最优解的决策序列，即最优决策序列6动态规划的求解思想动态规划方法求解多阶段决策问题时,可以归纳为两个步骤：证明问题满足最优性原理给出递推关系式20世纪50年代，贝尔曼等人根据这类问题多阶段决策的特性,提出了解决这类问题的“最优性原理”，从而创建了一种新的算法设计方法—动态规划。利用动态规划方法去求解最优决策序列可以使枚举量急剧下降。7最优性原理最优性原理(PrincipleofOptimality)过程的最优决策序列具有如下性质:无论过程的初始状态和初始决策是什么,其余的决策都必须相对于初始决策所产生的状态构成一个最优决策序列。如果所求解的问题满足最优性原理，则说明用动态规划方法有可能解决该问题；而解决该问题的关键在于求解递推关系式。S0x1S1x2S2xnSnx3……8最优性原理的证明思路①设最优决策序列的形式②确定初始状态和初始决策③确定初始决策所产生的状态④证明其余决策相对于③是最优决策序列9多段图问题(multistagegraphproblem)多段图G=(V,E)是一个有向图。它具有如下特性：图中的结点被划分成k≥2个不相交的集合Vi,1≤i≤k,其中V1和Vk分别只有一个结点s(源点)和t(汇点)。图中所有的边u,v均具有如下性质:若u∈Vi，则v∈Vi+1,1≤i≤k,且每条边u,v均附有成本c(u,v)。从s到t的一条路径成本是这条路径上边的成本和。多段图问题是求由s到t的最小成本路径。10例6.12345876111091s12t97324227111118654356524V1V2V3V4V511多段图问题的最优性原理证明假设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路径短，这与假设矛盾，因此最优性原理成立。120/1背包问题背包问题中的xj限定只能取0或1值，用KNAP(l,j,X)来表示这个问题。极大化∑pixi约束条件∑wixi≤Xxi=0或1,l≤i≤jl≤i≤jl≤i≤j若对于有n个物品，容量为M的背包，则0/1背包问题就可表示为KNAP(1,n,M)英文字母L,非数字1130/1背包问题的最优性原理证明设y1,y2,…,yn是最优序列。若y1=0，则y2,y3,…,yn必须相对于KNAP(2,n,M)问题构成一个最优序列。如若不然，则y1,y2,…,yn就不是KNAP(1,n,M)的最优序列。若y1=1，则y2,y3,…,yn必须是KNAP(2,n,M-w1)的最优序列。如若不然，则必有另一个0/1序列z2,z3,…,zn使得∑wizi≤M-w1(2≤i≤n)且∑pizi∑piyi(2≤i≤n)。因此，序列y1,z2,z3,…,zn是一个对问题KNAP(1,n,M)具有更大效益值的序列。这与假设相矛盾，所以0/1背包问题的最优性原理成立。14最优化决策序列的表示设S0是问题的初始状态,假定要作n次决策xi,1≤i≤nX1={r1,1,r1,2,…,r1,p1}是x1的可能决策值的集合,而S1,j1是在选取决策值r1,j1以后所产生的状态,1≤j1≤p11≤j1≤p1又设Γ1,j1是相应于状态S1,j1的最优决策序列;则相应于S0的最优决策序列就是{r1,j1Γ1,j1|1≤j1≤p1}中最优的序列，记为OPT{r1,j1Γ1,j1}=r1Γ115如果已作了k-1次决策,1≤k-1n,设x1,…xk-1的最优决策值是r1,..,rk-1,它们所产生的状态为S1,…Sk-1。又设Xk={rk,1,rk,2,…,rk,pk}是xk的可能值的集合,Sk,jk是选取rk,jk决策之后所产生的状态,1≤jk≤pk。Γk,jk是相应于Sk,jk的最优决策序列。因此相应于Sk-1的最优决策序列是:1≤jk≤pkOPT{rk,jkΓk,jk}=rkΓk于是相应于S0的最优决策序列为:r1,…,rk-1,rk,Γk16递推关系式的设计方法向前处理法(forwardapproach)从最后阶段开始,以逐步向前递推的方式,列出求解前一阶段决策值的递推关系式,即根据xi+1,…xn的那些最优决策序列来列出求取xi决策值的关系式。向后处理法(backwardapproach)从初始阶段开始,以逐步向后递推的方式,列出求解后一阶段决策值的递推关系式,即根据x1,…xi-1的那些最优决策序列来列出求取xi决策值的关系式。170/1背包问题向前处理法设gj(x)是KNAP(j+1,n,x)最优解的值，显然g0(M)是KANP(1,n,M)最优解的值。由于xi可能的取值是0或1，因此可得g0(M)=max{g1(M),g1(M-w1)+p1}推知一般情况：gj(x)=max{gj+1(x),gj+1(x-wj+1)+pj+1}向后处理法设fi(x)是KNAP(1,i,x)最优解的值fi(x)=max{fi-1(x),fi-1(x-wi)+pi}186.2多段图多段图向前处理递推关系式向前处理的计算过程向前处理算法及执行过程多段图向后处理递推关系式向后处理的计算过程向后处理算法多段图的应用19多段图向前处理递推关系式设P(i,j)是一条从Vi中的节点j到汇点t的最小成本路径,COST(i,j)表示这条路径的成本,根据向前处理方法：COST(i,j)=min{c(j,l)+COST(i+1,l)}其中:l∈Vi+1,j,l∈E,c(j,l)表示该边的成本。对于k段图,当i=k-1时,如果j,t∈E，有COST(k-1,j)=c(j,t)如果j,t∈E，有COST(k-1,j)=∞向前处理法:从最后阶段开始,逐步向前递推,根据xi+1,…,xn的那些最优决策序列来列出求取xi决策值的关系式。jVil1Vi+1lpt初始值20多段图向前处理的计算过程COST(4,9)=c(9,12)=4COST(4,10)=c(10,12)=2COST(4,11)=c(11,12)=51110912t524V4V5876654356V3COST(3,6)=min{c(6,9)+COST(4,9),c(6,10)+COST(4,10)}=min{6+4,5+2}=7COST(3,7)=min{c(7,9)+COST(4,9),c(7,10)+COST(4,10)}=min{4+4,3+2}=5COST(3,8)=min{c(8,10)+COST(4,10),c(8,11)+COST(4,11)}=min{5+2,6+5}=7COST(i,j)=min{c(j,l)+COST(i+1,l)}211s9732V123454227111118V21110912t524V4V5876654356V3COST(2,2)=min{c(2,6)+COST(3,6),c(2,7)+COST(3,7),c(2,8)+COST(3,8)}=min{4+7,2+5,1+7}=7COST(3,6)=7COST(3,7)=5COST(3,8)=7COST(2,3)=min{2+7,7+5}=9COST(2,4)=min{11+7}=18COST(2,5)=min{11+5,8+7}=15COST(1,1)=min{c(1,2)+COST(2,2),c(1,3)+COST(2,3),c(1,4)+COST(2,4),c(1,5)+COST(2,5)}=min{9+7,7+9,3+18,2+15}=1622在计算每个COST(i,j)的同时,记下每个状态(结点j)所做出的决策(即l的取值),令D(i,j)=l,则容易求出这条最小成本的路径COST(2,2)=min{c(2,6)+COST(3,6),c(2,7)+COST(3,7),c(2,8)+COST(3,8)}=7COST(1,1)=min{c(1,2)+COST(2,2),c(1,3)+COST(2,3),c(1,4)+COST(2,4),c(1,5)+COST(2,5)}=16D(1,1)=2D(2,2)=7D(2,3)=6D(2,4)=8D(2,5)=8D(3,6)=10D(3,7)=10D(3,8)=10COST(3,6)=min{c(6,9)+COST(4,9),c(6,10)+COST(4,10)}=71271012最小成本的路径为:23算法6.1多段图的向前处理算法procedureFGRAPH(E,k,n,P)realCOST(n),intD(n-1),P(k),r,j,k,nCOST(n)←0forj←n-1to1by-1do寻找结点r,满足j,r∈E且使c(j,r)+COST(r)值最小COST(j)←c(j,r)+COST(r);D(j)←r;repeatP(1)←1;P(k)←nforj←2tok-1doP(j)←D(P(j-1))repeatendFGRAPH为了算法描述的简单,对结点进行编号,从V1开始s编为1号,然后V2中的结点依次编为2,3,4,5号,按此规则编下去,有了编号可以将COST,D中表示段数的第一个下标i省略掉。通过计算找到一条最小成本的路径P(1:k)保存最小成本路径上结点。24邻接表形式存储有向图1s9732234542271111181110912t524876654356123456789101112∧∧118∧412∧212∧512927334∧254627∧1826∧77117∧8869∧51049∧310510∧611邻接表是图的一种链式存储结构,对图中的每个顶点建立一个单链表,链表中的结点有3个域,分别存储顶点,边的成本和下一个结点的指针.25k←5;n←12;COST(12)←0;forj←11to1by-1doCOST(j)←min{c(j,r)+COST(r)}D(j)←rrepeatP(1)←1;P(k)←12;forj←2to4doP(j)←D(P(j-1))repeat1234567891011120123456789101112345112COSTDPCOST(11)=5COST(10)=2COST(9)=4512241212COST(8)=7COST(7)=5COST(6)=7D(8)=10D(7)=10D(6)=10710571010COST(5)=15COST(4)=18COST(3)=9COST(2)=7D(11)=12D(10)=12D(9)=12D(5)=8D(4)=8D(3)=6D(2)=71581897867D(1)=2COST(1)=161622710算法6.1的执行过程26算法6.1时间复杂度和空间复杂度