ACM培训03-动态规划

10动态规划图1DAGCKBNPOMJFHELI312345214323142212223344阶段1阶段2阶段3阶段4阶段5任务：P是出发点，从P到A，求最短路径（图1）思路1.先看第5阶段，到达A点有两条路–BA，需要2km–CA，需要3km2.令–从PA的最短路径为P(A)；–从PB的最短路径为P(B)；–从PC的最短路径为P(C)……–P(A)=min{P(B)+2,P(C)+3}；–P(B)=min{P(D)+1,P(E)+2}；–P(C)=min{P(E)+5,P(F)+4}；P(A)=min{P(B)+2,P(C)+3}；P(B)=min{P(D)+1,P(E)+2}；P(C)=min{P(E)+5,P(F)+4}；D1B2A235P(B)EC4P(C)FP(N)=2;P(O)=3;上述递推公式告诉我们，要求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)。…3.选择数据结构，将每条路经的长度存在数组中。东西方向上的道路长度存在两维数组h[4][3]中规定数组的第一维为行号，第二维为列号。312345214323h[4][3]={{3,2,3},{2,1,4},{3,4,5},{3,1,2}};0121023南北方向上道路长度存至数组v[3][4]中，也规定第一维为行号，第二维为列号。0123210223441241223v[3][4]={{2,2,3,4},{4,1,2,4},{1,2,2,3}};4.为了计算方便，将图1改为图2h[3][0]h[3][1]h[3][2]h[2][0]h[2][1]h[2][2]h[1][0]h[1][1]h[1][2]h[0][0]h[0][1]h[0][2]v[2][0]v[2][1]v[2][2]v[2][3]v[1][0]v[1][1]v[1][2]v[1][3]v[0][0]v[0][1]v[0][2]v[0][3](3,3)0213213yx图25.求解过程为从(0,0)到(3,3)求最短路径问题定义二维数组，P[4][4]={{0,0,0,0},{0,0,0,0},{0,0,0,0},{0,0,0,0}},第一维为行，第二维为列。这时P(O)为P[0][1]；P(N)为P[1][0]；…P(A)为P[3][3]，以下为分阶段递推求解过程。对于阶段1:P[0][0]=0;P[0][1]=P[0][0]+h[0][0]=0+3=3;P[1][0]=P[0][0]+v[0][0]=0+2=2;对于阶段2P[1][1]=min{P[0][1]+v[0][1],P[1][0]+h[1][0]}=min{3+1,2+2}=4P[0][2]=P[0][1]+h[1][0]=3+2=5P[2][0]=P[1][0]+v[1][0]=2+4=6对于阶段3P[1][2]=min{P[0][2]+v[0][2],P[1][1]+h[1][1]}=min{5+3,4+1}=5P[0][3]=P[0][2]+h[0][2]=5+3=8P[2][1]=min{P[1][1]+v[1][1],P[2][0]+h[2][0]}=min{4+1,6+1}=5P[3][0]=P[2][0]+v[2][0]=6+1=7对于阶段4P[1][3]=min{P[0][3]+v[0][3],P[1][2]+h[1][2]}=min{8+4,5+4}=9P[2][2]=min{P[1][2]+v[1][2],P[2][1]+h[2][1]}=min{5+2,5+4}=7P[3][1]=min{P[2][1]+v[2][1],P[3][0]+h[3][0]}=min{5+2,7+3}=7对于阶段5P[2][3]=min{P[1][3]+v[1][3],P[2][2]+h[2][2]}=min{9+4,7+5}=12P[3][2]=min{P[2][2]+v[2][2],P[3][1]+h[3][1]}=min{7+2,7+1}=8最后P[3][3]=min{P[2][3]+v[2][3],P[3][2]+h[3][2]}=min{12+3,8+2}=10综上，数组P的通项表示为P[i][j]=min((p[i-1][j]+v[i-1][j]),(p[i][j-1]+h[i][j-1]))(i,j0)P[0][j]=P[0][j-1]+h[0][j-1](i=0,j0)P[i][0]=P[i-1][0]+v[i-1][0](i0,j=0)下面给出P数组中的数据01232100358245965712778103数组P的通项表示为P[i][j]=min((p[i-1][j]+v[i-1][j]),(p[i][j-1]+h[i][j-1]))(i,j0)P[0][j]=P[0][j-1]+h[0][j-1](i=0,j0)P[i][0]=P[i-1][0]+v[i-1][0](i0,j=0)画出用动态规划思想求出的各个路口对P点的最小距离。图中圆圈里就是这个距离。箭头表示所寻得的最佳行走路径。（图3）312345214323142212223344026734575578891210P点A点图3参考程序如下#includeiostream.hintmin(int,int);intmain()//主函数{inth[4][3]={{3,2,3},{2,1,4},{3,4,5},{3,1,2}};intv[3][4]={{2,2,3,4},{4,1,2,4},{1,2,2,3}};intp[4][4]={{0,0,0,0},{0,0,0,0},{0,0,0,0},{0,0,0,0}};p[0][0]=0;for(intj=1;j4;j++)//y轴上的点p[0][j]=p[0][j-1]+h[0][j-1];for(inti=1;i4;i++)//x轴上的点p[i][0]=p[i-1][0]+v[i-1][0];for(inti=1;i4;i++)//内部的点for(intj=1;j4;j++)p[i][j]=min((p[i-1][j]+v[i-1][j]),(p[i][j-1]+h[i][j-1]));cout“fromPtoAis”p[3][3]endl;//输出每个路口对P点的最小距离for(inti=3;i=0;i--){ifor(intj=0;j=3;j++){coutp[i][j];}coutendl;}return0;0j}intmin(inta,intb){if(a=b)returna;elsereturnb;}动态规划的几个概念:阶段：据空间顺序或时间顺序对问题的求解划分阶段。状态：描述事物的性质，不同事物有不同的性质，因而用不同的状态来刻画。对问题的求解状态的描述是分阶段的。决策：根据题意要求，对每个阶段所做出的某种选择性操作。状态转移方程：用数学公式描述与阶段相关的状态间的演变规律。动态规划是运筹学的一个重要分支，是解决多阶段决策过程最优化的一种方法。所谓多阶段决策过程，是将所研究的过程划分为若干个相互联系的阶段，在求解时，对每一个阶段都要做出决策，前一个决策确定以后，常常会影响下一个阶段的决策。动态规划所依据的是“最优性原理”。“最优性原理”可陈述为：不论初始状态和第一步决策是什么，余下的决策相对于前一次决策所产生的新状态，构成一个最优决策序列。最优决策序列的子序列，一定是局部最优决策子序列。包含有非局部最优的决策子序列，一定不是最优决策序列。动态规划的指导思想是：在做每一步决策时，列出各种可能的局部解，之后依据某种判定条件，舍弃那些肯定不能得到最优解的局部解。这样，在每一步都经过筛选，以每一步都是最优的来保证全局是最优的。筛选相当于最大限度地有效剪枝（从搜索角度看），效率会十分高。但它又不同于贪心法。贪心法只能做到局部最优，不能保证全局最优，因为有些问题不符合最优性原理。两种算法的差别在于，贪心法产生一个按贪心策略形成的判定序列，该序列不保证解是全局最优的。而动态规划会产生许多判定序列，再按最优性原理对这些序列加以筛选，去除那些非局部最优的子序列。举例说明动态规划思路问题：在数字串中插入若干乘号使总的乘积最大***s32151250123456请插入3个乘号使乘积最大32*15*12*5=288003*215*12*5=38700321*51*2*5=163710解题思路定义:从l到r加入k个乘号的最大乘积值*p(l,r,k)ll+1l+2...qq+1q+2...rd(l,q)p(q+1,r,k-1)d(l,q)=s[l]s[l+1]…s[q]q的变化范围：从q+1到r之间所包含的数字个数应大于k-1（乘号个数）。r-(q+1)+1k-1qr-k+1p(l,r,k)=max{d(l,q)*p(q+1,r,k-1)}q=l,l+1,…,r-k*q=l=032151250123456d(l,q)=d(0,0)=3p(q+1,r,k-1)=p(1,6,2)(p(0,6,3)|q=0)=3*p(1,6,2)q=l+1=1*32151250123456d(l,q)=d(0,1)=32p(q+1,r,k-1)=p(2,6,2)(p(0,6,3)|q=1)=32*p(2,6,2)q=l+2=2*32151250123456d(l,q)=d(0,2)=321p(q+1,r,1)=p(3,6,2)(p(0,6,3)|q=2)=321*p(3,6,2)q=l+3=3*32151250123456d(l,q)=d(0,3)=3215p(q+1,r,k-1)=p(4,6,2)(p(0,6,3)|q=3)=3215*p(4,6,2)p(0,6,3)=max{3*p(1,6,2),//q=032*p(2,6,2),//q=1321*p(3,6,2),//q=23215*p(4,6,2)}//q=3p(1,6,2)2151252*p(2,6,1)12345621512521*p(3,6,1)123456215125215*p(4,6,1)1234562151252151*p(5,6,1)123456p(2,6,1)151251*5125234561512515*1252345615125151*2523456151251512*523456p(2,6,1)=max{1*5125,15*125,151*25,1512*5}=7560p(3,6,1)51255*1253456512551*2534565125512*53456p(3,6,1)=max{5*125,51*25,512*5}=2560p(4,6,1)1251*2545612512*5456p(4,6,1)=max{1*25,12*5}=60p(5,6,1)252*556p(5,6,1)=10p(2,6,2)151251*p(3,6,1)234561512515*p(4,6,1)2345615125151*p(5,6,1)23456p(2,6,2)={1*2560,15*60,151*10}=2560p(3,6,2)51255*p(4,6,1)3456512551*p(5,6,1)3456p(3,6,2)={5*60,51*10}=510p(4,6,2)1251*2*5456p(4,6,2)=10p(4,6,2)1251*p(5,6,1)456p(5,6,1)=2*5=10p(4,6,2)=1*p(5,6,1)=10p(0,6,3)=max{3*p(1,6,2),//q=032*p(2,6,2),//q=1321*p(3,6,2),//q=23215*p(4,6,2)}//q=3p(1,6,2)=53760p(2,6,2)=25