《动态规划DP》由会员分享，可在线阅读，更多相关《动态规划DP（91页珍藏版）》请在金锄头文库上搜索。
1、10 动态规划免费机票旅游加拿大西 东多种解法n单向搜索n双向搜索n动态规划图1DAGCKBNPOMJFHELI312345214323142212223344阶段1阶段2阶段3阶段4阶段5任务：P是出发点，从P到A，求最短路径（图1）思路n先看第5阶段，到达A点有两条路 B A，需要2km C A，需要3km B 2 A P(A) n令 P(B) 3 从P A的最短路径为P(A)； C 从P B的最短路径为P(B)； P(C) 从P C的最短路径为P(C) 5阶段 P(A) = minP(B)+2, P(C)+3； P(B) = minP(D)+1, P(E)+2； P(C) = minP(
2、E)+5, P(F)+4；P(A) = minP(B)+2, P(C)+3； P(B) = minP(D)+1, P(E)+2； P(C) = minP(E)+5, P(F)+4；P(D) D 1 B 2 A2 35 P(B) E C4 P(C)P(E) F P(F)P(N) = 2; P(O) = 3;上述递推公式告诉我们，要求上述递推公式告诉我们，要求P(A)P(A)需要先需要先 求出阶段求出阶段5 5中的中的P(B)P(B)和和P(C)P(C)；要求要求 P(B) (P(B) (或者或者 P(C)P(C)），），又要先求出阶段又要先求出阶段4 4中的中的 P(D) P(D) 和和 P(E
3、) P(E) ( (或或P(F)P(F)和和P(E)P(E) 显然，要依照上述递推过程求解，需要倒显然，要依照上述递推过程求解，需要倒 过来，从过来，从P(P)P(P)出发，先求出第一阶段的出发，先求出第一阶段的P(O)P(O) 和和P(N)P(N)，再求第二阶段的再求第二阶段的P(K)P(K)，P(L)P(L)，P(M)P(M) ；，最后得到最后得到P(A)P(A)。n选择数据结构，将每条路经的长度存在数 组中。 东西方向上的道路长度存在两维数组h43中 规定数组的第一维为行号，第二维为列号。312345214323h43 = 3,2,3, 2,1,4, 3,4,5, 3,1,2 ;0121
4、023南北方向上道路长度存至数组v34中，也规 定第一维为行号，第二维为列号。0123210223441241223v34 = 2, 2, 3, 4,4, 1, 2, 4,1, 2, 2, 3;n为了计算方便，将图1改为图2h30h31h32h20h21h22h10h11h12h00h01h02v20v21v22v23v10v11v12v13v00v01v02v03(3, 3)0213213yx图2 求解过程为从(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
5、)为P10；P(A)为P33，以下为分 阶段递推求解过程。对于阶段对于阶段1 1:P00 = 0;P01 = P00+h00 = 0+3 = 3;P10 = P00+v00 = 0+2 = 2;p30 p31 p32 p33 h30 h31 h32v20 v21 v22 v23p20 p21 p22 p23 h20 h21 h22 阶段 5v10 v11 v12 v13 p10 p11 p12 p13 h10 h11 h12 阶 段 4v00 v01 v02 v03p00 p01 p02 p03 h00 h01 h02 阶 段 3阶段 1 阶段 2对于阶段2 P11 = min P01+v01
6、, 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 P21 = min P11+v11, P20+h20= min4+1, 6+1 = 5 P30 = P20+v20 = 6+1 = 7对于阶段4 P13 = min P03+v03, P12+h12= min8+4, 5+4 = 9 P22 = min P12+v12, P21+h21= min5+2
7、, 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= min12+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
8、( i0, j=0) 下面给出P数组中的数据01232100358245965712778103数组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)n画出用动态规划思想求出的各个路口对P 点的最小距离。图中圆圈里就是这个距 离。箭头表示所寻得的最佳行走路径。 （图3）312345214323142212223344026734575578891210P点A点图3参考程序如下#include using namespace std;
9、int min(int,int); / 声明有子函数 min()int main() / 主函数 int h43= 3,2,3,2,1,4,3,4,5,3,1,2 ;/东西路段int v34= 2,2,3,4,4,1,2,4,1,2,2,3 ; /南北路段int p44= 0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0 ;p00=0; / 初始化for(int j=1;j=0;i-) ifor(int j=0;j=0; j- )for(int i=0; i / 预编译命令 #include / 预编译命令 using namespace std; / 使用名字空间 const int S=3215125; /定义常整数int d77; /定义二维数组 int P( int l, int r, int k ) /计算P函数值
