大连海事大学《现代优化技术》算法应用1 精确解算法与计算复杂性.pptVIP

动态规划法：算法应用 例 从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 动态规划法：算法应用 r( B1,C1 ) + f1 (C1 ) 3+1 f2 ( B1 ) = min r( B1,C2 ) + f1 (C2 ) = min 3+3 r( B1,C3 ) + f1 (C3 ) 1+4 4 = min 6 = 4 5 第二阶段（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 (最短路线为B1→C1 →D) 动态规划法：算法应用 r( B2,C1 ) + f1 (C1 ) 2+1 f2 ( B2 ) = min r( B2,C2 ) + f1 (C2 ) = min 3+3 r( B2,C3 ) + f1 (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 (最短路线为B2→C1 →D) 动态规划法：算法应用 第一阶段（ A → B ）： A 到B 有二条路线。 f1(A)1 = r(A, B1 )＋ f2 ( B1 ) ＝2＋4＝6 f1 (A)2 = r(A, B2 )＋ f2 ( B2 ) ＝4＋3＝7 ∴ f1 (A) = min = min｛6,7｝=6 r(A, B1 )＋ f2 ( B1 ) r(A, B2 )＋ f2 ( B2 ) (最短路线为A→B1→C1 →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 最短路线为 A→B1→C1 →D 路长为 6 动态规划法：算法应用 动态规划法：算法应用 解：将问题按工厂分为三个阶段，甲、乙、丙三厂分别编号为1，2，3。 设sk=分配给第k个厂至第3个厂的设备台数（ k =1，2，3） xk =分配给第k个厂的设备台数。 已知 s1=5 s2=s1-x1 s3=s2-x2 动态规划法：算法应用 以下我们从第三阶段开始计算： 第三阶段 显然将s3（ s3 =0,1,2,3,4,5）台设备都分配给第3工厂时，也就是s3 = x3时，第3阶段的指标值为最大。 动态规划法：算法应用 第三阶段（ s3=0,1,2,3,4,5 ）