ACM培训03-动态规划.ppt

10动态规划图1思路P(N)=2;P(O)=3;选择数据结构将每条路经的长度存在数组中。东西方向上的道路长度存在两维数组h[4][3]中规定数组的第一维为行号第二维为列号。南北方向上道路长度存至数组v[3][4]中也规定第一维为行号第二维为列号。为了计算方便将图1改为图2求解过程为从(00)到(33)求最短路径问题定义二维数组P[4][4]={{0000}{0000}{0000}{0000}}第一维为行第二维为列。这时P(O)为P[0][1]；P(N)为P[1][0]；…P(A)为P[3][3]以下为分阶段递推求解过程。对于阶段2P[1][1]=min{P[0][1]+v[0][1]P[1][0]+h[1][0]}=min{3+12+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+34+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+16+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+45+4}=9P[2][2]=min{P[1][2]+v[1][2]P[2][1]+h[2][1]}=min{5+25+4}=7P[3][1]=min{P[2][1]+v[2][1]P[3][0]+h[3][0]}=min{5+27+3}=7对于阶段5P[2][3]=min{P[1][3]+v[1][3]P[2][2]+h[2][2]}=min{9+47+5}=12P[3][2]=min{P[2][2]+v[2][2]P[3][1]+h[3][1]}=min{7+27+1}=8最后P[3][3]=min{P[2][3]+v[2][3]P[3][2]+h[3][2]}=min{12+38+2}=10综上数组P的通项表示为P[i][j]=min((p[i-1][j]+v[i-1][j])(p[i][j-1]+h[i][j-1]))(ij>0)P[0][j]=P[0][j-1]+h[0][j-1](i=0j>0)P[i][0]=P[i-1][0]+v[i-1][0](i>0j=0)下面给出P数组中的数据画出用动态规划思想求出的各个路口对P点的最小距离。图中圆圈里就是这个距离。箭头表示所寻得的最佳行走路径。（图3）参考程序如下#include<iostream.h>intmin(intint);intmain()//主函数{inth[4][3]={{323}{214}{345}{312}};intv[3][4]={{2234}{4124}{1223}};intp[4][4]={{0000}{0000}{0000}{0000}};p[0][0]=0;for(intj=1;j<4;j++)//y轴上的点p[0][j]=p[0][j-1]+h[0][j-1];for(inti=1;i<4;i++)//x轴上的点p[i][0]=p[i-1][0]+v[i-1][0];for(inti=1;i<4;i++)//内部的点for(intj=1;j<4;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++){cout<<p[i][j]<<"";}