动态规划(动态程序设计)课件

单击此处编辑母版标题样式,单击此处编辑母版文本样式,第二级,第三级,第四级,第五级,*,动态规划,上海市控江中学 王建德,动态规划上海市控江中学 王建德,1,讨论的问题,1、动态规划的基本概念,2、动态规划的基础题型,3、动态规划的综合题型,讨论的问题1、动态规划的基本概念,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，求最短路径,DAGCKBNPOMJFHELI31234521432314,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；,思路令从P B的最短路径为P(B)；P(B) = min,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)（顺推）。,上述递推公式告诉我们，要求P(A)需要先求出阶段5中的,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,h30h31h32h20h,7,数据结构,将每条路经的长度存在数组中东西方向上的道路长度存在两维数组h43中,规定数组的第一维为行号，第二维为列号。,h43 = 3,2,3,2,1,4,3,4,5,3,1,2;,数据结构h43 = 3,2,3,2,1,4,8,南北方向上道路长度存至数组v34中，也规定第一维为行号，第二维为列号。,v34 =2, 2, 3, 4,4, 1, 2, 4,1, 2, 2, 3;,南北方向上道路长度存至数组v34中，也规定第一维为行,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;,求解过程为从(0, 0)到(3, 3)求最短路径问题定义二维,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,阶段1: P01 = P00+h0,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点的最小距离,箭头为最佳行走路径。,综上，数组P的通项表示为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*/,程序,for j 1 to 4 do,13,阶段：据空间顺序或时间顺序对问题的求解划分阶段。,状态：描述事物的性质，不同事物有不同的性质，因而用不同的状态来刻画。对问题的求解状态的描述是分阶段的。,决策：根据题意要求，对每个阶段所做出的某种选择性操作。,状态转移方程：用数学公式描述与阶段相关的状态间的演变规律。,多阶段决策过程：将所研究的过程划分为若干个相互联系的阶段，在求解时，对每一个阶段都要做出决策，前一个决策确定以后，常常会影响下一个阶段的决策。,动态规划的几个要素,阶段：据空间顺序或时间顺序对问题的求解划分阶段。动态规,14,“最优性原理”：不论初始状态和第一步决策是什么，余下的决策相对于前一次决策所产生的新状态，构成一个最优决策序列。,最优决策序列的子序列，一定是局部最优决策子序列。注意包含有非局部最优的决策子序列，一定不是最优决策序列,例如贪心法。,动态规划的依据“最优性原理”,“最优性原理”：不论初始状态和第一步决策是什么,15,动态规划的指导思想,在做每一步决策时，列出各种可能的局部解，之后依据某种判定条件，舍弃那些肯定不能得到最优解的局部解。这样，在每一步都经过筛选，以每一步都是最优的来保证全局是最优的。筛选相当于最大限度地有效剪枝（从搜索角度看），效率会十分高。但它又不同于贪心法。,贪心法:产生一个按贪心策略形成的判定序列，该序列不保证解是全局最优的，因为有些问题不符合最优性原理。,动态规划:产生许多判定序列，再按最优性原理对这些序列加以筛选，去除那些非局部最优的子序列,。,动态规划的指导思想在做每一步决策时，列出各种可能的局部解，之,16,2、动态规划的基础题型,1、路径问题,2、01背包问题,3、求最佳子序列问题,4、双重动态规划,2、动态规划的基础题型1、路径问题,17,路径问题的讨论,问题的一般形式：,1、计算所有路径方案,2、计算一条最佳路径,3、计算两条最佳路径（多进程的最优化决策）,一般方法：,按照出发点走出的步数划分阶段，将当前步可达的顶点集定义为状态，当前步如何走定义为决策。注意：,1、可能需要将原题转化为路径问题,2、如果最佳路径问题不满足最优子结构特征特征的话，可以转化为判定性问题求解。,路径问题的讨论问题的一般形式：,18,一、计算所有方案,对于一些阶段性强、但不属于最优化的问题，是否也可以借助动态规划方法呢？如果我们可以找出状态转移的关系，并在状态转移方程,中去掉最佳性要求opt（min或max），将扩展子状态的所有行动作为决策，则可以例举出由初始状态至目标状态的所有方案。显然，在计数类问题中使用这种方法要比回溯法等搜索算法简捷许多。,一、计算所有方案 对于一些阶段性强、但不属于最优化的问,19,例题 过河卒,如图，A点有一个过河卒，需要走到目标B点。卒行走的规则：可以向下、或者向右。,例题 过河卒 如图，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）,输 出：屏幕输出一个整数（路径的条数）。,同时在棋盘上的任一点有一个对方的马（如上图的C点）,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*/,设马的初始位置为（x,y）。按照下述方式计算can序列can,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,计算一条最佳路径以路径长度划分阶段，从出发点走i步可达的顶点,25,寻宝游戏,寻宝游戏,26,分析,在“藏宝图”中寻求一条含len个顶点的路径，使得,(1klen,)(x,k,y,k,)-a,k,),2,最小。,分析在“藏宝图”中寻求一条含len个顶点的路径，使得(1,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; /*数列与表格的接近程度*/,数据结构const,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);,输入信息，计算c0的初始值readln(f,n,m);,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; /*计算ansminc1I,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时间内可采到的草药的最大总价值*/,.,var,37,Chain,拜特兰并不总是一个非常民主的国家，也有一些阴暗的历史。一个美好的日子，拜特将军该国的统帅作了一个用以结束长期内战的决定，释放被关押的反对派。然而，他并未让反对派的领袖拜特萨直接自由，而是用一根“拜特链”将拜特萨锁在墙边.该链子由很多环和固定在墙上栅栏组成。尽管环并未和栅栏融合在一起，但想除去它们却非常困难。,“将军，你为什么要用链子将我锁在墙边而不让我自由！”拜特萨大叫道。“拜特萨，你并未完全被链子锁住，我可以坦率的告诉你，你完全可以从栅栏上解下环。”拜特将军不忠地回答，同时他补充说，“但是，你必须在夜里工作，一个小时之内完成，不能弄出任何声音，否则，我将按有关法律制罪。”。为了帮助拜特萨！链子上的环按整数1,2,n进行了编号。我们可以按照以下规则解开环：,只有一个环时可以被连接到栅栏或从栅栏上拆开。,第1号环总能进行连接或拆开,如果1,.,k-1 (1=kn)环都被拆开，第k个环被连接时, 此时我们能连接或拆开第k+1个环.,Chain 拜特兰并不总是一个非常民主的国家，也有一些阴暗的,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*/,计算lg和最后一行的起始单词序号cnreadln(f,n,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*/,ansmaxint;,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);/*输出两条路径上的最大数和*/,read(m,n);/*输入行数和列数*/,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,kj then fi,jmax(fi,j,fi,gj,k+1);,continue ; /*,继续枚举下一对顶点*,/,;/*for*/,writeln(fn,n-2); /*,输出最多可能访问的顶点数*,/,;/*make*/,通过动态规划计算和输出最多可能访问的顶点数proc make,65,对于一些阶段性明显、但不具备最优子结构特征的问题，可以考虑将指标函数值当作“状态”，计算每一个可能的状态是否可达，从而变最优化问题为能否到达指定状态的判定性问题。再借用动态规划思想，用递推方式计算最佳值（即按照状态值递增的顺序寻找第一个可达的状态）。,计算一些阶段性明显、但不具备最优子结构特征的路径问题,对于一些阶段性明显、但不具备最优子结构特征的问题,66,例题 mod 4 最优路径问题,在上图中找出从第1点到第4点的一条路径，要求路径长度mod 4的余数最小。,例题 mod 4 最优路径问题,67,该问题最优子结构特征,例如一条最优路径（3+2+3）mod 4=0。在它走到第2点的、第3点的路径长度mod 4的余数不一定是