资源描述：
《最短路径和背包问题.ppt》由会员上传分享，免费在线阅读，更多相关内容在教育资源-天天文库。
1、最短路径问题的应用找出A到E的最短路径（四个阶段五个状态）三、举例阶段划分IIVIIIIIS1S2S3S4S5将A到E的最短路径问题，转化为三个性质完全相同，但规模较小的子问题求解策略(逆推)记fk(vk)为节点vk到E的最短路（逆推）求解f4(D1)=5，f4(D2)=2f3(C1)=8；f3(C2)=7；f3(C3)=12决策f(3C1)=8；f3(C2)=7；f3(C3)=12f2(B1)=20；f2(B2)=14；f2(B3)=19最优解AB2C1D1E距离为19BACBDBCDEC2123
2、123125112141061041312113965810520581419注意：每一阶段的最优决策未必能保证总体最优，总体最优也不能保证每一阶段最优。用逆推法求解最短路的计算公式概括为解法2：表格法动态规划递推关系sKxKs4D1D252EEk=4D1D2C1C2C33+59+28D16+55+27D28+510+212D2s3x3k=3C1C2C3B1B2B312+814+710+1220C16+810+74+1214C113+812+711+1219C2s2x2k=2f(3C1)=8；f3(
3、C2)=7；f3(C3)=12B1B2B3A2+205+141+1919B2s1x1K=1f2(B1)=20；f2(B2)=14；f2(B3)=19练习1、从A地到D地要铺设一条煤气管道,其中需经过两级中间站，两点之间的连线上的数字表示距离，如图所示。问应该选择什么路线，使总距离最短？AB1B2C1C2C3D24333321114解：整个计算过程分三个阶段，从最后一个阶段开始。第一阶段（C→D）：C有三条路线到终点D。AB1B2C1C2C3D24333321114DC1C2C3显然有f3(C1)=1
4、；f3(C2)=3；f3(C3)=4ABCD阶段1阶段2阶段3f2f3f1第二阶段（B→C）：B到C有六条路线。AB1B2C1C2C3D24333321114DC1C2C3B1B2d(B1,C1)+f3(C1)3+1f2(B1)=mind(B1,C2)+f3(C2)=min3+3d(B1,C3)+f3(C3)1+44=min6=45(最短路线为B1→C1→D)d(B2,C1)+f3(C1)2+1f2(B2)=mind(B2,C2)+f3(C2)=min3+3d(B2,C3)+f3(C3)1+43=m
5、in6=35AB1B2C1C2C3D24333321114DC1C2C3B1B2(最短路线为B2→C1→D)第三阶段（A→B）：A到B有二条路线。f1(A)1=d(A,B1)＋f2(B1)＝2＋4＝6f1(A)2=d(A,B2)＋f2(B2)＝4＋3＝7∴f1(A)=min=min｛6,7｝=6d(A,B1)＋f2(B1)d(A,B2)＋f2(B2)(最短路线为A→B1→C1→D)AB1B2C1C2C3D24333321114DC1C2C3B1B2AAB1B2C1C2C3D24333321114DC
6、1C2C3B1B2A最短路线为A→B1→C1→D路长为6AB1B2C1C2D24333321114顺推法C3ABCD阶段1阶段2阶段3f2f3f1AB1B2C1C2D24333321114C3第一阶段：f1(B1）=2，f1(B2）=4第二阶段：第三阶段：AB1B2C1C2D24333321114C3练习2：AB1B2C1C2C3C4D1D2D3E1E2E3F1F2G53136876368533842221333525664最优路线为：A→B1→C2→D1→E2→F2→G路长＝18求从A到G的最短路
7、径3k=5，出发点E1、E2、E3x5(E1)=F1E1F1GAB1B2C1C2C3C4D1D2D3E1E2E3F1F2G531368766835338422123335526643x5(E2)=F2E2F2Gx5(E3)=F2E3F2Gk=6,F1G,f6(F1)=4F2G,f6(F2)=3k=4，f4(D1)=7x4(D1)=E2f4(D2)=6x4(D2)=E2f4(D3)=8x4(D3)=E2k=2,f2(B1)=13x2(B1)=C2f2(B2)=16x2(B2)=C3f3(C1)=13x
8、3(C1)=D1f3(C2)=10x3(C2)=D1f3(C3)=9x3(C3)=D1f3(C4)=12x3(C4)=D3k=3,=minf1(A)=mind1(A,B1)+f2(B1)d1(A,B2)+f2(B2)5+133+16=18k=1,x1(A)=B1x2(B1)=C2x3(C2)=D1x4(D1)=E2x1(A)=B1x2(B1)=C2x3(C2)=D1x4(D1)=E2x5(E1)=F1E1F1Gx5(E2)=F2E2F2Gx5(E3)=F2E3F2G7
