许香敏最优化方法PPT

1、1第十讲第十讲 动态规划动态规划(dynamic programming) 动态规划的基本概念和思想动态规划的基本概念和思想 最短路径问题最短路径问题 投资分配问题投资分配问题 背包问题背包问题 排序问题排序问题2动态规划是运筹学的一个分支，是求解多阶段决策过动态规划是运筹学的一个分支，是求解多阶段决策过程最优化问题的数学方法。程最优化问题的数学方法。动态规划在经济管理、工程技术、工农业生产及军事动态规划在经济管理、工程技术、工农业生产及军事部门中都有着广泛的应用，并且获得了显著的效果。部门中都有着广泛的应用，并且获得了显著的效果。学习动态规划，我们首先要了解多阶段决策问题。学习动态规划，我们

2、首先要了解多阶段决策问题。3最短路径问题最短路径问题：给定一个交通网络图如下，其中两点之间：给定一个交通网络图如下，其中两点之间的数字表示距离（或运费），试求从的数字表示距离（或运费），试求从a a点到点到g g点的最短距离点的最短距离（总运输费用最小）。（总运输费用最小）。123456ab1b2c1c2c3c4d1d2d3e1e2e3f1f2g5313687636853384222133352566434背包问题背包问题 有一个徒步旅行者，其可携带物品重量的限度有一个徒步旅行者，其可携带物品重量的限度为为a a 公斤，设有公斤，设有n n 种物品可供他选择装入包中。已知每种种物品可供他选择装

3、入包中。已知每种物品的重量及使用价值（作用），问此人应如何选择携带物品的重量及使用价值（作用），问此人应如何选择携带的物品（各几件），使所起作用（使用价值）最大？的物品（各几件），使所起作用（使用价值）最大？物品物品 1 2 j n重量（重量（公斤公斤/ /件件） a1 a2 aj an每件使用价值每件使用价值 c1 c2 cj cn 类似的还有工厂里的下料问题、运输中的货物装载问题、人造卫星内的物品装载问题等。5 生产决策问题生产决策问题：企业在生产过程中，由于需求是随时间变：企业在生产过程中，由于需求是随时间变化的，因此企业为了获得全年的最佳生产效益，就要在整个化的，因此企业为了获得全年的

4、最佳生产效益，就要在整个生产过程中逐月或逐季度地生产过程中逐月或逐季度地根据库存和需求决定生产计划。根据库存和需求决定生产计划。机器负荷分配问题机器负荷分配问题：某种机器可以在高低两种不同的负荷：某种机器可以在高低两种不同的负荷下进行生产。要求制定一个五年计划，在下进行生产。要求制定一个五年计划，在每年开始时，决每年开始时，决定如何重新分配定如何重新分配完好的完好的机器在两种不同的负荷下生产的数机器在两种不同的负荷下生产的数量量，使在五年内产品的总产量达到最高。，使在五年内产品的总产量达到最高。航天飞机飞行控制问题航天飞机飞行控制问题：由于航天飞机的运动的环境是不：由于航天飞机的运动的环境是不

5、断变化的，因此就要根据航天飞机飞行在不同环境中的情断变化的，因此就要根据航天飞机飞行在不同环境中的情况，不断地决定航天飞机的飞行方向和速度（状态），使况，不断地决定航天飞机的飞行方向和速度（状态），使之能最省燃料和之能最省燃料和完成飞行任务完成飞行任务（如软着（如软着陆陆）。）。6根据过程的特性可以将过程按空间、时间等标志分为根据过程的特性可以将过程按空间、时间等标志分为若干个互相联系又互相区别的阶段。若干个互相联系又互相区别的阶段。在每一个阶段都需要做出决策，从而使整个过程达到在每一个阶段都需要做出决策，从而使整个过程达到最好的效果。最好的效果。各个阶段决策的选取不是任意确定的，它依赖于当前

6、各个阶段决策的选取不是任意确定的，它依赖于当前面临的状态，又影响以后的发展。面临的状态，又影响以后的发展。当各个阶段的决策确定后，就组成了一个决策序列，当各个阶段的决策确定后，就组成了一个决策序列，因而也就决定了整个过程的一条活动路线，这样的一因而也就决定了整个过程的一条活动路线，这样的一个前后关联具有链状结构的多阶段过程就称为多阶段个前后关联具有链状结构的多阶段过程就称为多阶段决策问题。决策问题。多阶段决策过程的特点：多阶段决策过程的特点：7针对多阶段决策过程的最优化问题，美国数学家针对多阶段决策过程的最优化问题，美国数学家bellmanbellman等等人在人在2020世纪世纪5050年代

7、初提出了著名的最优化原理，年代初提出了著名的最优化原理，把多阶段把多阶段决策问题转化为一系列单阶段最优化问题决策问题转化为一系列单阶段最优化问题，从而逐个求解，从而逐个求解，创立了解决这类过程优化问题的新方法：动态规划。创立了解决这类过程优化问题的新方法：动态规划。对最佳路径（最佳决策过程）所经过的各个阶段，其中每个阶段始点到全过程终点的路径，必定是该阶段始点到全过程终点的一切可能路径中的最佳路径（最优决策），这就是bellman提出的著名的最优化原理。简言之， 一个最优策略的子策略必然也是最优的。bellman在在1957年出版的年出版的dynamic programming是动是动态规划领

8、域的第一本著作。态规划领域的第一本著作。8例1、从从a a 地到地到e e 地要铺设一条煤气管道地要铺设一条煤气管道, ,其中需经过三级其中需经过三级中间站，两点之间的连线上的数字表示距离，如图所示。中间站，两点之间的连线上的数字表示距离，如图所示。问应该选择什么路线，使总距离最短？问应该选择什么路线，使总距离最短？ 二. 最短路径问题ab2b1b3c1c3d1d2e52141126101043121113965810521c29 解：解：整个计算过程分四个整个计算过程分四个阶段阶段，从最后一个阶段开始。，从最后一个阶段开始。 第四阶段（第四阶段（d e）： d 有两条路线到终点有两条路线到终

9、点e 。 显然有显然有ab2b1b3c1c3d1d2e52141126101043121113965810521c22)(; 5)(2414 dfdf10首先考虑经过首先考虑经过 的两条路线的两条路线第三阶段（第三阶段（c d）： c 到到d 有有 6 条路线。条路线。(最短路线为最短路线为 )ab2b1b3c1c3d1d2e5214126101043121113965810521c282953min)(),()(),(min)(2421141113 dfdcddfdcdcfedc111c11ab2b1b3c1c3d1d2e5214126101043121113965810521c272556

10、min)(),()(),(min)(2422141223 dfdcddfdcdcf(最短路线为最短路线为 )edc22考虑经过考虑经过 的两条路线的两条路线2c12ab2b1b3c1c3d1d2e5214126101043121113965810521c21221058min)(),()(),(min)(2423141333 dfdcddfdcdcf(最短路线为最短路线为 )edc23考虑经过考虑经过 的两条路线的两条路线3c13ab2b1b3c1c3d1d2e5214126101043121113965810521c2201210714812min)(),()(),()(),(min)(33

11、312321131112 cfcbdcfcbdcfcbdbf(最短路线为最短路线为 )edcb111第二阶段（第二阶段（b c）： b 到到c 有有 9 条路线。条路线。首先考虑经过首先考虑经过 的的3条路线条路线1b14ab2b1b3c1c3d1d2e5214126101043121113965810521c21412471086min)(),()(),()(),(min)(34322422141222 cfcbdcfcbdcfcbdbf(最短路线为最短路线为 )edcb112考虑经过考虑经过 的的3条路线条路线2b15ab2b1b3c1c3d1d2e52141261010431211139

12、65810521c2191211712813min)(),()(),()(),(min)(33332323131332 cfcbdcfcbdcfcbdbf(最短路线为最短路线为 )edcb223考虑经过考虑经过 的的3条路线条路线3b16ab2b1b3c1c3d1d2e5214126101043121113965810521c219191145202min)(),()(),()(),(min)(3232221211 bfbadbfbadbfbadaf(最短路线为最短路线为 )edcba112第一阶段（第一阶段（a b）： a 到到b 有有 3 条路线。条路线。 （最短距离为（最短距离为19）1

13、7 动态规划是用来解决多阶段决策过程最优化的一种数量动态规划是用来解决多阶段决策过程最优化的一种数量方法。其特点在于，方法。其特点在于，它可以把一个它可以把一个n 维决策问题变换为几个维决策问题变换为几个一维最优化问题一维最优化问题，从而一个一个地去解决。，从而一个一个地去解决。 需指出：需指出：动态规划是求解某类问题的一种方法，是考察动态规划是求解某类问题的一种方法，是考察问题的一种途径，而不是一种算法问题的一种途径，而不是一种算法。必须对具体问题进行具。必须对具体问题进行具体分析，运用动态规划的原理和方法，建立相应的模型，然体分析，运用动态规划的原理和方法，建立相应的模型，然后再用动态规划

14、方法去求解。后再用动态规划方法去求解。即在系统发展的不同时刻（或阶段）根据系统所处的状即在系统发展的不同时刻（或阶段）根据系统所处的状态，态，不断地做出决策不断地做出决策；动态决策问题的特点：动态决策问题的特点：系统所处的系统所处的状态和时刻状态和时刻是进行决策的重要因素；是进行决策的重要因素；找到找到不同时刻不同时刻的最优决策以及的最优决策以及整个过程的最优策略整个过程的最优策略。18 动态规划方法的关键：在于正确地写出动态规划方法的关键：在于正确地写出基本的递推关基本的递推关系式系式和和恰当的边界条件恰当的边界条件（简称（简称基本方程基本方程）。）。 要做到这一点，就必须将问题的过程分成几

15、个相互联要做到这一点，就必须将问题的过程分成几个相互联系的系的阶段阶段，恰当的选取，恰当的选取状态变量状态变量和和决策变量决策变量及定义及定义最优值最优值函数函数，从而把一个大问题转化成一组同类型的子问题，然，从而把一个大问题转化成一组同类型的子问题，然后逐个求解。后逐个求解。 即从边界条件开始，逐段递推寻优，在每一个子问题即从边界条件开始，逐段递推寻优，在每一个子问题的求解中，均利用了它前面的子问题的最优化结果，依次的求解中，均利用了它前面的子问题的最优化结果，依次进行，最后一个子问题所得的最优解，就是整个问题的最进行，最后一个子问题所得的最优解，就是整个问题的最优解。优解。19 2、在多阶

16、段决策过程中，动态规划方法是既把当前一、在多阶段决策过程中，动态规划方法是既把当前一段和未来一段段和未来一段分开分开，又把当前效益和未来效益，又把当前效益和未来效益结合结合起来考起来考虑的一种最优化方法。因此，每段决策的选取是从全局来虑的一种最优化方法。因此，每段决策的选取是从全局来考虑的，与该段的最优选择答案一般是不同的考虑的，与该段的最优选择答案一般是不同的. 最优化原理：作为整个过程的最优策略具有这样的性质：无论过去的状态和决策如何，相对于前面的决策所形成的状态而言，余下的决策序列必然构成最优子策略。也就是说，一个最优策略的子策略也是最优的。 3、在求整个问题的最优策略时，由于初始状态是

17、已知的，而每段的决策都是该段状态的函数，故最优策略所经过的各段状态便可逐段变换得到，从而确定了最优路线。20动态规划求解动态规划求解的的多阶段问题的特点：多阶段问题的特点： 每个阶段的最优决策过程只与本阶段的初始状态有关，每个阶段的最优决策过程只与本阶段的初始状态有关，而与以前各阶段的决策（即为了到达本阶段的初始状而与以前各阶段的决策（即为了到达本阶段的初始状态而采用哪组决策路线无关）。换言之，本阶段之前态而采用哪组决策路线无关）。换言之，本阶段之前的状态与决策，只是通过系统在本阶段所处的初始状的状态与决策，只是通过系统在本阶段所处的初始状态来影响本阶段及以后各个阶段的决策。或者说，系态来影响

18、本阶段及以后各个阶段的决策。或者说，系统过程的历史只能通过系统现阶段的状态去影响系统统过程的历史只能通过系统现阶段的状态去影响系统的未来。的未来。 具有这种性质的状态称为无后效性（即马尔科夫性）具有这种性质的状态称为无后效性（即马尔科夫性）状态。状态。 动态规划方法只适用于求解具有无后效性状态的多阶动态规划方法只适用于求解具有无后效性状态的多阶段决策问题。段决策问题。21 现有数量为a（万元）的资金，计划分配给n 个工厂,用于扩大再生产。 假设：xi 为分配给第i 个工厂的资金数量（万元）；gi(xi)为第i 个工厂得到资金后提供的利润值（万元）。 问题：如何确定各工厂的资金数，使得总的利润为

19、最大。 nixaxxgziniiniii.2.1 0)( max11据此，有下式：三. 投资分配问题22 令：令：fk(x) 表示表示 以数量为以数量为 x 的资金分配给的资金分配给前前k 个个工厂，所工厂，所得到的最大利润值。得到的最大利润值。 用动态规划求解，就是用动态规划求解，就是求求 fn(a) 的问题的问题。 当当 k=1 时，时， f1(x) = g1(x) （因为只给一个工厂）（因为只给一个工厂） 当当1kn 时，其递推关系如下：时，其递推关系如下： 设：设：y 为分给第为分给第k 个工厂的资金（其中个工厂的资金（其中 0y x ），此时还），此时还剩剩 x y（万元）的资金需要

20、分配给前（万元）的资金需要分配给前 k1 个工厂个工厂,如果采如果采取最优策略，则得到的最大利润为取最优策略，则得到的最大利润为fk1(xy) ,因此总的利润因此总的利润为：为： gk(y) fk1(xy) 23 nkyxfygxfkkxyk.)()(max)(3210 其中 如果如果a 是以万元为资金分配单位，则式中的是以万元为资金分配单位，则式中的y 只取非负整只取非负整数数0，1，2，x。上式可变为：。上式可变为： )()(max)(,yxfygxfkkxyk 1210所以，根据动态规划的最优化原理，有下式：所以，根据动态规划的最优化原理，有下式：24 例2：设国家拨给60万元投资，供四

21、个工厂扩建使用，每个工厂扩建后的利润与投资额的大小有关，投资后的利润函数如下表所示。 投资利润0102030405060g1(x)0205065808585g2(x)0204050556065g3(x)0256085100110115g4(x)0254050606570解：依据题意，是要求 f4(60) 。25按顺序解法计算。按顺序解法计算。第一阶段：求第一阶段：求 f1(x)。显然有。显然有 f1(x) g1(x)，得到下表，得到下表 投资投资利润利润0102030405060f1(x) g1(x)0205065808585最优策略最优策略0102030405060第二阶段：求第二阶段：求

22、f2(x)。此时需考虑第一、第二个工厂如何进行。此时需考虑第一、第二个工厂如何进行投资分配，以取得最大的总利润。投资分配，以取得最大的总利润。 )60()(max)60(1260,10,02yfygfy 2612006520605055655080408520850max)0()60()10()50()20()40()30()30()40()20()50()10()60()0(max12121212121212fgfgfgfgfgfgfg最优策略为（最优策略为（40，20），此时最大利润为），此时最大利润为120万元。万元。同理可求得其它同理可求得其它 f2(x) 的值。的值。 )60()(m

23、ax)60(1260,10,02yfygfy 27 105)0()50()10()40()20()30()30()20()40()10()50()0( )50()(max)50(1212121212121250,10,02 fgfgfgfgfgfgyfygfy最优策略为（最优策略为（3030，2020），此时最大利润为），此时最大利润为105105万元。万元。28 90 )40()(max)40(1240,10,02 yfygfy最优策略为（最优策略为（20，20），此时最大利润为），此时最大利润为90万元。万元。 70 )30()(max)30(1230,20,10,02 yfygfy最优策

24、略为（最优策略为（20，10），此时最大利润为），此时最大利润为70万元。万元。29 50 )20()(max)20(1220,10,02 yfygfy 20 )10()(max)10(12,10,02 yfygfy最优策略为（最优策略为（10，0）或（）或（ 0 ， 10 ） ，此时最大利润为，此时最大利润为20万元。万元。 f2(0) 0。最优策略为（最优策略为（0，0），最大利润为），最大利润为0万元。万元。 得到下表得到下表最优策略为（最优策略为（20，0），此时最大利润为），此时最大利润为50万元。万元。30 投资投资利润利润0102030405060f2(x)02050709010

25、5120最优策略最优策略(0,0)(10,0)(0,10)(20,0) (20,10) (20,20) (30,20) (40,20)第三阶段：求第三阶段：求 f3(x)。此时需考虑第一、第二及第三个工。此时需考虑第一、第二及第三个工厂如何进行投资分配，以取得最大的总利润。厂如何进行投资分配，以取得最大的总利润。 )60()(max)60(2360,10,03yfygfy 311550115201105010070859060105251200max)0()60()10()50()20()40()30()30()40()20()50()10()60()0(max23232323232323 f

26、gfgfgfgfgfgfg最优策略为（最优策略为（20，10，30），最大利润为），最大利润为155万元。万元。同理可求得其它同理可求得其它 f3(x) 的值。得到下表的值。得到下表32 投资投资利润利润0102030405060f3(x)0256085110135155最优最优策略策略(0,0,0) (0,0,10) (0,0,20) (0,0,30) (20,0,20) (20,0,30) (20,10,30)第四阶段：求 f4(60)。即问题的最优策略。)60()(max)60(3460,10,04yfygfy3316007025656060855011040135251550max)0

27、()60()10()50()20()40()30()30()40()20()50()10()60()0(max34343434343434fgfgfgfgfgfgfg最优策略为（20，0，30，10），最大利润为160万元。34 有一个徒步旅行者，其可携带物品重量的限度为a 公斤，设有n 种物品可供他选择装入包中。已知每种物品的重量及使用价值（作用），问此人应如何选择携带的物品（各几件），使所起作用（使用价值）最大？物品物品 1 2 j n重量（重量（公斤公斤/ /件件） a1 a2 aj an每件使用价值每件使用价值 c1 c2 cj cn 这就是背包问题。类似的还有工厂里的下料问题、运输中

28、的货物装载问题、人造卫星内的物品装载问题等。四、背包问题35设 xj 为第 j 种物品的装件数（非负整数）则问题的数学模型如下： ).(maxnjxaxaxczjnijjjnjjj21 01且为整数用动态规划方法求解，令 fk(y) = 总重量不超过 y 公斤，包中只装有前k 种物品时的最大使用价值。 其中y 0， k 1,2, , n 。所以问题就是求 fn(a) 36其递推关系式为： nkxayfxcyfkkkkkayxkkk 2 10其中)(max)(当 k=1 时，有：的最大整数表示不超过其中1111111 ayayayxaycyf ,)(37例3：求下面背包问题的最优解 且且为为整整

29、数数0,55231258max321321321xxxxxxxxxz物品物品( (xi ) x1 x2 x3重量（重量（ai） 3 2 5使用价值使用价值 8 5 12解：a5 ，问题是求 f3(5) )55(12max)5(323503333xfxfxax 整整数数38 )( max)( 32350355125333xfxfxax 整数 )( max 323550551233xfxxx 整数 )( max 3231055123xfxx ， )( )()( ),(max 10223301250 xxff物品物品( (xi ) x1 x2 x3重量（重量（ai） 3 2 5使用价值使用价值 8

30、5 1239 5 5 )( 2)1()0(1112122, 10212250212502222222222)1(10),3(5),5(0max)25(max)25(max)25(5max)5(xxxxxxxaxfffxfxxfxxfxf，整数整数整数整数物品物品( (xi ) x1 x2 x3重量（重量（ai） 3 2 5使用价值使用价值 8 5 12 )()()()(max)(1022333012505x xf, ff40 )0( )0(0max )20(5 max )20(5 max )20(5 max)0(1 )0( 12120212 200212 0022222222ffxfxxfxx

31、fxfxxxxxax 整数整数整数整数物品物品( (xi ) x1 x2 x3重量（重量（ai） 3 2 5使用价值使用价值 8 5 12 )1()0(22333)0(12)5(0max)5(x xf, ff41)0(0308)0()0(0318)1()1(8338)3()1(8358)5(1111111111111111 xxcfxxcfxxcfxxcf ) 1, 1(1310, 85, 8max) 1 (10),3(5),5(0max)5(212)1()0(1112222 xxffffxxx )( 42 )0, 0(0)0()0(0max)0(211)0(122 xxfffx )0,1,1

32、(13012,130max)0(12),5(0max)5(321)1()0(22333 xxxfffxx所以，最优解为所以，最优解为 x（1 . 1 . 0），），最优值为最优值为 z = 13。总结：总结：解动态规划的一般方法解动态规划的一般方法:从终点逐段向始点方向寻找从终点逐段向始点方向寻找最小最小(大大)的方法。的方法。43 排序问题指n 种零件经过不同设备加工是的顺序问题。其目的是使加工周期为最短。 1、n 1 排序问题 即n 种零件经过1 种设备进行加工，如何安排？14682023交货日期（交货日期（d）45173加工时间（加工时间（t）零件代号零件代号2j1j3j4j5j例5.1

33、 五、排序问题44 （1）平均通过设备的时间最小 按零件加工时间非负次序排列顺序，其时间最小。（即将加工时间由小到大排列即可）1j2j3j4j5j零件加工顺序零件加工顺序 工序时间工序时间13457 实际通过时间实际通过时间1481320 交货时间交货时间82314620 平均通过时间2 . 9)1481320(51 x延迟时间 = 13 6 = 745 （2）按时交货排列顺序1j2j3j4j5j零件加工顺序零件加工顺序 工序时间工序时间13457 实际通过时间实际通过时间56101720 交货时间交货时间82314620 平均通过时间6 .11)56101720(51 x延迟时间 = 046

34、 （3）既满足交货时间，又使平均通过时间最小1j2j3j4j5j零件加工顺序零件加工顺序 工序时间工序时间13457 实际通过时间实际通过时间1691320 交货时间交货时间82314620延迟时间 = 0 平均通过时间8 .9)1691320(51 x47 2、n 2 排序问题排序问题 即即n 种零件经过种零件经过2 种设备进行加工，如何安排？种设备进行加工，如何安排？例5.249523b53786a 零件零件2j1j3j4j5j设备设备abt48经变换为49523b53786a 零件零件2j1j3j4j5j设备设备加工顺序图如下：加工顺序图如下：abt3j1j2j4j5j375689543

35、2+2+2-5 加工周期加工周期 t = 3+7+5+6+8+2 = 31小小即即batti 49 3、n 3 排序问题排序问题 即即n 种零件经过种零件经过 3 种设备进行加工，如何安排？种设备进行加工，如何安排？例5.33468564683579310cba1j2j3j4j5jabct50abct变换4+36+45+86+56+48+65+37+53+910+3b + ca+b1j2j3j4j5j51排序4+36+45+86+56+48+65+37+53+910+3b + ca+b1j2j3j4j5j复原3468564683579310cba1j2j3j4j5j52计算t = 6+10+8

36、+7+6+4+3 = 44计算依据：abccbabcbattttttttttiiiiii 或即可按下式计算或maxminmaxmin53练习练习1：ab1b2c1c2c3c4d1d2d3e1e2e3f1f2g53136876368533842221333525664最优路线为：最优路线为：a b1 c2 d1 e2 f2 g 路长路长18求从求从a到到g的最短路径的最短路径354 53245min,min262251612525 fffedfffedefk=5k=5，出发点，出发点e1e1、e2e2、e3e3 73543min,min2621161155 fffedfffedu5(e1)= f

37、1e1 f1 gab1b2c1c2c3c4d1d2d3e1e2e3f1f2g531368766835338422123335526643)(15efu5(e2)= f2e2 f2 g 93646min,min262351613535 fffedfffedefu5(e3)= f2e3 f2 gk=6k=6,f1 g, f f6 6(f1)=4(f1)=4f f2 2 g,f,f6 6(f2)=3(f2)=355k=4，f4(d1)=7 u4(d1)=e2f4(d2)=6 u4(d2)=e2f4(d3)=8 u4(d3)=e2k=2, f2(b1)=13 u2(b1)=c2 f2(b2)=16 u

38、2(b2)=c3f3(c1)=13 u3(c1)=d1f3(c2)=10 u3(c2)=d1f3(c3)=9 u3(c3)=d1f3(c4)=12 u3(c4)=d3k=3,= minf1(a)= mind1(a,b1)+ f2(b1) d1(a,b2)+ f2(b2)5+133+16=18k=1,u1(a)=b1u2(b1)=c2u3(c2)=d1u4(d1)=e256u1(a)=b1u2(b1)=c2u3(c2)=d1u4(d1)=e2u5(e1)=f1e1 f1 gu5(e2)=f2e2 f2 gu5(e3)=f2e3 f2 g7 5 9 u5(e2)=f2u6(f2)=g最优策略最优策略ab1b2c1c2c3c4d1d2d3e1e2e3f1f2g53136876368533842221333525664357求从求从a到到e的最短路径的最短路径路线为路线为ab2c1 d1 e ，最短路径为最短路径为1919ab2b1b3c1c3d1d2ec25214112610104312111396581052练习练习2：158练习：练习：11851079827746cba1j2j3j4jt=4