动规-路径.ppt

单击此处编辑母版标题样式,单击此处编辑母版文本样式,第二级,第三级,第四级,第五级,*,如下图所示为一个数字三角形，请编程计算从顶到底的某处的一条路径，使该路径所经过的数字总和最大。（只要求输出总和）,规定：,一步可沿左斜线向下或右斜线向下走；,图形行数小于等于,100,；,三角形中的数字为,0,，,1,，,，,99,；,输入,:,右下图数据应以如下所示格式输入,5(,行数,),7,3 8,8 1 0,2 7 4 4,4 5 2 6 5,输出：,30,数字三角形,按照三角形的行进行阶段,划分,，若行数为,n,，,则可把问题看做一个,n-1,个阶段的决策问题。先求出第,n-1,阶段,各点,到第n,行的最大和，再依次求出第,n-2,阶段、第,n-3,阶段,第,1,阶段各点至第,n,行的最大和。,设,fi,j,为从第,i,阶段中的第,j,个,点至第,n,行的最大和；,由于,fi,j,只和第,i+1,阶段的状态和本阶段的点有关系，符合无后效性原则；在每一个阶段都要求出这个阶段的各个点到第,n,行的最大和，也符合最优化原则。因此可以用动态规划的方法来求解，以走到每一行时所在的位置作为状态，决策就是向左下走或向右下走。其状态转移方程可以写为：,fi,j,=max ai,j+fi+1,j,ai,j+fi+1,j+1,（,i=1,2,3,4,n-1,1=j=i,）,fn,j,=,an,j,（,1=jfi+1,j+1,then,fi,j,:=fi+1,j+ai,j,else,fi,j,:=fi+1,j+1+ai,j;,writeln(f1,1);,end.,阶段,状态,决策,状态转移方程,4,5,2,6,5,7,12,10,10,20,13,10,23,21,30,下图所示是城市道路示意图。每条边上的数字为该段街道的长度。求从,A,到,B,地（只允许往右和往上走）的最短路径长度。,1 3 2 3,2 2 1 4,2 3 4 5,2 3 1 2,2 3 2,1 4 2,2 1 1,2 2 3,3 3 4,A（0，0）,B（3，4）,街道最短路径,我们以图中的,对角线行,来划分阶段，共,m+n,个,阶段,。设,di,j,表示点,(0,0),到点,(,i,j),的最短路径长度，,vi,j,表示点,(,i-1,j),到点,(,i,j),的竖向距离，,hi,j,表示点,(,i,j-1),到点,(,i,j),的横向距离，则,di,j,=,min,di-1,j+,vi,j,di,j-1+,hi,j,1 3 2 3,2 2 1 4,2 3 4 5,2 3 1 2,2 3 2,1 4 2,2 1 1,2 2 3,3 3 4,A（0，0）,B（3，4）,2,5,7,1,4,6,9,3,5,6,10,7,6,8,13,8,8,9,11,0,var,i,j,k,t,m,n:integer,;,hv:array0.100,0.100 of integer;,d:array0.100,0.100 of,longint,;,function,min(x,y:integer):longint,;,begin,if xy then min:=y,else min:=x;,end;,begin,readln(m,n);m+1,行，,n+1,列,for i:=0 to m do,东西向,begin,for j:=1 to n do,read(hi,j,);,readln,end;,for i:=1 to m do,begin,南北向,for j:=0 to n do,read(vi,j,);,readln,end;,d0,0:=0;,for i:=1 to m do,di,0:=di-1,0+vi,0;,for j:=1 to n do,d0,j:=d0,j-1+h0,j;,初值,for k:=,2 to,m+n,do,for i:=,1 to k-1,do,if(i=m)and(,k-i,=n)then,begin,j:=,k-i,;,di,j,:=min(d,i-1,j,+vi,j,d,i,j-1,+hi,j);,end;,writeln(dm,n,);,end.,我们也可以以图中的行来划分阶段。设,fi,j,表示点,(0,0),到点,(,i,j),的最短路径长度，,dji,j,表示点,(,i-1,j),到点,(,i,j),的竖向距离，,dii,j,表示点,(,i,j-1),到点,(,i,j),的横向距离，则,fi,j,=,min,fi-1,j+,dji,j,fi,j-1+,dii,j,1 3 2 3,2 2 1 4,2 3 4 5,2 3 1 2,2 3 2,1 4 2,2 1 1,2 2 3,3 3 4,A（0，0）,B,（,3,4）,2,5,7,1,4,6,9,3,5,6,10,7,6,8,13,8,8,9,11,0,此算法中状态转移不全在两个阶段之间进行，但解题方法的本质没变。在使用动态规划方法解题时，我们应掌握其基本解题模式针对具体问题进行灵活应变。,Vardi,dj:array0.100,0.100of,longint,;,i,j,m,n,min:longint,;,f:array0.100,0.100of,longint,;,begin,readln(m,n,);,for i:=0 to m do,for j:=1 to n do,read(dii,j,);,for i:=1 to m do,for j:=0 to n do,read(dji,j,);,f0,0:=0;,for i:=1 to m do,fi,0:=fi-1,0+dji,0;,for j:=1 to n do,f0,j:=f0,j-1+di0,j;,for i:=1 to m do,for j:=1 to n do,begin,min:=,maxlongint,;,if fi-1,j+dji,jmin then min:=fi-1,j+dji,j;,if fi,j-1+dii,jmin then min:=fi,j-1+dii,j;,fi,j:=min;,end;,writeln(fm,n,);,end.,问题描述,设有下列图形的网络图，如图所示。,其中：,S1,S2,S3,S4,S5,为起点，可以从任一个起点开始。,A1,A2,C3,C4,为中间点。,T1,T2,T5,为结束点，可以在任一点结束。边上数字表示,2,个点之间的距离，如,S1-A1,距离为,3,。从任一起点开始，到任一终点结束的一条路径，如,S3-A2-B3-C3-T4,路径上距离的和为,5+12+14+6=37,。从图中可看到，从起点到终点存在许多条不同路径，且路径上距离的和也不相同。,问题,：当网络和距离给出之后，找出一条路径，使路径上距离的和为最小。,输入文件,3.,in,共,m,行，第一行含二个正整数,n,m(di,j,2+ei,j+1,then,ei,j:=di,j,2+ei,j+1,else ei,j:=di,j,1+ei-1,j+1;,en,j,:=dn,j,1+en-1,j+1;,end,else,for i:=1 to n-1 do,if di,j,2+ei,j+1di,j,3+ei+1,j+1,then ei,j:=di,j,3+ei+1,j+1,else ei,j:=di,j,2+ei,j+1;,j:=1;,for i:=2 to n do,if ei,1ej,1 then j:=i;,write(ej,1);,end.,花店橱窗布置,假设以最美观的方式布置花店的橱窗，,有,F,束花,，每束花的品种都不一样，同时，,至少有同样数量的花瓶,，被按顺序摆成一行。花瓶的位置是固定的，并从左到右，从,1,到,V,顺序编号，,V,是花瓶的数目,，编号为,1,的花瓶在最左边，编号为,V,的花瓶在最右边。花束可以移动，并且每束花用,1,到,F,的整数惟一标识，,标识花束的整数决定了花束在花瓶中的顺序,即如果,I J，,则花束,I,必须放在花束,J,左边的花瓶中,。例如，假设杜鹃花的标识数为,1,，秋海棠的标识数为,2,，康乃馨的标识数为,3,，所有的花束在放入花瓶时必须保持其标识数的顺序，即：杜鹃花必须放在秋海棠左边的花瓶中，秋海棠必须放在康乃馨左边的花瓶中。如果花瓶的数目大于花束的数目，则多余的花瓶必须空，即每个花瓶中只能放一束花。每一个花瓶的形状和颜色也不相同，因此，当各个花瓶中放人不同的花束时会产生不同的美学效果，并以美学值,(,一个整数,),来表示，空置花瓶的美学值为,0,。在上述例子中，花瓶与花束的不同搭配所具有的美学值，可以用如下表格表示：花瓶,1,花瓶,2,花瓶,3,花瓶,4,花瓶,5,杜鹃花,7,23,-5,-24,16,秋海棠,5,21,-4,10,23,康乃馨,-21,5,-4,-20,20,根据表格，杜鹃花放在花瓶,2,中会显得非常好看，但若放在花瓶,4,中则显得很难看。为取得最佳美学效果，,必须在保持花束顺序的前提下，使花的摆放取得最大的美学值,，如果具有最大美学值的摆放方式不止一种，则输出任何一种方案即可。题中数据满足下面条件：,1,F100，FV100，50A,i,j,50，,其中,A,i j,是花束,I,摆放在花瓶,J,中的美学值。,输入文件,flower.inp,，,第一行包含两个整数,F，V。,随后的,F行中，每行包含,V,个整数。,输出文件,flower.ans,，,程序所产生摆放方式的美学值。,样例输入：,3 5,7,23,-5 -24 16,5 21 -4,10,23,-21 5 -4 -20,20,样例输出：,53,算法分析：,将摆放方案的要求用表格表现出来,则摆放方案需要满足：每行选且只选一个数,(,花瓶,);,摆放方案的相邻两行中，下面一行的花瓶编号要大于上面一行的花瓶编号两个条件。这时可将问题转化为：,给定一个数字表格，要求编程计算从顶行至底行的一条路径,使得这条路径所经过的数字总和最大,(,要求每行选且仅选一个数字,),。同时，对于路径中相邻两行的数字，必须保证下一行数字的列数大于上一行数字的列数。,假设用,bi,j,表示美学值表格中第,i,行的第,j,个数字，用,qi,j,表示从表格最底层到,bi,j,这个数字的最佳路径（路径经过的数字总和最大）的数字和，则状态转移方程为：,qi,，,v+1=-,（,1=i=f,）,qf,j,=,bf,j,(1=j=v),qi,j,=max qi+1,k(,jk=v+1,)+,ai,j,(1=i=f,1=j=v),这样得出的,maxq1,j(1=j,besti,j,then,besti,j,:=besti+1,k+ai,j;,end;,max:=-99999999;,for j:=1 to v do,选择全局最优解,if best1,jmax then max:=best1,j;,writeln(max,);,end.,滑雪,问题描述,:,小明喜欢滑雪，因为滑雪的确很刺激，可是为了获得速度，滑的区域必须向下倾斜，当小明滑到坡底，不得不再次走上坡或等着直升机来载他，,小明想知道在一个区域中最长的滑坡,。滑坡的长度由滑过点的个数来计算，区域由一个二维数组给出，数组的每个数字代表点的高度。,下面是一个例子：,1 2 3 4 5,16 17 18 19 6,15 24 25 20 7,14 23 22 21 8,13 12 11 10 9,一个人可以从某个点滑向上下左右相邻四个点之一，当且仅当高度减小，在上面的例子中，一条可行的滑坡为,25-24-17-16-1,，当然,25-24-233-2-1,更长，事实上这是最长的一条。,输入文件,4.,in:,输入的第一行为表示区域的二维数组的行数,R,和列数,C，,下面是,R,行，每行有,C,个数代表高度。,输出文件,4.,out:,输出区域中最长的滑坡长度，如上面的例子中输出为,25,。,样例：,输入,5 5,1 2 3 4 5,16 17 18 19 6,15 24 25 20 7,14 23 22 21 8,13 12 11 10 9,输出,25,const,dx:array1.4 of,shortint,=(-1,0,1,0);,dy:array1.4 of,shortint,=(0,1,0,-1);,var,r,c,i,j,p,t,ans:longint,;,m:array1.100,1.100 of word;,f:array1.100,1.100 of word;,begin,readln(r,c,);,for i:=1 to r do,for j:=1 to c do read(mi,j);,ans,:=0;,for i:=1 to r do,for j:=1 to c do,begin,t:=,search(i,j),;fi,j:=t;,if t,ans,then,ans,:=t;,end;,writeln(ans,);,end.,function,search(x,y:longint):word,;,var,i,t,tmp,nx,ny:longint,;,begin,if fx,y0 then,begin,search:=fx,y;,exit;,end;,t:=1;,for i:=1 to 4 do,begin,nx,:=,x+dxi,;,ny,:=,y+dyi,;,if,(,nx,=1)and(nx=1),and(ny,=c),and,(mx,yt then t:=,tmp,;,end;,end;,search:=t;,end;,坐标增量,fi，j,表示到点（,i，j）,为止的最大长度,读入各点的高度,用递归按行逐点求出区域中到此点的最长路径并作记录,此点长度已经求出，不必进行进一步递归,从四个方向上搜索能到达（,x,y）,的点,递归进行记忆化搜索,一般说来，动态规划总要遍历所有的状态，而搜索可以排除一些无效状态。更重要的是搜索还可以剪枝，可能剪去大量不必要的状态，因此在空间开销上往往比动态规划要低很多。,如何协调动态规划的高效率与高消费之间的矛盾呢？有一种折中的方法就是记忆化算法。在求解的时候还是按着自顶向下的顺序，但是每求解一个状态，就将它的解保存下来，以后再次遇到的时候，就不必要重新求解了。记种方法综合了搜索和动态规划两方面的优点，是很有实用价值的。,问题描述：,设有,N*N,的方格图(,N=10,我们将其中的某些方格中填入正整数,而其他的方格中则放入数字0。如下图所示（见样例）：,某人从图的左上角的,A,点出发，可以向下行走，也可以向右走，直到到达右下角的,B,点。在走过的路上，他可以取走方格中的数（取走后的方格中将变为数字0）。,此人从,A,点到,B,点共走两次，试找出2条这样的路径，使得取得的数之和为最大。,方格取数,输入文件6.,in,输入的第一行为一个整数,N（,表示,N*N,的方格图），接下来的每行有三个整数，前两个表示位置，第三个数为该位置上所放的数。一行单独的0表示输入结束。,输出文件6.,out,一行，一个整数，表示2条路径上取得的最大的和。,样例,：,输入,8,2 3 13,2 6 6,3 5 7,4 4 14,5 2 21,5 6 4,6 3 15,7 2 14,0 0 0,输出,67,考虑两个人同时从,A,出发，则需考虑两个人到达任意两个格子(,i1，j1),与(,i2，j2),的情况，显然要到达这两个格子，其前一状态必为,(,i1-1，j1)，(i2-1，j2)；,(i1-1，j1)，(i2，j2-1)；,(i1，j1-1)，(i2-1，j2)；,(i1，j1-1)，(i2，j2-1),四种情况之一，类似地，可以推导出：,设,p=max(sumi1-1,j1,i2-1,j2,sumi1-1,j1,i2,j2-1,sumi1,j1-1,i2-1,j2,sumi1,j1-1,i2,j2-1)，,则,sumi1,j1,i2,j2=,0,当,i1=0,或,j1=0,或,i2=0,或,j2=0,p+datai1,j1,当,i1,j1,i2,j2,均不为零，且,i1=i2，j1=j2,p+datai1,j1+datai2,j2,当,i1,j1,i2,j2,均不为零,且,i1i2,或,j1j2,