气t; s[[j}=k;} return u 如果用T(n)表示该算法的计算A[1n的时间,则有如下递归关系式 「O(1) 1 (n)≥ 1+∑(T(k)+7(m-k)+1)n>1 当n>1时T(m)≥1+(m-1)+∑7(k)+∑T(m-k)=n+2∑T(k), k=1 k=1 可用数学归纳法直接证明:T(n)≥2-1=92"),这显然不是我们所 期望的。 注意到,在用递归算法自顶向下求解具有最优子结构的问题时 每次产生的子问题并不总是新问题,有些问题被反复计算多次。动态 规划算法正是利用了这种子问题的重叠性质,对每一个问题只解 次,而后将其解保存在一个表格中,当再次需要解此问题时,只是简 单地用常数时间查看一下结果。通常,不同的子问题个数随输入问题 的大小呈多项式增长。因此,用动态规划算法通常只需要多项式时间, 从而获得较高的效率。所以,可用动态规划算法求解得的问题应具备 的另一个基本要素是子问题的重叠性。例如,在矩阵的连乘积问题中, 若用m]表示由第i个矩阵到第j个矩阵的连乘积所用的最少数乘 次数,则计算m[Iln时的子问题共有(n2)个。这是因为,对于
if (t<u) { u=t; s[i][j]=k;} } return u; } 如果用 T(n)表示该算法的计算 A[1:n]的时间，则有如下递归关系式： + + − + > = ≥ ∑ − = 1 1 1 ( ( ) ( ) 1) 1 (1) 1 ( ) n k T k T n k n O n T n 当n > 1时 ∑ ∑ ∑ − = − = − = ≥ + − + + = + 1 1 1 1 1 1 ( ) 1 ( 1) ( ) ( ) 2 ( ) n k n k n k T n n T k T n－k n T k ， 可用数学归纳法直接证明： ( ) 2 (2 ) n 1 n T n ≥ = Ω − ，这显然不是我们所 期望的。 注意到，在用递归算法自顶向下求解具有最优子结构的问题时， 每次产生的子问题并不总是新问题，有些问题被反复计算多次。动态 规划算法正是利用了这种子问题的重叠性质，对每一个问题只解一 次，而后将其解保存在一个表格中，当再次需要解此问题时，只是简 单地用常数时间查看一下结果。通常，不同的子问题个数随输入问题 的大小呈多项式增长。因此，用动态规划算法通常只需要多项式时间， 从而获得较高的效率。所以，可用动态规划算法求解得的问题应具备 的另一个基本要素是子问题的重叠性。例如，在矩阵的连乘积问题中， 若用 m[i][j]表示由第 i 个矩阵到第 j 个矩阵的连乘积所用的最少数乘 次数，则计算 m[1][n]时的子问题共有 ( ) 2 Θ n 个。这是因为，对于
1≤i≤j≤n不同的有序对(j)对应于不同的子问题,不同子问题最多 只有(}+n=6(m2)个。用动态规划解此问题时,在计算过程中,保 存已解决的子问题答案,每个子问题只计算一次,而在后面用到时简 单地査一下,从而避免了大量的重复计算。 求矩阵连乘最优次序的动态规划算法 void Matrix Chain(int p, int n, int**m, int **s) for(int i=l; K<=n; 1++)m00=0; for (int r=2; r<=n;r++) for(int 1=1; 1<=n-r+1; 1++) ntj=i计+r-1; m[]]=m[i+1j+p[i-1*p[]*pl; SGF=1; for (int k=i+; k<; k++i int t=milk]+ m[k+10l+pi-1*p[k]"pl] if(t<mgli m[iG=t S[Dl=k;) 算法 Matrix chain的主要计算量取决于程序中对r,i和k的三重循环
1≤ i ≤ j ≤ n不同的有序对(i, j)对应于不同的子问题，不同子问题最多 只有 ( ) 2 2 n n n + = Θ 个。用动态规划解此问题时，在计算过程中，保 存已解决的子问题答案，每个子问题只计算一次，而在后面用到时简 单地查一下，从而避免了大量的重复计算。 求矩阵连乘最优次序的动态规划算法 void MatrixChain(int p, int n, int * *m, int * *s) { for (int i=1; i<=n; i++) m[i][i]=0; for (int r=2; r<=n; r++){ for (int i=1; i<=n-r+1; i++) int j=i+r-1; m[i][j]= m[i+1][j]+p[i-1]*p[i]*p[j]; s[i][j]=i; for (int k=i+1; k<j; k++){ int t= m[i][k]+ m[k+1][j]+p[i-1]*p[k]*p[j]; if (t< m[i][j]) { m[i][j]=t; s[i][j]=k; } } } } 算法 MatrixChain 的主要计算量取决于程序中对 r, i 和 k 的三重循环
循环体内的计算量为O(1),三重循环的总次数是O(n3),所以,算法 的计算时间上界为O(n3)。 注意,上述算法只是明确给出了矩阵最优连乘次序所用的数乘次 数m[Iln],并未明确给出最优连乘次序,即完全加括号方法。但是 以s[i为元素的2维数组却给出了足够的信息。事实上,sij[]=k 说明,计算连乘积A[ij]的最佳方式应该在矩阵A和A+之间断开 即最优加括号方式为(A[ik]A[k+1j)。下面的算法 Traceback按算法 Matrix Chain计算出的断点信息s指示的加括号方式输出计算A[ij的 最优次序。 根据最优值算法构造最优解 Void Traceback(int i, int j, int**s if (i=ireturn Traceback(i, s[[, s); Traceback(S[0+1,j,s); cout<< Multiply a”≤i<“;”≤s[j[j] cout<<andA”≤(s[+1)<“”≤j;<endl 总结上面解矩阵连乘积问题,我们可以归纳出使用动态规划算法 的基本步骤 1.分析最优解的结构 在这一步中,应该确定要解决的问题应该是具有最小子结构性质
循环体内的计算量为 O(1)，三重循环的总次数是 O(n3 )，所以，算法 的计算时间上界为 O(n3 )。 注意，上述算法只是明确给出了矩阵最优连乘次序所用的数乘次 数 m[1][n]，并未明确给出最优连乘次序，即完全加括号方法。但是 以 s[i][j]为元素的 2 维数组却给出了足够的信息。事实上，s[i][j]=k 说明，计算连乘积 A[i:j]的最佳方式应该在矩阵 Ak和 Ak+1之间断开， 即最优加括号方式为(A[i:k])(A[k+1:j])。下面的算法 Traceback 按算法 MatrixChain 计算出的断点信息 s 指示的加括号方式输出计算 A[i:j]的 最优次序。 根据最优值算法构造最优解 Void Traceback(int i, int j, int * * s) { if (i==j) return; Traceback(i, s[i][j], s); Traceback(s[i][j]+1, j, s); cout << “Multiply A” << i << “,” << s[i][j]; cout << “and A” << (s[i][j] +1) << “,” << j; << endl; } 总结上面解矩阵连乘积问题，我们可以归纳出使用动态规划算法 的基本步骤： 1． 分析最优解的结构 在这一步中，应该确定要解决的问题应该是具有最小子结构性质
这是选择动态规划算法的基础。 2.建立递归关系 第一步的结构分析已经为建立递归关系奠定了基础。这一步的主要 任务是递归地定义最优值,并建立该问题与其子问题最优值之间的 递归关系。例如在矩阵连乘积问题中,递归关系为 0 mU=1min(m+m/k+1B+m17/D}<j i≤k≤j 在经典O/1规划问题中的递归关系是 g(X)=max{g+1(X)g/+1(X-w+1)+p+1(68 在多段图问题中的递归关系是 COST(i,)=min c(, D)+COST(i+1, 0))(6.9) 这里j表示取V中的顶点 3.计算最优值 依据递归关系式可以自底向上的方式或自顶向下的方式进行计算, 在计算过程中保存已经解决的子问题答案。每个子问题只计算一次, 而在后面需要时只要简单査一下,从而避免大量的重复计算,最终获 得多项式时间的算法 4.造最优解 依据求最优值时记录的信息,构造出最优解。 上述归纳的4个阶段是一个整体,必要时才分步完成,很多时是统 一来完成的
这是选择动态规划算法的基础。 2． 建立递归关系 第一步的结构分析已经为建立递归关系奠定了基础。这一步的主要 任务是递归地定义最优值，并建立该问题与其子问题最优值之间的 递归关系。例如在矩阵连乘积问题中，递归关系为 { } + + + < = = ≤ ≤ m[i] [k] m[k ] [j] p[i- ]*p[k]*p[j] i j i j m i j i k j min 1 1 0 [ ][ ] 在经典 0/1 规划问题中的递归关系是 g(X ) = max{g j+1(X ), g j +1(X − wj +1) + p j +1} (6.8) 在多段图问题中的递归关系是 ( , ) min { ( , ) ( 1, )} ,( , ) 1 COST i j c j l COST i l l Vi i l E = + + ∈ + ∈ (6.9) 这里 j 表示取 Vi中的顶点 j。 3． 计算最优值 依据递归关系式可以自底向上的方式或自顶向下的方式进行计算， 在计算过程中保存已经解决的子问题答案。每个子问题只计算一次， 而在后面需要时只要简单查一下，从而避免大量的重复计算，最终获 得多项式时间的算法。 4． 造最优解 依据求最优值时记录的信息，构造出最优解。 上述归纳的 4 个阶段是一个整体，必要时才分步完成，很多时是统 一来完成的
§2多段图问题 多段图是一种简单而经典的模型,它既能地反映了动态规划算法的基 本特征,而且在实际问题中有较多的应用。 ·乘0 由后向前的处理方法(动态规划方法) 由前向后的处理方法(备忘录方法) 根据(69)式,我们可以由后向前逐步确定各阶段中的顶点到汇顶点t 的最短路径。对于如上的5阶段网络图,上图中的红色字体标出了各 顶点到汇顶点t的最短距离。 事实上,我们也可以由前向后逐步确定由源顶点s到各阶段中顶
§2 多段图问题 多段图是一种简单而经典的模型，它既能地反映了动态规划算法的基 本特征，而且在实际问题中有较多的应用。 V1 V2 V3 V4 V5 7 4 4 6 9 7 4 4 9 2 5 7 2 S 7 5 3 2 2 t 16 3 18 1 11 5 2 7 5 15 11 6 5 8 由后向前的处理方法（动态规划方法） V1 V2 V3 V4 V5 9 13 4 6 9 9 4 4 7 2 5 7 2 S 7 11 3 14 2 t 3 3 1 16 11 5 2 10 5 2 11 6 16 8 由前向后的处理方法（备忘录方法） 根据(6.9)式，我们可以由后向前逐步确定各阶段中的顶点到汇顶点 t 的最短路径。对于如上的 5 阶段网络图，上图中的红色字体标出了各 顶点到汇顶点 t 的最短距离。 事实上，我们也可以由前向后逐步确定由源顶点 s 到各阶段中顶 1 2 4 6 9 10 11 12 3 7 8 5 1 2 4 6 9 10 11 12 3 7 8 5