山东师范大学信息科学与工程学院软件工程研究所 徐连诚 E-Mail：lchxu@163.com 2006年10月9日 算法设计与分析 山东师范大学信息科学与工程学院软件工程研究所 徐连诚 E-Mail：lchxu@163.com 2006年10月9日

第三章 动态规划 本章主要知识点：(11) 3.1 矩阵连乘问题 3.2 动态规划算法的基本要素 3.3 最长公共子序列问题 3.4 最大子段和 3.5 凸多边形的最优三角剖分 3.6 多边形游戏 3.7 图像压缩 3.8 电路布线 3.9 流水作业调度 3.10 0-1背包问题 3.11 最有二叉搜索树 3.12 动态规划加速原理 >

引言 Those who cannot remember the past are doomed to repeat it. n = 动态规划算法与分治法类似，其基本思想也是将待求解问题分解成若干个子问题。 但是经分解得到的子问题往往不是互相独立的。不同子问题的数目常常只有多项式量级。在用分治法求解时，有些子问题被重复计算了许多次。 如果能够保存已解决的子问题的答案，而在需要时再找出已求得的答案，就可以避免大量重复计算，从而得到多项式时间算法。 Those who cannot remember the past are doomed to repeat it. ——George Santayana, The life of Reason, Book I: Introduction and Reason in Common Sense (1905) n = n/2 T(n/4) T(n) n T(n) = n/2 T(n/4) n T(n/2) T(n) = 美国哲学家乔治.桑塔雅那(George Santayana)，忽略历史会使我们重蹈覆辙，而了解过去可以使我们走向光明的未来。

动态规划基本步骤 找出最优解的性质，并刻划其结构特征。 递归地定义最优值。 以自底向上的方式计算出最优值。 根据计算最优值时得到的信息，构造最优解。

3.1 矩阵连乘问题 给定n个矩阵{A1,A2,...,An}，其中Ai与Ai+1是可乘的，i=1,2,...,n-1。考察这n个矩阵的连乘积A1A2...An。 由于矩阵乘法满足结合律，所以计算矩阵的连乘可以有许多不同的计算次序。这种计算次序可以用加括号的方式来确定。若一个矩阵连乘积的计算次序完全确定，也就是说该连乘积已完全加括号，则可以依此次序反复调用2个矩阵相乘的标准算法计算出矩阵连乘积。 完全加括号的矩阵连乘积可递归地定义为： 单个矩阵是完全加括号的； 矩阵连乘积A是完全加括号的，则A可表示为2个完全加括号的矩阵连乘积B和C的乘积并加括号，即A=(BC)。 设有四个矩阵A,B,C,D，它们的维数分别是：A=50×10，B=10×40，C=40×30，D=30×5 总共有五种完全加括号的方式：(A((BC)D)) (A(B(CD))) ((AB)(CD)) (((AB)C)D) ((A(BC))D) 其数乘次数分别为：16000, 10500, 36000, 87500, 34500

穷举搜索法 问题描述：给定n个矩阵｛A1,A2,…,An｝，其中Ai与Ai+1是可乘的，i=1，2…，n-1。如何确定计算矩阵连乘积的计算次序，使得依此次序计算矩阵连乘积需要的数乘次数最少。 穷举法：列举出所有可能的计算次序，并计算出每一种计算次序相应需要的数乘次数，从中找出一种数乘次数最少的计算次序。 算法复杂度分析： 对于n个矩阵的连乘积，设其不同的计算次序为P(n)。 由于每种加括号方式都可以分解为两个子矩阵的加括号问题：(A1...Ak)(Ak+1…An)可以得到关于P(n)的递推式如下： 也就是说，P(n)是随n的增长成指数增长的。

动态规划法——1.分析最优解的结构 下面我们考虑用求解。 预处理： 分析最优解的结构 将矩阵连乘积AiAi+1...Aj简记为A[i:j]，这里i≤j。 考察计算A[i:j]的最优计算次序。设这个计算次序在矩阵Ak和Ak+1之间将矩阵链断开，i≤k<j，则其相应完全加括号方式为（AiAi+1... Ak）（Ak+1 Ak+2... Aj ）。 计算量：A[i:k]的计算量加上A[k+1:j]的计算量，再加上A[i:k]和A[k+1:j]相乘的计算量。 分析最优解的结构 特征：计算A[i:j]的最优次序所包含的计算矩阵子链 A[i:k]和A[k+1:j]的次序也是最优的。 矩阵连乘计算次序问题的最优解包含着其子问题的最优解。这种性质称为最优子结构性质。问题的最优子结构性质是该问题可用动态规划算法求解的显著特征。

2.建立递归关系 设计算A[i:j]，1≤i≤j≤n，所需要的最少数乘次数m[i,j]，则原问题的最优值为m[1,n]。 当i=j时，A[i:j]=Ai，因此，m[i,i]=0，i=1,2,…,n。 当i<j时，m[i,j]=m[i,k]+m[k+1,j]+pi-1pkpj，这里Ai的维数为pi-1×pi。 可以递归地定义m[i,j]为： k的位置只有j-i种可能。

3.计算最优值 对于1≤i≤j≤n不同的有序对(i,j)对应于不同的子问题。 因此，不同子问题的个数最多只有 由此可见，在递归计算时，许多子问题被重复计算多次。这也是该问题可用动态规划算法求解的又一显著特征。 用动态规划算法解此问题，可依据其递归式以自底向上的方式进行计算。在计算过程中，保存已解决的子问题答案。每个子问题只计算一次，而在后面需要时只要简单查一下，从而避免大量的重复计算，最终得到多项式时间的算法。

算法描述 算法描述： 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;} 　　　} 　　} }

示例 A1 A2 A3 A4 A5 A6 3035 3515 155 510 1020 2025

4.构造最优解 算法描述：略。 复杂性分析： 算法MatrixChain的主要计算量取决于算法中对r，i和k的3重循环。循环体内的计算量为O(1)，而3重循环的总次数为O(n3)。因此算法的计算时间上界为O(n3)。算法所占用的空间显然为O(n2)。 算法TraceBack的复杂性？

3.2 动态规划算法的基本要素 从计算矩阵连乘积最优计算次序的动态规划算法可以看出，该算法的有效性依赖于问题本身所具有的两个重要性质：最优子结构性质和子问题重叠性质。从一般意义上讲，问题的这两个重要性质是该问题可以用动态规划算法求解的基本要素。本节着重介绍： 最优子结构 重叠子问题 备忘录方法 此外，本节最后对动态规划算法与备忘录方法的适用条件作了简单介绍。

一、最优子结构 矩阵连乘计算次序问题的最优解包含着其子问题的最优解。这种性质称为最优子结构性质。 在分析问题的最优子结构性质时，所用的方法具有普遍性：首先假设由问题的最优解导出的子问题的解不是最优的，然后再设法说明在这个假设下可构造出比原问题最优解更好的解，从而导致矛盾。 利用问题的最优子结构性质，以自底向上的方式递归地从子问题的最优解逐步构造出整个问题的最优解。最优子结构是问题能用动态规划算法求解的前提。 注意：同一个问题可以有多种方式刻划它的最优子结构，有些表示方法的求解速度更快（空间占用小，问题的维度低）

二、重叠子问题 递归算法求解问题时，每次产生的子问题并不总是新问题，有些子问题被反复计算多次。这种性质称为子问题的重叠性质。 动态规划算法，对每一个子问题只解一次，而后将其解保存在一个表格中，当再次需要解此子问题时，只是简单地用常数时间查看一下结果。 通常不同的子问题个数随问题的大小呈多项式增长。因此用动态规划算法只需要多项式时间，从而获得较高的解题效率。

三、备忘录方法 备忘录方法的控制结构与直接递归方法的控制结构相同，区别在于备忘录方法为每个解过的子问题建立了备忘录以备需要时查看，避免了相同子问题的重复求解。 int LookupChain(int i，int j) { if (m[i][j] > 0) return m[i][j]; if (i == j) return 0; int u = LookupChain(i，i) + LookupChain(i+1，j) + p[i-1]*p[i]*p[j]; s[i][j] = i; for (int k = i+1; k < j; k++) { int t = LookupChain(i，k) + LookupChain(k+1，j) + p[i-1]*p[k]*p[j]; if (t < u) { u = t; s[i][j] = k;} } m[i][j] = u; return u; 算法复杂性：T(n)=O(n3)

关于动态规划算法和备忘录方法的适用条件 综上所述，矩阵连乘积的最优计算次序问题可用自顶向下的备忘录方法或自底向上的动态规划算法在O(n3)计算时间内求解。 这两个算法都利用了子问题重叠性质。总共有θ(n2)个不同的子问题，对每个子问题两种算法都只解一次并记录答案。当再次遇到该子问题时，简单地取用已得到的答案，节省了计算量，提高了算法的效率。 适用条件：一般来说，当一个问题的所有子问题都至少要解一次时，用动态规划算法比用备忘录方法好。此时，动态规划算法没有任何多余的计算，还可以利用其规则的表格存取方式来减少在动态规划算法中的计算时间和空间需求。当子问题空间中部分子问题可以不必求解时，易用备忘录方法则较为有利，因为从其控制结构可以看出，该方法只解那些确实需要求解的子问题。

3.3 最长公共子序列 概述： 若给定序列X={x1,x2,…,xm}，则另一序列Z={z1,z2,…,zk}，是X的子序列是指存在一个严格递增下标序列{i1,i2,…,ik}使得对于所有j=1,2,…,k有：zj=xij。例如，序列Z={B，C，D，B}是序列X={A，B，C，B，D，A，B}的子序列，相应的递增下标序列为{2，3，5，7}。 给定2个序列X和Y，当另一序列Z既是X的子序列又是Y的子序列时，称Z是序列X和Y的公共子序列。 给定2个序列X={x1,x2,…,xm}和Y={y1,y2,…,yn}，找出X和Y的最长公共子序列。

最长公共子序列的结构 设序列X={x1,x2,…,xm}和Y={y1,y2,…,yn}的最长公共子序列为Z={z1,z2,…,zk} ，则 若xm=yn，则zk=xm=yn，且Zk-1是Xm-1和Yn-1的最长公共子序列。 若xm≠yn且zk≠xm，则Z是Xm-1和Y的最长公共子序列。 若xm≠yn且zk≠yn，则Z是X和Yn-1的最长公共子序列。 由此可见，2个序列的最长公共子序列包含了这2个序列的前缀的最长公共子序列。因此，最长公共子序列问题具有最优子结构性质。

子问题的递归结构 由最长公共子序列问题的最优子结构性质建立子问题最优值的递归关系。用c[i][j]记录序列和的最长公共子序列的长度。其中， Xi={x1,x2,…,xi}；Yj={y1,y2,…,yj}。当i=0或j=0时，空序列是Xi和Yj的最长公共子序列。故此时C[i][j]=0。其它情况下，由最优子结构性质可建立递归关系如下：

计算最优值 由于在所考虑的子问题空间中，总共有θ(mn)个不同的子问题，因此，用动态规划算法自底向上地计算最优值能提高算法的效率。 void LCSLength(int m，int n，char *x，char *y，int **c，int **b) { int i，j; for (i = 1; i <= m; i++) c[i][0] = 0; for (i = 1; i <= n; i++) c[0][i] = 0; for (i = 1; i <= m; i++) for (j = 1; j <= n; j++) { if (x[i]==y[j]) { c[i][j]=c[i-1][j-1]+1; b[i][j]=1;} else if (c[i-1][j]>=c[i][j-1]) { c[i][j]=c[i-1][j]; b[i][j]=2;} else { c[i][j]=c[i][j-1]; b[i][j]=3; } }

构造最长公共子序列 算法描述： void LCS(int i，int j，char *x，int **b) { } if (i ==0 || j==0) return; if (b[i][j]== 1){ LCS(i-1，j-1，x，b); cout<<x[i]; } else if (b[i][j]== 2) LCS(i-1，j，x，b); else LCS(i，j-1，x，b); }

算法的改进 在算法lcsLength和lcs中，可进一步将数组b省去。事实上，数组元素c[i][j]的值仅由c[i-1][j-1]，c[i-1][j]和c[i][j-1]这3个数组元素的值所确定。对于给定的数组元素c[i][j]，可以不借助于数组b而仅借助于c本身在时间内确定c[i][j]的值是由c[i-1][j-1]，c[i-1][j]和c[i][j-1]中哪一个值所确定的。 如果只需要计算最长公共子序列的长度，则算法的空间需求可大大减少。事实上，在计算c[i][j]时，只用到数组c的第i行和第i-1行。因此，用2行的数组空间就可以计算出最长公共子序列的长度。进一步的分析还可将空间需求减至O(min(m,n))。

3.4 最大子段和 问题描述： 给定由n个整数（包含负整数）组成的序列a1,a2,...,an，求该序列子段和的最大值。当所有整数均为负值时定义其最大子段和为0。 依此定义，所求的最优值为： 例如，当(a1,a2, a3, a4, a5,a6)=(-2,11,-4,13,-5,-2)时，最大子段和为：

1. 一个简单算法 一个简单算法： 算法有3重循环，复杂性为O(n3)。 由于有： 算法可作如下改进： 改进后的算法复杂性为O(n2) 。 int MaxSum(int n, a, &besti, &bestj) { int sum=0; for(i=1;i<=n;i++) for(j=1;j<=n;j++){ int thissum=0; for(k=i;k<=j;k++)thissum+=a[k]; if(thissum>sum){ sum=thissum; besti=i; Bestj=j; } return sum; 算法有3重循环，复杂性为O(n3)。 由于有： 算法可作如下改进： int MaxSum(int n, a, &besti, &bestj) { int sum=0; for(i=1;i<=n;i++){ int thissum=0; for(j=1;j<=n;j++){ thissum+=a[j]; if(thissum>sum){ sum=thissum; besti=i; bestj=j; } 改进后的算法复杂性为O(n2) 。

2. 分治方法求解 从问题的解的结构可以看出，它适合于用分治策略求解： 从而设计出下面所示的分治算法。 如果将所给的序列a[1:n]分为长度相等的两段a[1:n/1]和a[n/2+1:n]，分别求出这两段的最大子段和，则a[1:n]的最大子段和有三种情形： a[1:n]的最大子段和与a[1:n/2]的最大子段和相同； a[1:n]的最大子段和与a[n/2+1:n]的最大子段和相同； a[1:n]的最大子段和为下面的形式。 A、B这两种情形可递归求得。对于情形C，容易看出，a[n/2]与a[n/2+1]在最优子序列中。因此，我们可以在a[1:n/2]和a[n/2+1:n]中分别计算出如下的s1和s2。则s1+s2即为出现情形C使得最优值。 从而设计出下面所示的分治算法。 int MaxSubSum(int a, int left, int right) { int sum=0; if (left==right)sum=a[left]>0?a[left]:0; else{int center=(left+right)/2; int leftsum=MaxSubSum(a,left,center); int rightsum=MaxSubSum(a,center+1,right); int s1=0;lefts=0; for (int i=center;i>=left;i--) { lefts+=a[i]; if (lefts>s1) s1=lefts; } int s2=0;rights=0; for (int i=center+1;i<=right;i++) { rights+=a[i]; if (rights>s2) s2=rights; sum=s1+s2; if (sum<leftsum) sum=leftsum; if (sum<sightsum) sum=rightsum; return sum;

3. 动态规划方法求解 在对上述分治算法的分析中我们注意到， 由bj的定义易知，当bj-1>0时bj=bj-1+aj，否则bj=aj。由此可得计算bj的动态规划递归式bj=max{bj-1+aj，aj}，1≤j≤n。 据此，可设计出求最大子段和的动态规划算法如下： int MaxSum(int n, int a) { int sum=0; b=0; for (i=1;i<=n;i++) if (b>0) b+=a[i]; else b=a[i]; if (b>sum) sum=b; } return sum; 显然该算法的计算时间为O(n)。

4. 算法的推广 最大矩阵和问题，略 最大m子段和问题，略

3.5 凸多边形最优三角剖分 用多边形顶点的逆时针序列表示凸多边形，即P={v0,v1,…,vn-1}表示具有n条边的凸多边形。 若vi与vj是多边形上不相邻的2个顶点，则线段vivj称为多边形的一条弦。弦将多边形分割成2个多边形{vi,vi+1,…,vj}和{vj,vj+1,…vi}。 多边形的三角剖分是将多边形分割成互不相交的三角形的弦的集合T。 给定凸多边形P，以及定义在由多边形的边和弦组成的三角形上的权函数w。要求确定该凸多边形的三角剖分，使得该三角剖分中诸三角形上权之和为最小。

三角剖分的结构及其相关问题 一个表达式的完全加括号方式相应于一棵完全二叉树，称为表达式的语法树。例如，完全加括号的矩阵连乘积((A1(A2A3))(A4(A5A6)))所相应的语法树如图 (a)所示。 凸多边形{v0,v1,…vn-1}的三角剖分也可以用语法树表示。例如，图 (b)中凸多边形的三角剖分可用图 (a)所示的语法树表示。 矩阵连乘积中的每个矩阵Ai对应于凸(n+1)边形中的一条边vi-1vi。三角剖分中的一条弦vivj，i<j，对应于矩阵连乘积A[i+1:j]。

最优子结构性质 凸多边形的最优三角剖分问题有最优子结构性质。 事实上，若凸(n+1)边形P={v0,v1,…,vn-1}的最优三角剖分T包含三角形v0vkvn，1≤k≤n-1，则T的权为3个部分权的和：三角形v0vkvn的权，子多边形{v0,v1,…,vk}和{vk,vk+1,…,vn}的权之和。可以断言，由T所确定的这2个子多边形的三角剖分也是最优的。因为若有{v0,v1,…,vk}或{vk,vk+1,…,vn}的更小权的三角剖分将导致T不是最优三角剖分的矛盾。

最优三角剖分的递归结构 定义t[i][j]，1≤i<j≤n为凸子多边形{vi-1,vi,…,vj}的最优三角剖分所对应的权函数值，即其最优值。为方便起见，设退化的多边形{vi-1,vi}具有权值0。据此定义，要计算的凸(n+1)边形P的最优权值为t[1][n]。 t[i][j]的值可以利用最优子结构性质递归地计算。当j-i≥1时，凸子多边形至少有3个顶点。由最优子结构性质，t[i][j]的值应为t[i][k]的值加上t[k+1][j]的值，再加上三角形vi-1vkvj的权值，其中i≤k≤j-1。由于在计算时还不知道k的确切位置，而k的所有可能位置只有j-i个，因此可以在这j-i个位置中选出使t[i][j]值达到最小的位置。由此，t[i][j]可递归地定义为：

计算最优值 凸n+1边形P={v0,v1,...,vn}的最有三角剖分动态规划算法MinWT： void MinWT(int n, type **t, int **s) { for (int i=1;i<=n;i++) t[i][i]=0; for (int r=2; r<=n; r++) for (i=1; i<=n; i++){ int j=i+r-1; t[i][j]=t[i][i]+t[i+1][j]+w(i-1,i,j); s[i][j]=i; for (int k=i+1;k<j;k++){ int u=t[i][k]+t[k+1][j]+w(i-1,k,j); if (u<t[i][j]){t[i][j]=u;s[i][j]=k;} } 复杂性：T(n)=O(n3) S(n)=O(n2)

构造最优解 思考：构造一个在O(n)时间内的求最优解的算法。

3.6 多边形游戏 多边形游戏是一个单人玩的游戏，开始时有一个由n个顶点构成的多边形。每个顶点被赋予一个整数值，每条边被赋予一个运算符“+”或“*”。所有边依次用整数从1到n编号。 游戏第1步，将一条边删除。 随后n-1步按以下方式操作： (1)选择一条边E以及由E连接着的2个顶点V1和V2； (2)用一个新的顶点取代边E以及由E连接着的2个顶点V1和V2。将由顶点V1和V2的整数值通过边E上的运算得到的结果赋予新顶点。 最后，所有边都被删除，游戏结束。游戏的得分就是所剩顶点上的整数值。 问题:对于给定的多边形，计算最高得分。

op[1], v[1], op[2], v[2], ..., op[n], v[n] 最优子结构性质 设所给的多边形的定点和便的顺时针序列为： op[1], v[1], op[2], v[2], ..., op[n], v[n] 在所给多边形中，从顶点i(1≤i≤n)开始，长度为j(链中有j个顶点)的顺时针链p(i，j) 可表示为v[i]，op[i+1]，…，v[i+j-1]。 如果这条链的最后一次合并运算在op[i+s]处发生(1≤s≤j-1)，则可在op[i+s]处将链分割为2个子链p(i，s)和p(i+s，j-s)。 设m1是对子链p(i，s)的任意一种合并方式得到的值，而a和b分别是在所有可能的合并中得到的最小值和最大值。m2是p(i+s，j-s)的任意一种合并方式得到的值，而c和d分别是在所有可能的合并中得到的最小值和最大值。依此定义有a≤m1≤b，c≤m2≤d (1)当op[i+s]='+'时，显然有a+c≤m≤b+d (2)当op[i+s]='*'时，有min{ac，ad，bc，bd}≤m≤max{ac，ad，bc，bd} 换句话说，主链的最大值和最小值可由子链的最大值和最小值得到。

a=m[i,s,0]，b=m[i,s,1]，c=m[i+s,j-s,0]，d=m[i+s,j-s,0] 递归求解 由前面的分析可知，为了求链合并的最大值，必须同时求子链合并的最大值和最小值。 设m[i,j,0]是链p(i,j)合并的最小值，m[i,j,1]是最大值。 若最优合并在op[i+s]处将p(i,j)分为2个长度小于j的子链p(i,s)和p(i+s,j-s)，且从顶点i开始的长度小于j的子链的最大值和最小值均已计算出。为叙述方便，记 a=m[i,s,0]，b=m[i,s,1]，c=m[i+s,j-s,0]，d=m[i+s,j-s,0] (1)当op[i+s]=‘+’时，m[i,j,0]=a+c，m[i,j,1]=b+d (2)当op[i+s]=‘*’时，m[i,j,0]=min{ac,ad,bc,bd}，m[i,j,1]=max{ac,ad,bc,bd} 综合(1)和(2)，将p(i,j)在op[i+s]处断开的最大值为maxf(i,j,s)，最小值为minf(i,j,s)，则 由于最优断开位置s有1≤s≤j-1的j-1种情况，由此可知 初始边界值显然为m[i,1,0]=v[i], m[i,1,1]=v[i], 1≤i≤n。

算法描述 算法描述：P63 算法复杂性：O(n3)

3.7 图像压缩 图象的变位压缩存储格式将所给的象素点序列{p1,p2,…,pn},0≤pi≤255分割成m个连续段S1,S2,…,Sm。第i个象素段Si中(1≤i≤m)，有l[i]个象素,且该段中每个象素都只用b[i]位表示。设　　　　　则第i个象素段Si为 设 ，则hi≤b[i]≤8。因此需要用3位表示b[i],如果限制1≤l[i]≤255，则需要用8位表示l[i]。因此，第i个象素段所需的存储空间为l[i]*b[i]+11位。按此格式存储象素序列{p1,p2,…,pn}，需要　　　　　　　位的存储空间。 图象压缩问题要求确定象素序列{p1,p2,…,pn}的最优分段，使得依此分段所需的存储空间最少。每个分段的长度不超过256位。

最优子结构性质 设l[i]，b[i]，是{p1,p2,…,pn}的最优分段。显而易见，l[1]，b[1]是{p1,…,pl[1]}的最优分段，且l[i]，b[i]，是{pl[1]+1,…,pn}的最优分段。即图象压缩问题满足最优子结构性质。 设s[i]，1≤i≤n，是象素序列{p1,…,pn}的最优分段所需的存储位数。由最优子结构性质易知： 其中 算法复杂度分析：由于算法compress中对k的循环次数不超这256，故对每一个确定的i，可在时间O(1)内完成的计算。因此整个算法所需的计算时间为O(n)。

递归计算最优值与构造最优解 递归计算最优值算法描述：P64—65 构造最优解算法描述：P65—66 Compress：S(n)=O(n)，T(n)=O(n)

3.8 电路布线 在一块电路板的上、下2端分别有n个接线柱。根据电路设计，要求用导线(i,π(i))将上端接线柱与下端接线柱相连，如图所示。其中π(i)是{1,2,…,n}的一个排列。导线(i,π(i))称为该电路板上的第i条连线。对于任何1≤i<j≤n，第i条连线和第j条连线相交的充分且必要的条件是π(i)>π(j)。 电路布线问题要确定将哪些连线安排在第一层上，使得该层上有尽可能多的连线。换句话说，该问题要求确定导线集Nets={(i,π(i)),1≤i≤n}的最大不相交子集。 ∏=｛8，7，4，2，5，1，9，3，10，6｝

最优子结构性质 记N(i,j)={t|(t,π(t))∈Nets,t≤i,π(t)≤j}，N(i,j)的最大不相交子集为MNS(i,j)，Size(i,j)=|MNS(i,j)|。 (1)当i=1时， (2)当i>1时， j<π(i)。此时， (i,π(i))┐∈N(i,j)。故在这种情况下，N(i,j)=N(i-1,j)，从而Size(i,j)=Size(i-1,j)。 j≥π(i)。若(i,π(i))∈MNS(i,j) 。 则对任意(t,π(t)) ∈MNS(i,j)有t<i且π(t)<π(i)。在这种情况下MNS(i,j)-{(i,π(i))}是N(i-1,π(i)-1)的最大不相交子集。若(i,π(i))┐∈N(i,j)，则对任意(t,π(t)) ∈MNS(i,j)有t<i。从而MNS(i,j)∠N(i-1,j)。因此，Size(i,j)≤Size(i-1,j)。另一方面MNS(i-1,j)∠N(i,j)，故又有Size(i,j)≥Size(i-1,j)，从而Size(i,j)=Size(i-1,j)。 综上可知，电路布线问题满足最优子结构性质。

递归计算最优值 算法描述：详见P67—68，计算最优值，构造最优解。 算法复杂性： 思考：求解目标为最少层数时的算法问题。 MNS算法：T(n)=O(n2)，S(n)=(n2) Traceback算法：T(n)=O(n) 思考：求解目标为最少层数时的算法问题。 void MNS(C[], n, **size) { for (j=0; j<C[1]; j++) size[1][j]=0; for (j=C[1]; j<=n; j++) size[1][j]=0; for (i=2; i<n; i++) { for (j=0; j<C[i]; j++) size[i][j]=size[i-1][j]; for (j=C[j]; j<=n; j++) size[i][j]=max{size[i-1][j], size[i-1][C[i]-1]+1}; } size[n][n]==max{size[n-1][n], size[n-1][C[n]-1]+1}; void Traceback(C[], **size, n, Net[], m) { int j=n; m=0; for (int i=n; i>1; i--) if (size[i][j]!=size[i-1][j]{Net[m++]=i; j=C[i]-1;} if (j>=C[1]) Net[m++]=1; }

3.9 流水作业问题 n个作业{1，2，…，n}要在由2台机器M1和M2组成的流水线上完成加工。每个作业加工的顺序都是先在M1上加工，然后在M2上加工。M1和M2加工作业i所需的时间分别为ai和bi。 流水作业调度问题要求确定这n个作业的最优加工顺序，使得从第一个作业在机器M1上开始加工，到最后一个作业在机器M2上加工完成所需的时间最少。 分析： 直观上，一个最优调度应使机器M1没有空闲时间，且机器M2的空闲时间最少。在一般情况下，机器M2上会有机器空闲和作业积压2种情况。 设全部作业的集合为N={1，2，…，n}。S是N的作业子集。在一般情况下，机器M1开始加工S中作业时，机器M2还在加工其他作业，要等时间t后才可利用。将这种情况下完成S中作业所需的最短时间记为T(S,t)。流水作业调度问题的最优值为T(N,0)。

最优子结构性质 设π是所给n个流水作业的一个最优调度，它所需的加工时间为 aπ(1)+T’。其中T’是在机器M2的等待时间为bπ(1)时，安排作业π(2)，…，π(n)所需的时间。记S=N-{π(1)}，则有T’=T(S,bπ(1))。 证明：事实上，由T的定义知T’≥T(S,bπ(1))。若T’>T(S,bπ(1))，设π’是作业集S在机器M2的等待时间为bπ(1)情况下的一个最优调度。则π(1)，π’(2)，…，π’(n)是N的一个调度，且该调度所需的时间为aπ(1)+T(S,bπ(1))<aπ(1)+T’。这与π是N的最优调度矛盾。故T’≤T(S,bπ(1))。从而T’=T(S,bπ(1))。这就证明了流水作业调度问题具有最优子结构的性质。 由流水作业调度问题的最优子结构性质可知， 思考：直接利用该递归关系构造动态规划算法。

Johnson不等式 对递归式的深入分析表明，算法可进一步得到简化。 设π是作业集S在机器M2的等待时间为t时的任一最优调度。若π(1)=i, π(2)=j。则由动态规划递归式可得： T(S,t)=ai+T(S-{i},bi+max{t-ai,0})=ai+aj+T(S-{i,j},tij) 其中， 如果作业i和j满足min{bi,aj}≥min{bj,ai}，则称作业i和j满足Johnson不等式。

流水作业调度的Johnson法则 交换作业i和作业j的加工顺序，得到作业集S的另一调度，它所需的加工时间为T’(S,t)=ai+aj+T(S-{i,j},tji) 其中， 当作业i和j满足Johnson不等式时，有 由此可见当作业i和作业j不满足Johnson不等式时，交换它们的加工顺序后，不增加加工时间。对于流水作业调度问题，必存在最优调度 ，使得作业(i)和(i+1)满足Johnson不等式。进一步还可以证明，调度满足Johnson法则当且仅当对任意i<j有 由此可知，所有满足Johnson法则的调度均为最优调度。

算法及其复杂性 流水作业调度问题的Johnson算法： 思考：上述步骤得到的作业序列满足Johnson法则。 算法描述：P70。 令N1={i|ai<bi}，N2={i|ai≥bi}； 将N1中作业依ai的非减序排序；将N2中作业依bi的非增序排序； N1中作业接N2中作业构成满足Johnson法则的最优调度。 思考：上述步骤得到的作业序列满足Johnson法则。 算法描述：P70。 算法复杂度分析：算法的主要计算时间花在对作业集的排序。因此，在最坏情况下算法所需的计算时间为O(nlogn)。所需的空间为O(n)。

3.10 0-1背包问题 给定n种物品和一背包。物品i的重量是wi，其价值为vi，背包的容量为C。问应如何选择装入背包的物品，使得装入背包中物品的总价值最大? 0-1背包问题是一个特殊的整数规划问题。

最优子结构性质 设所给0-1背包问题的子问题 的最优值为m(i，j)，即m(i，j)是背包容量为j，可选择物品为i，i+1，…，n时0-1背包问题的最优值。由0-1背包问题的最优子结构性质，可以建立计算m(i，j)的递归式如下。

计算最优值算法及其复杂性 算法描述：P72 算法复杂度分析：从m(i，j)的递归式容易看出，算法需要O(nc)计算时间。当背包容量c很大时，算法需要的计算时间较多。例如，当c>2n时，算法需要Ω(n2n)计算时间。

算法改进 由m(i,j)的递归式容易证明，在一般情况下，对每一个确定的i(1≤i≤n)，函数m(i,j)是关于变量j的阶梯状单调不减函数。跳跃点是这一类函数的描述特征。在一般情况下，函数m(i,j)由其全部跳跃点惟一确定。如图所示。 对每一个确定的i(1≤i≤n)，用一个表p[i]存储函数m(i，j)的全部跳跃点。表p[i]可依计算m(i，j)的递归式递归地由表p[i+1]计算，初始时p[n+1]={(0，0)}。

示例：n=3，c=6，w={4,3,2}，v={5,2,1}。 x (0,0) m(4,x) (2,1) m(4,x-2)+1 m(3,x) (3,2) m(3,x-3)+2 (5,3) m(2,x) m(2,x-4)+5 (4,5) (6,6) (7,7) (9,8) (0, 0) (2, 1) m(1,x)

关于m(i,j) 函数m(i,j)是由函数m(i+1,j)与函数m(i+1,j-wi)+vi作max运算得到的。因此，函数m(i,j)的全部跳跃点包含于函数m(i+1，j)的跳跃点集p[i+1]与函数m(i+1，j-wi)+vi的跳跃点集q[i+1]的并集中。易知，(s,t)q[i+1]当且仅当wisc且(s-wi,t-vi)p[i+1]。因此，容易由p[i+1]确定跳跃点集q[i+1]如下q[i+1]=p[i+1](wi,vi)={(j+wi,m(i,j)+vi)|(j,m(i,j))p[i+1]} 另一方面，设(a，b)和(c，d)是p[i+1]q[i+1]中的2个跳跃点，则当ca且d<b时，(c，d)受控于(a，b)，从而(c，d)不是p[i]中的跳跃点。除受控跳跃点外，p[i+1]q[i+1]中的其他跳跃点均为p[i]中的跳跃点。 由此可见，在递归地由表p[i+1]计算表p[i]时，可先由p[i+1]计算出q[i+1]，然后合并表p[i+1]和表q[i+1]，并清除其中的受控跳跃点得到表p[i]。

另一个例子 实例： n=5，c=10，w={2,2,6,5,4}， v={6,3,5,4,6}。 初始时p[6]={(0,0)}，(w5,v5)=(4,6)。 因此，q[6]=p[6](w5,v5)={(4,6)}。 p[5]={(0,0),(4,6)}。 q[5]=p[5](w4,v4)={(5,4),(9,10)}。从跳跃点集p[5]与q[5]的并集p[5]∪ q[5]={(0,0),(4,6),(5,4),(9,10)}中看到跳跃点(5,4)受控于跳跃点(4,6)。将受控跳跃点(5,4)清除后，得到p[4]={(0,0),(4,6),(9,10)} q[4]=p[4](6，5)={(6，5)，(10，11)} p[3]={(0，0)，(4，6)，(9，10)，(10，11)} q[3]=p[3](2，3)={(2，3)，(6，9)} p[2]={(0，0)，(2，3)，(4，6)，(6，9)，(9，10)，(10，11)} q[2]=p[2](2，6)={(2，6)，(4，9)，(6，12)，(8，15)} p[1]={(0，0)，(2，6)，(4，9)，(6，12)，(8，15)} p[1]的最后的那个跳跃点(8,15)给出所求的最优值为m(1,c)=15。

算法复杂度分析 算法描述：P74—75 上述算法的主要计算量在于计算跳跃点集p[i](1≤i≤n)。由于q[i+1]=p[i+1](wi，vi)，故计算q[i+1]需要O(|p[i+1]|)计算时间。合并p[i+1]和q[i+1]并清除受控跳跃点也需要O(|p[i+1]|)计算时间。从跳跃点集p[i]的定义可以看出，p[i]中的跳跃点相应于xi,…,xn的0/1赋值。因此，p[i]中跳跃点个数不超过2n-i+1。由此可见，算法计算跳跃点集p[i]所花费的计算时间为 从而，改进后算法的计算时间复杂性为O(2n)。当所给物品的重量wi(1≤i≤n)是整数时，|p[i]|≤c+1，(1≤i≤n)。在这种情况下，改进后算法的计算时间复杂性为O(min{nc,2n})。

3.11 最优二叉搜索树 什么是二叉搜索树？ 在随机的情况下，二叉查找树的平均查找长度和logn是等数量级的。 若它的左子树不空，则左子树上所有节点的值均小于它的根节点的值； 若它的右子树不空，则右子树上所有节点的值均大于它的根节点的值； 它的左、右子树也分别为二叉排序树 在随机的情况下，二叉查找树的平均查找长度和logn是等数量级的。 45 12 53 3 37 24 100 61 90 78

基本概念 具体地，设S={x1,x2,...,xn}是一个有序集，且x1<x2<...<xn。表示有序集S的二叉搜索树利用二叉树的结点来存储有序集中的元素。它具有下述性质：存储于每个结点中的元素x大于其左子树中任一结点所存储的元素，小于其右子树中任一结点所存储的元素。二叉搜索树的叶结点是形如(xi，xi+1)的开区间。在表示S的二叉搜索树中搜索一个元素x，返回的结果有两种情形： 在二叉搜索树的内结点中找到x=xi。 在二叉搜索树的叶结点中确定x∈(xi，xi+1)。 设第一种情形中找到元素x=xi的概率为bi；在第二种情形中确定x∈(xi，xi+1)的概 率为ai。并约定x0=-∞，xn+1=+∞。显然有 (a0,b1,a1,...,bn,an)称为集合S的存取概率分布。 在表示S的二叉搜索树T中，设存储元素xi的结点深度为ci；存储叶结点(xj,xj+1)的 结点深度为dj，则 表示在二叉搜索树T中作一次搜索所需要的平均比较次数。P又称为二叉搜索树T的平均路长。在一般情况下，不同的二叉树的平均路长时不相同的。

二叉查找树的期望耗费示例

最优二叉搜索树 最优二叉搜索树问题是对于有序集S及其存取概率分布(a0,b1,a1,...,bn,an)，在所有表示有序集S的二叉搜索树中找出一棵具有最小平均路长的二叉搜索树。 有n个节点的二叉树的个数为：Ω(4n/n3/2)。穷举搜索法的时间复杂度为指数级。

最优子结构 二叉搜索树T的一棵含有结点xi,...,xj和叶结点(xi-1,xi),...,(xj,xj+1)的子树可以 看作是有序集{xi,...,xj}关于全集合{xi-1,xj+1}的一棵二叉搜索树，其存取概 率为下面的条件概率 其中，wij=ai-1+bi+...+bj+aj。 设Tij是有序集合{xi,...,xj}关于存取概率P的一棵最优二叉搜索树，其平均 路长为pij。Tij的根结点存储元素xm，其左右子树Tl和Tr的平均路长分别为 pl和pr。由于Tl和Tr中结点深度是他们在Tij中的结点深度减1，故我们有 由于Tl是关于集合{xi,...xm-1}的一棵二叉搜索树，故pl≥pi,m-1。若pl>pi,m-1，则用Ti.m-1替换Tl可得到平均路长比Tij更小的二叉搜索树。这与Tij是最优二叉搜索树矛盾。故Tij是一个最优二叉搜索树。同理可证也是一棵最优二叉搜索树。 因此最优二叉搜索树具有最优子结构性质。

计算最优值 最优二叉搜索树Tij的平均路长为pij，则所求的最优值为p1,n。由最优二叉搜索树问题的最优子结构性质可建立计算pij的递归式如下： 记wi,jpi,j为m(i,j)，则m(1,n)=w1,np1,n=p1,n为所求的最优值。计算m(i,j)的递归式为 注意到， 可以得到O(n2)的算法P77

构造最优解及算法复杂性与算法改进 构造最优解：略。 算法复杂性：S(n)=O(n3) 算法改进：P78 改进后的复杂性：T(n)=O(n2)，S(n)=O(n2)

3.12 动态规划加速原理 从前面的讨论中我们注意到许多动态规划问题具有类似的递归计算式。下面我们来讨论一种常见的递归计算式。 设w(i,j)∈R，1≤i<j≤n。且m(i,j)的递归计算式 为 最有二叉搜索树问题的动态递归式是上述递归式的特殊情形。

O(n3)计算时间算法 算法复杂性： T(n)=O(n3) S(n)=O(n2) void DynamicProgramming(int n, int **m, int **s, int **w) { for (int i=1;i<=n;i++){ m[i][i]=0; s[i][i]=0; } for (int r=1;r<n;r++) for (int i=1;i<=n-r+1;i++){ int j=i+r; w[i][j]=weight(i,j); m[i][j]=m[i+1][j]; s[i][j]=i; for (int k=i+1;k<j;k++){ int t=m[i][k]+m[k+1][j]; if (t<=m[i][j]) {m[i][j]=t; s[i][j]=k;} m[i][j]+=w[i][j]; 算法复杂性： 　　T(n)=O(n3) 　　S(n)=O(n2)

四边形不等式 四边形不等式： 推论： 综上所述，当w是满足四边形不等式的单调函数时，函数s(i,j)单调。于是 在上面计算m(i,j)的递归式中，当函数w(i,j)满足w(i,j)+w(i',j')≤w(i',j)+w(i,j')，i≤i'＜j≤j'时，称w满足四边形不等式。 当函数w(i,j)满足w(i',j)≤w(i,j')，i≤i'＜j≤j'时，称W关于区间包含关系单调。 例如，在最优二叉搜索树问题中，由ai≥0，0≤i≤n；bj≥0，1≤j≤n知，w(i,j)显然满足单调性。另一方面，w(i,j)+w(i',j')≤w(i',j)+w(i,j')，i≤i'＜j≤j' ，即w也满足四边形不等式。 对满足四边形不等式的单调函数w，可推知由递归式定义的函数也满足四边形不等式，即m(i,j)+m(i',j')≤m(i',j)+m(i,j')，i≤i'＜j≤j'。 这一性质可用数学归纳法证明(略)。 推论： 定义s(i,j)=max{k|m(i,j)=m(i,k-1)+m(k,j)+w(i,j)}由函数m(i,j)的四边形不等式性质可推出函数s(i,j)的单调性，即s(i,j)≤s(i,j+1)≤s(i+1,j+1)，i≤j。 推论证明(略)。 综上所述，当w是满足四边形不等式的单调函数时，函数s(i,j)单调。于是

加速算法 void SpeedDynamicProgramming(int n, int **m, int **s, int **w) { for (int i=1;i<=n;i++){ m[i][i]=0; s[i][i]=0; } for (int r=1;r<n;r++) for (int i=1;i<=n-r+1;i++){ int j=i+r, i1=s[i][j-1]>i?s[i][j-1]:i, j1=s[i+1][j]>i?s[i+1][j]:j-1; w[i][j]=weight(i,j); m[i][j]=m[i][i1]+m[i1+1][j]; s[i][j]=i1; for (int k=i1+1;k<j1;k++){ int t=m[i][k]+m[k+1][j]; if (t<=m[i][j]) {m[i][j]=t; s[i][j]=k;} m[i][j]+=w[i][j];

小结 动态规划算法的概念及其基本要素： 动态规划算法的设计步骤： 动态规划算法的主要范例： 最优子结构性质 重叠子问题性质 找出最优解的性质，并刻画其结构特征 递归定义最优值 以自底向上的方式计算最优值 根据计算最优值时得到的信息构造最优解 动态规划算法的主要范例： 矩阵连乘问题 最长公共子序列问题 最大子段和 凸多边形的最优三角剖分 多边形游戏 图像压缩 电路布线 流水作业调度 背包问题 最优二叉搜索数

习题 3-3、3-4、3-7