《动态规划（动态程序设计）王建德》由会员分享，可在线阅读，更多相关《动态规划（动态程序设计）王建德（247页珍藏版）》请在金锄头文库上搜索。
1、动态规划,上海市控江中学 王建德,讨论的问题,1、动态规划的基本概念 2、动态规划的基础题型 3、动态规划的综合题型,基本概念,动态程序设计是解决多阶段决策最优化问题的一种思想方法。所谓“动态”，指的是在问题的多阶段决策中，按某一顺序，根据每一步所选决策的不同，将随即引起状态的转移，最终在变化的状态中产生一个决策序列。动态规划就是为了使产生的决策序列在符合某种条件下达到最优。,问题的引出： P是出发点，从P到A，求最短路径,思路,令 从P A的最短路径为P(A)；P(A) = minP(B)+2, P(C)+3；,从P B的最短路径为P(B)；P(B) = minP(D)+1, P(E)+2；
2、,从P C的最短路径为P(C); P(C) = minP(E)+5, P(F)+4；,上述递推公式告诉我们，要求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)（顺推）。,数据结构 将每条路经的长度存在数组中东西方向上的道路长度存在两维数组h43中,规定数组的第一维为行号，第二维为列号。,h43 = 3,2,3,2,1,4,3,4
3、,5,3,1,2;,南北方向上道路长度存至数组v34中，也规定第一维为行号，第二维为列号。,v34 =2, 2, 3, 4,4, 1, 2, 4,1, 2, 2, 3;,求解过程为从(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;,阶段1: P01 = P00+h00 = 0+3 = 3; P10 = P00+v00 = 0+2 = 3;,阶段2: P11 = min P01+v01, P10
4、+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 P
5、31 = 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,综上，数组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数
6、组数据,圆圈内为路口对P点的最小距离,箭头为最佳行走路径。,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 pijmin( ( pi-1j+vi-1j), (pij-1+hij-1) ); For i3 downto 0 do /*输出每个路口对P点的最小距离*/ for j 0 to 3 do write(pij:4) writeln; ;/*for*/,程序,阶段：据空间顺序或时间
7、顺序对问题的求解划分阶段。 状态：描述事物的性质，不同事物有不同的性质，因而用不同的状态来刻画。对问题的求解状态的描述是分阶段的。 决策：根据题意要求，对每个阶段所做出的某种选择性操作。 状态转移方程：用数学公式描述与阶段相关的状态间的演变规律。 多阶段决策过程：将所研究的过程划分为若干个相互联系的阶段，在求解时，对每一个阶段都要做出决策，前一个决策确定以后，常常会影响下一个阶段的决策。,动态规划的几个要素,“最优性原理”：不论初始状态和第一步决策是什么，余下的决策相对于前一次决策所产生的新状态，构成一个最优决策序列。 最优决策序列的子序列，一定是局部最优决策子序列。注意包含有非局部最优的决策
8、子序列，一定不是最优决策序列,例如贪心法。,动态规划的依据“最优性原理”,动态规划的指导思想,在做每一步决策时，列出各种可能的局部解，之后依据某种判定条件，舍弃那些肯定不能得到最优解的局部解。这样，在每一步都经过筛选，以每一步都是最优的来保证全局是最优的。筛选相当于最大限度地有效剪枝（从搜索角度看），效率会十分高。但它又不同于贪心法。 贪心法:产生一个按贪心策略形成的判定序列，该序列不保证解是全局最优的，因为有些问题不符合最优性原理。 动态规划:产生许多判定序列，再按最优性原理对这些序列加以筛选，去除那些非局部最优的子序列。,2、动态规划的基础题型,1、路径问题 2、01背包问题 3、求最佳子
9、序列问题 4、双重动态规划,路径问题的讨论,问题的一般形式： 1、计算所有路径方案 2、计算一条最佳路径 3、计算两条最佳路径（多进程的最优化决策） 一般方法： 按照出发点走出的步数划分阶段，将当前步可达的顶点集定义为状态，当前步如何走定义为决策。注意： 1、可能需要将原题转化为路径问题 2、如果最佳路径问题不满足最优子结构特征特征的话，可以转化为判定性问题求解。,一、计算所有方案,对于一些阶段性强、但不属于最优化的问题，是否也可以借助动态规划方法呢？如果我们可以找出状态转移的关系，并在状态转移方程,中去掉最佳性要求opt（min或max），将扩展子状态的所有行动作为决策，则可以例举出由初始状
10、态至目标状态的所有方案。显然，在计数类问题中使用这种方法要比回溯法等搜索算法简捷许多。,例题 过河卒,如图，A点有一个过河卒，需要走到目标B点。卒行走的规则：可以向下、或者向右。,同时在棋盘上的任一点有一个对方的马（如上图的C点）,该马所在的点和所有跳跃一步可达的点称为对方马的控制点。例如上图C点上的马可以控制8个点（图中的P1，P2.P8）。卒不能通过对方马的控制点。 棋盘用坐标表示，A点（0，0）、B点（n，m）(n,m为不超过20的整数,并由键盘输入)，同样马的位置坐标是需要给出的（约定：CA，同时CB）。现在要求你计算出卒从A 点能够到达B点的路径的条数。 输 入：键盘输入B点的坐标(
11、n,m)以及对方马的坐标（X，Y） 输 出：屏幕输出一个整数（路径的条数）。,按照题意，对方的马所在的点和所有跳跃一步可达的点称为对方马的控制点，卒不能通过对方马的控制点。在卒出发之前，必须计算对方马的所有控制点。显然，若（0，0）或（n,m）为控制点，则输出路径数为0。设 const move:array18,12of integer /* movek，12为马沿k方向跳跃一步的水平增量和垂直增量*/ =(1,-2),(1,2),(2,1),(2,-1),(-1,2),(-1,-2),(-2,1),(-2,-1)； var list:array-120,-120of comp；/*listi
12、,j为卒从(0,0)到(i,j)的路径数*/ can:array020,020of boolean；/*cani,j为允许卒通行(i,j)的标志*/,1、计算对方马的控制点,设马的初始位置为（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； ；
13、/*for*/ if (not can0,0)or(not cann,m) /*若卒的起点和终点为控制点，则输出路径数0*/ then writeln(0) else计算和输出卒从（0，0）走到（n,m）点的路径数listn,m ；/*else*/,我们按照由上而下、由左而右的顺序，将卒可能到达的每一个位置（i,j）(0in，0jm)设为阶段和状态。 首先，将卒的出发点（0，0）的路径数设为1，该位置设为控制点（list0,01;can0,0 fals）。然后从（0，0）出发，按照由上而下、由左而右的顺序计算卒经过每一个可行点的路径数:若（i，j）为可行点，则走前位置（i-1,j）和（i,j-
14、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）点的路径条数,计算一条最佳路径,以路径长度划分阶段，从出发点走i步可达的顶点集合为状态。设fi,j为到达阶段i的顶点j的最优解。 枚
