王建德 5 动态程序设计

单击此处编辑母版标题样式,单击此处编辑母版文本样式,第二级,第三级,第四级,第五级,*,动态规划,1,讨论的问题,1,、动态规划的基本概念,2,、动态规划的基础题型,3,、动态规划的综合题型,2,基本概念,动态程序设计是解决多阶段决策最优化问题的一种思想方法。所谓,“,动态,”,，指的是在问题的多阶段决策中，按某一顺序，根据每一步所选决策的不同，将随即引起状态的转移，最终在变化的状态中产生一个决策序列。动态规划就是为了使产生的决策序列在符合某种条件下达到最优。,3,D,A,G,C,K,B,N,P,O,M,J,F,H,E,L,I,3,1,2,3,4,5,2,1,4,3,2,3,1,4,2,2,1,2,2,2,3,3,4,4,阶段,1,阶段,2,阶段,3,阶段,4,阶段,5,问题的引出：,P,是出发点，从,P,到,A,，求最短路径,4,思路,令,从,P, A,的最短路径为,P(A),；,P(A) = minP(B)+2, P(C)+3,；,从,P B,的最短路径为,P(B),；,P(B) = minP(D)+1, P(E)+2,；,从,P, C,的最短路径为,P(C); P(C) = minP(E)+5, P(F)+4,；,5,上述递推公式告诉我们，要求,P(A),需要先求出阶段,5,中的,P(B),和,P(C),；要求,P(B) (,或者,P(C),），又要先求出阶段,4,中的,P(D),和,P(E) (,或,P(F),和,P(E),（倒推）,显然，要依照上述递推过程求解，需要倒过来，从,P(P),出发，先求出第一阶段的,P(O),和,P(N),，再求第二阶段的,P(K),，,P(L),，,P(M),；,，最后得到,P(A),（顺推）。,6,h30,h31,h32,h20,h21,h22,h10,h11,h12,h00,h01,h02,v20,v21,v22,v23,v10,v11,v12,v13,v00,v01,v02,v03,(3, 3),0,2,1,3,2,1,3,y,x,7,数据结构,将每条路经的长度存在数组中东西方向上的道路长度存在两维数组,h43,中,规定数组的第一维为行号，第二维为列号。,h43 = 3,2,3,2,1,4,3,4,5,3,1,2;,8,南北方向上道路长度存至数组,v34,中，也规定第一维为行号，第二维为列号。,v34 =2, 2, 3, 4,4, 1, 2, 4,1, 2, 2, 3;,9,求解过程为从,(0, 0),到,(3, 3),求最短路径问题定义二维数组，,P44=0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,第一维为行，第二维为列。这时,P(O),为,P01,；,P(N),为,P10,；,P(A),为,P33,，以下为分阶段递推求解过程。,P00 = 0;,10,阶段,1: P01 = P00+h00 = 0+3 = 3; P10 = P00+v00 = 0+2 = 3;,阶段,2: P11 = min P01+v01, P10+h10= min3+1, 2+2 = 4,P02 = P01+h10 =3+2=5; P20 = P10+v10 = 2+4 = 6,阶段,3: P12 = min P02+v02, P11+h11= min5+3, 4+1 = 5,P03 = P02+h02 =5+3=8 ; P30 = P20+v20 = 6+1=7,P21 = min P11+v11, P20+h20= min4+1, 6+1 = 5,阶段,4: P13 = min P03+v03, P12+h12= min8+4, 5+4 = 9,P22 = min P12+v12, P21+h21= min5+2, 5+4 = 7,P31 = min P21+v21, P30+h30= min5+2, 7+3 = 7,阶段,5: P23 = min P13+v13, P22+h22= min9+4,7+5=12,P32 = min P22+v22, P31+h31= min7+2, 7+1 = 8,最后,:P33 = min P23+v23, P32+h32 = min/*12+3, 8+2 = 10,11,综上，数组,P,的通项表示为,Pij=min(pi-1j+vi-1j),(pij-1+hij-1) ) (i, j0),P0j=P0j-1+h0j-1( i=0, j0),Pi0=Pi-10+vi-10( i0, j=0),P,数组数据,圆圈内为路口对,P,点的最小距离,箭头为最佳行走路径。,12,for j,1 to 4 do /*,计算,0,行上的每点的距离*,/,p0j,p0j-1+h0j-1;,For i,1 to 4 do /*,计算,0,列上的每点的距离*,/,pi0,pi-10+vi-10;,for i,1 to 4 do,for j,1 to 4 do,pij,min( ( pi-1j+vi-1j), (pij-1+hij-1) );,For i,3 downto 0 do /*,输出每个路口对,P,点的最小距离*,/, for j,0 to 3 do write(pij:4),writeln;,;/*for*/,程序,13,阶段：据空间顺序或时间顺序对问题的求解划分阶段。,状态：描述事物的性质，不同事物有不同的性质，因而用不同的状态来刻画。对问题的求解状态的描述是分阶段的。,决策：根据题意要求，对每个阶段所做出的某种选择性操作。,状态转移方程：用数学公式描述与阶段相关的状态间的演变规律。,多阶段决策过程：将所研究的过程划分为若干个相互联系的阶段，在求解时，对每一个阶段都要做出决策，前一个决策确定以后，常常会影响下一个阶段的决策。,动态规划的几个要素,14,“,最优性原理,”,：不论初始状态和第一步决策是什么，余下的决策相对于前一次决策所产生的新状态，构成一个最优决策序列。,最优决策序列的子序列，一定是局部最优决策子序列。注意包含有非局部最优的决策子序列，一定不是最优决策序列,例如贪心法。,动态规划的依据,“,最优性原理”,15,动态规划的指导思想,在做每一步决策时，列出各种可能的局部解，之后依据某种判定条件，舍弃那些肯定不能得到最优解的局部解。这样，在每一步都经过筛选，以每一步都是最优的来保证全局是最优的。筛选相当于最大限度地有效剪枝（从搜索角度看），效率会十分高。但它又不同于贪心法。,贪心法,:,产生一个按贪心策略形成的判定序列，该序列不保证解是全局最优的，因为有些问题不符合最优性原理。,动态规划,:,产生许多判定序列，再按最优性原理对这些序列加以筛选，去除那些非局部最优的子序列,。,16,2,、动态规划的基础题型,1,、路径问题,2,、,01,背包问题,3,、求最佳子序列问题,4,、双重动态规划,17,路径问题的讨论,问题的一般形式：,1,、计算所有路径方案,2,、计算一条最佳路径,3,、计算两条最佳路径（多进程的最优化决策）,一般方法：,按照出发点走出的步数划分阶段，将当前步可达的顶点集定义为状态，当前步如何走定义为决策。注意：,1,、可能需要将原题转化为路径问题,2,、如果最佳路径问题不满足最优子结构特征特征的话，可以转化为判定性问题求解。,18,一、计算所有方案,对于一些阶段性强、但不属于最优化的问题，是否也可以借助动态规划方法呢？如果我们可以找出状态转移的关系，并在状态转移方程,中去掉最佳性要求,opt,（,min,或,max,），将扩展子状态的所有行动作为决策，则可以例举出由初始状态至目标状态的所有方案。显然，在计数类问题中使用这种方法要比回溯法等搜索算法简捷许多。,19,例题 过河卒,如图，,A,点有一个过河卒，需要走到目标,B,点。卒行走的规则：可以向下、或者向右。,20,同时在棋盘上的任一点有一个对方的马（如上图的,C,点）,该马所在的点和所有跳跃一步可达的点称为对方马的控制点。例如上图,C,点上的马可以控制,8,个点（图中的,P1,，,P2.P8,）。卒不能通过对方马的控制点。,棋盘用坐标表示，,A,点（,0,，,0,）、,B,点（,n,，,m,）,(n,m,为不超过,20,的整数,并由键盘输入,),，同样马的位置坐标是需要给出的（约定：,CA,，同时,CB,）。现在要求你计算出卒从,A,点能够到达,B,点的路径的条数。,输 入：键盘输入,B,点的坐标,(n,m),以及对方马的坐标（,X,，,Y,）,输 出：屏幕输出一个整数（路径的条数）。,21,按照题意，对方的马所在的点和所有跳跃一步可达的点称为对方马的控制点，卒不能通过对方马的控制点。在卒出发之前，必须计算对方马的所有控制点。显然，若（,0,，,0,）或（,n,m,）为控制点，则输出路径数为,0,。设,const,move:array1.8,1.2of integer /* movek,，,1.2,为马沿,k,方向跳跃一步的水平增量和垂直增量*,/,=(1,-2),(1,2),(2,1),(2,-1),(-1,2),(-1,-2),(-2,1),(-2,-1),；,var,list:array-1.20,-1.20of comp,；,/*listi,j,为卒从,(0,0),到,(i,j),的路径数*,/,can:array0.20,0.20of boolean,；,/*cani,j,为允许卒通行,(i,j),的标志*,/,1,、计算对方马的控制点,22,设马的初始位置为（,x,y,）。按照下述方式计算,can,序列,canx,y false,；,/*,对方马所在的点为控制点*,/,for i1 to 8 do /*,从（,x,，,y,）出发，沿,8,个方向计算控制点*,/, jx+movei,1,；,/*,计算,i,方向的跳马位置,(j,，,k)*/,ky+movei,2,；,if (j=0)and(k=0)and(j=n)and(k=m) /*,若（,j,k,）在界内，则为控制点*,/,then canj,kfalse,；,；,/*for*/,if (not can0,0)or(not cann,m) /*,若卒的起点和终点为控制点，则输出路径数,0*/,then writeln(0),else,计算和输出卒从（,0,，,0,）走到（,n,m,）点的路径数,listn,m,；,/*else*/,23,我们按照由上而下、由左而右的顺序，将卒可能到达的每一个位置（,i,j,）,(0in,，,0jm),设为阶段和状态。,首先，将卒的出发点（,0,，,0,）的路径数设为,1,，该位置设为控制点（,list0,01;can0,0 fals,）。然后从（,0,，,0,）出发，按照由上而下、由左而右的顺序计算卒经过每一个可行点的路径数,:,若（,i,，,j,）为可行点，则走前位置（,i-1,j,）和（,i,j-1,）的路径数加起来，即为从（,0,，,0,）走到（,i,，,j,）的路径数，即,listi,j=listi-1,j+listi,j-1,（,i,，,j,）非控制点,依次类推，最后得出的,listn,m,即为问题的解。由此得出算法：,fillchar(list,sizeof(list),0),；,/*,路径数序列初始化*,/,list0,01,；,can0,0 false,；,/*,卒从（,0,，,0,）出发的路径数为,1,，该位置不再允许卒通行*,/,for i0 to n do /*,按照由上而下、由左而右计算从,(0,0),到每个可行点的路径数*,/,for j0 to m do,if cani,jthen listi,jlisti-1,j+listi,j-1,；,输出卒从（,0,，,0,）走到（,n,m,）点的路径条数,listn,m,；,2,、计算和输出卒从（,0,，,0,）走到（,n,m,）点的路径条数,24,计算一条最佳路径,以路径长度划分阶段，从出发点走,i,步可达的顶点集合为状态。设,fi,j,为到达阶段,i,的顶点,j,的最优解。,枚举第,i-1,阶段中与状态,j,相连的状态,k,其子问题的最优解,fi-1,k+,状态,k,至状态,j,的决策代价,w,k,j,即为阶段,i,的状态,j,的一种方案。枚举了所有可能方案后即可得出,fi,j,。,fi-1,k,1,W,k1,j,fi-1,k,2,W,k2,j,fi-1,k,p,W,kp,j,25,寻宝游戏,26,分析,在,“,藏宝图,”,中寻求一条含,len,个顶点的路径，使得,(1klen,)(x,k,y,k,)-a,k,),2,最小。,27,数据结构,const,ex:array1.4of shortint=(0,0,1,-1);,ey:array1.4of shortint=(1,-1,0,0);,var,n,m,len,i,j,k,l,i0,j0:integer; /*n,m,为“藏宝图”的规模*,/,mp:array1.50,1.50of integer; /*“,藏宝图”*,/,c0,c1:array1.50,1.50of longint; /*c0I,j,为,ck-1,I,j; c1I,j,为,ck,I,j*/,a:array1.150of integer; /*,数列*,/,ans:longint; /*,数列与表格的接近程度*,/,28,输入信息，计算,c0,的初始值,readln(f,n,m); /*,输入“藏宝图”的规模*,/,for i1 to n do /*,输入“藏宝图”*,/,for j1 to m do read(f,mpi,j);,readln(f,len); /*,输入数列的项数,len*/,for i1 to len do read(f,ai); /*,输入数列*,/,for i1 to n do /*,计算初始解*,/,for j1 to m do c0i,jsqr(a1-mpi,j);,29,for k2 to len do /*,阶段,:,路径长度*,/, for i1 to n do /*,状态,:,当前位置*,/,for j1 to m do, c1i,jmaxint;,for l1 to 4 do /*,决策,:,选择最佳移前位置*,/, i0i+exl; j0j+eyl;,if (i0 in 1.n) and (j0 in 1.m) and (c0i0,j0c1i,j),then c1i,jc0i0,j0,; /*for*/,c1i,jc1i,j+sqr(mpi,j-ak),; /*for*/,c0c1,; /*for*/,ansmaxint; /*,计算,ans,min,c1I,j,*,/,for i1 to n do,for j1 to m do if c1i,j=0)and(aj+xaj+y),then aj+x,aj+y ;/* for */,ans,-1; /*,在,t,时间内采到草药的最大总价值,ans= */,for i,0 to t do if ansai then ans,ai;,writeln(ans);/*,输出,t,时间内可采到的草药的最大总价值*,/,.,37,Chain,拜特兰并不总是一个非常民主的国家，也有一些阴暗的历史。一个美好的日子，拜特将军该国的统帅作了一个用以结束长期内战的决定，释放被关押的反对派。然而，他并未让反对派的领袖拜特萨直接自由，而是用一根,“,拜特链,”,将拜特萨锁在墙边,.,该链子由很多环和固定在墙上栅栏组成。尽管环并未和栅栏融合在一起，但想除去它们却非常困难。,“,将军，你为什么要用链子将我锁在墙边而不让我自由！,”,拜特萨大叫道。,“,拜特萨，你并未完全被链子锁住，我可以坦率的告诉你，你完全可以从栅栏上解下环。,”,拜特将军不忠地回答，同时他补充说，,“,但是，你必须在夜里工作，一个小时之内完成，不能弄出任何声音，否则，我将按有关法律制罪。,”,。为了帮助拜特萨！链子上的环按整数,1,2,n,进行了编号。我们可以按照以下规则解开环：,只有一个环时可以被连接到栅栏或从栅栏上拆开。,第,1,号环总能进行连接或拆开,如果,1,.,k-1 (1=kn),环都被拆开，第,k,个环被连接时,此时我们能连接或拆开第,k+1,个环,.,38,写一个程序：文本文件,LAN.IN,描述了拜特链的构成,计算拆除拜特链上全部环的最少操作次数,将结果写入文本文件,LAN.OUT.,输入：在文本文件,LAN.IN,中的第,1,行有一个整数,n, 1=nm then break; /*,计算最后一行的起始单词序号,cn*/,cni; inc(cn);,if cnn/*,若单词,n,的长度超过,m,，失败退出*,/,then writeln(f0,Print is impossible.);continue ;,if cn=1/*,若,n,个单词的长度不足一行，则输出结果*,/,then writeln(f0,0);writeln(f0,Line 1 : ,n);continue ; /*then*/,50,动态程序设计,51,ansmaxint;,for i1 to n do c0,imaxint;,c0,00;,for k1 to n-1 do /*,递推每一行*,/,for i0 to k-1 do ck,imaxint;/*,前,k,行的状态转移方程初始化*,/,for ik to n-1 do /*,枚举第,k,行的尾单词*,/, ck,imaxint;,for ji-1 downto k-1 do /*,枚举第,k-1,行的尾单词*,/,if (lgj+1,i=m) and (ck-1,j+(m-lgj+1,i),3,ck,i),then ck,ick-1,j+ (m-lgj+1,i),3,;/*for*/,for icn-1 to n-1 do/*,记录目前最“漂亮值”和方案*,/,if ck,ians then ansck,i; akk; aii /*then*/,;/*for*/,52,输出方案,procedure putout(k,i:integer);/*,前,k,行为前,i,个单词。输出该方案*,/,var,j:integer;, if k=0 then exit; /*,递归边界*,/,for ji-1 downto k-1 do /*,计算第,k-1,行的尾单词,j*/,if (lgj+1,i0)and(y20)and(y1=n)and(y2=n)or(j=k),then continue; /*,若两条路径的,当前列位置越出界外或者同处一行的话，则继续枚举,*,/,fi,j,kmax(fi,j,k,fi-1,j,k); /*,情况,1,：两条路径向右走*,/,if j-1k then fi,j,kmax(fi,j,k,fi-1,j-1,k); /*,情况,2,：第,1,条路径向下走，第,2,条路径向右走*,/,if jk-1 then fi,j,kmax(fi,j,k,fi-1,j,k-1); /*,情况,3,：第,2,条路径向下走，第,1,条路径向右走*,/,fi,j,kmax(fi,j,k,fi-1,j-1,k-1); /*,情况,4,：两条路径向下走*,/,fi,j,kfi,j,k+aj,y1+ak,y2; /*,取走（,j,y1,）,和（,k,y2,）的数字*,/,;/*for*/,writeln(fm+n-2,m,m-1);/*,输出两条路径上的最大数和*,/,59,最佳旅行路线问题,你在加拿大航空公司组织的一次竞赛中获奖，奖品是一张免费机票，可在加拿大旅行，从最西的一个城市,1,出发，单方向从西向东经若干城市到达最东的城市,n,（必须到达最东的城市,n,）；然后再单方向从东向西飞回起点城市,1,（可途径若干城市）。除起点城市,1,外，任何城市只能访问次，起点城市,1,被访问次：出发一次；返回一次。除指定的航线外，不允许乘其他航线也不允许使用其他交通工具。求解的问题是：给定城市表列及两城市之间的直通航线表列，请找出一条旅行路线，在满足上述限制条件下，使访问的城市数尽可能多。,60,旅行路线问题满足,“,无后效性原则,”,将旅行路线拆分成两条由东到西的航线。设阶段为,P,1,P,2,，即第,1,条航线目前到达城市,p,1,，第,2,条航线目前到达城市,p,2,。假如阶段,P,1,P,2,可到达阶段,Q,1,Q,2,，则必须满足的条件就是,:P,1,Q,1,或,P,2,j,或者,i=j=n,时,i,的前驱城市,k,；,ij,，或,i=j=n,时，到达,i,的前趋顶点,k,与,j,的两条路线的所需乘航线之和也一定最大，否则与,fi,，,j,最大矛盾。若,ij,时，结论同理可得。由此得出如下状态转移方程：,f i,，,i,无意义,(1ij)or(i=n)and(j=n) /*,计算第一种情况*,/,then for k1 to bi do /*,枚举,i,的每个前驱顶点，计算经由前驱顶点到达顶点,i,和到达顶点,j,的最佳方案*,/,if gi,ki then fi,jmax(fi,j,fgi,k,j+1);,continue ; /*,继续枚举下一对顶点*,/,if ij /*,计算第二种情况：枚举,j,的每个前驱顶点，计算到达顶点,i,和经由前驱顶点到达顶点,j,的最佳方案，从中找出到达顶点,i,和到达顶点,j,的最佳方案*,/,then for k1 to bj do if gj,k0 mod 4,(3+2)mod 4(3+1)mod 4,。,但是我们可