最短路径和背包问题.ppt

最短路径问题的应用,找出A到E的最短路径,（四个阶段五个状态）,三、举例,阶段划分,I,IV,III,II,S1,S2,S3,S4,S5,将A到E的最短路径问题，转化为三个性质完全相同，但规模较小的子问题,求解策略(逆推),记fk(vk)为节点vk到E的最短路,（逆推）,求解,f4(D1)=5，f4(D2)=2,f3(C1)=8；f3(C2)=7； f3(C3)=12,决策,f(3C1)=8；f3(C2)=7； f3(C3)=12,f2(B1)=20；f2(B2)=14；f2(B3)=19,最优解,A B2 C1 D1 E 距离为19,B,C,B,D,B,C,D,E,C,2,1,2,3,1,2,3,1,2,5,1,12,14,10,6,10,4,13,12,11,3,9,6,5,8,10,5,2,0,5,8,14,19,注意： 每一阶段的最优决策未必能保证总体最优， 总体最优也不能保证每一阶段最优。,用逆推法求解最短路的计算公式概括为,解法2：表格法,动态规划递推关系,sK,xK,k=4,s3,x3,k=3,s2,x2,k=2,f(3C1)=8；f3(C2)=7； f3(C3)=12,s1,x1,K=1,f2(B1)=20；f2(B2)=14；f2(B3)=19,练习1、从A 地到D 地要铺设一条煤气管道,其中需经过两级中间站，两点之间的连线上的数字表示距离，如图所示。问应该选择什么路线，使总距离最短？,A,B1,B2,C1,C2,C3,D,2,4,3,3,3,3,2,1,1,1,4,解：整个计算过程分三个阶段，从最后一个阶段开始。,第一阶段（C D）： C 有三条路线到终点D 。,A,B1,B2,C1,C2,C3,D,2,4,3,3,3,3,2,1,1,1,4,D,C1,C2,C3,显然有 f3(C1 ) = 1 ； f3(C2 ) = 3 ； f3 (C3 ) = 4,A,B,C,D,阶段1,阶段2,阶段3,f2,f3,f1,第二阶段（B C）： B 到C 有六条路线。,A,B1,B2,C1,C2,C3,D,2,4,3,3,3,3,2,1,1,1,4,D,C1,C2,C3,B1,B2,d( B2,C1 ) + f3 (C1 ) 2+1 f2 ( B2 ) = min d( B2,C2 ) + f3 (C2 ) = min 3+3 d( B2,C3 ) + f3 (C3 ) 1+4 3 = min 6 = 3 5,A,B1,B2,C1,C2,C3,D,2,4,3,3,3,3,2,1,1,1,4,D,C1,C2,C3,B1,B2,(最短路线为B2C1 D),第三阶段（ A B ）： A 到B 有二条路线。,f1(A)1 = d(A, B1 ) f2 ( B1 ) 246 f1 (A)2 = d(A, B2 ) f2 ( B2 ) 437, f1 (A) = min = min6,7=6,d(A, B1 ) f2 ( B1 ) d(A, B2 ) f2 ( B2 ),(最短路线为AB1C1 D),A,B1,B2,C1,C2,C3,D,2,4,3,3,3,3,2,1,1,1,4,D,C1,C2,C3,B1,B2,A,A,B1,B2,C1,C2,C3,D,2,4,3,3,3,3,2,1,1,1,4,D,C1,C2,C3,B1,B2,A,最短路线为 AB1C1 D 路长为 6,A,B1,B2,C1,C2,D,2,4,3,3,3,3,2,1,1,1,4,顺推法,C3,A,B,C,D,阶段1,阶段2,阶段3,f2,f3,f1,A,B1,B2,C1,C2,D,2,4,3,3,3,3,2,1,1,1,4,C3,第一阶段：,f1(B1 ）= 2， f1 (B2 ）= 4,第二阶段：,第三阶段：,A,B1,B2,C1,C2,D,2,4,3,3,3,3,2,1,1,1,4,C3,练习2：,A,B1,B2,C1,C2,C3,C4,D1,D2,D3,E1,E2,E3,F1,F2,G,5,3,1,3,6,8,7,6,3,6,8,5,3,3,8,4,2,2,2,1,3,3,3,5,2,5,6,6,4,最优路线为：A B1 C2 D1 E2 F2 G 路长18,求从A到G的最短路径,3,k=5，出发点E1、E2、E3,A,B1,B2,C1,C2,C3,C4,D1,D2,D3,E1,E2,E3,F1,F2,G,5,3,1,3,6,8,7,6,6,8,3,5,3,3,8,4,2,2,1,2,3,3,3,5,5,2,6,6,4,3,7 5 9,x5(E2)=F2,x6(F2)=G,最优策略,A,B1,B2,C1,C2,C3,C4,D1,D2,D3,E1,E2,E3,F1,F2,G,5,3,1,3,6,8,7,6,3,6,8,5,3,3,8,4,2,2,2,1,3,3,3,5,2,5,6,6,4,3,有一个徒步旅行者，其可携带物品重量的限度为a 公斤，设有n 种物品可供他选择装入包中。已知每种物品的重量及使用价值（作用），问此人应如何选择携带的物品（各几件），使所起作用（使用价值）最大？,背包问题,解：设 xj 为第 j 种物品的装件数（非负整数）则问题的数学模型如下：,用动态规划方法求解： （1）阶段k：每段装一种物品，共划分n个阶段，即k=1,2,n。 （2）状态变量sk+1：表k 阶段开始时，背包中允许装入前k 种 物品的总重量。 （3）决策变量xk:装入第k种物品的件数。 （4）状态转移方程： （5）允许决策的集合：,(6) 阶段指标：ckxk (7) 最优指标函数：fk(sk+1) 表总重量不超过 sk+1 公 斤（即背包中允许装入前k 种物品的总重量），包 中只装有前k 种物品时的最大使用价值。有 所以问题就是求 fn(a) ，（a是可携带物品重量的限度）,（8）递推关系式为：,总重量不超过 sk 公斤，包中只装有前k-1 种物品时的最大使用价值。,例3：求下面背包问题的最优解,解：a5 ，问题是求 f3(5),问题转化为求,所以，最优解为 X（1 . 1