第4章动态规划

1、第四章 动态规划目录目录概述概述矩阵连乘问题矩阵连乘问题凸多边形最优三角剖分凸多边形最优三角剖分最长公共子序列问题最长公共子序列问题加工顺序问题加工顺序问题0-1背包问题背包问题最优二叉查找树最优二叉查找树教学目标理解动态规划的思想理解动态规划的思想掌握掌握动态规划、分治法及贪心法的异同动态规划、分治法及贪心法的异同掌握动态规划的掌握动态规划的基本要素基本要素掌握动态规划的掌握动态规划的设计步骤设计步骤通过实例学习，掌握动态规划通过实例学习，掌握动态规划设计的策略设计的策略学习动态规划的意义学习动态规划的意义动态规划属于动态规划属于运筹学范畴运筹学范畴。自问世以来，在自问世以来，在经济管理经济

2、管理、生产调度生产调度、工程技术和、工程技术和最最优控制优控制等方面得到了广泛的等方面得到了广泛的应用应用，例如，例如最短路线最短路线、库库存管理、资源分配、设备更新、排序、装载存管理、资源分配、设备更新、排序、装载等问题，等问题，用动态规划方法比用其它方法求解更为方便。用动态规划方法比用其它方法求解更为方便。虽然动态规划主要用于虽然动态规划主要用于求解求解以时间划分阶段以时间划分阶段的动态过的动态过程的优化问题程的优化问题，但是一些与时间无关的静态规划（如，但是一些与时间无关的静态规划（如线性规划、非线性规划），只要线性规划、非线性规划），只要人为地引进时间因素，人为地引进时间因素，把它视为

3、把它视为多阶段决策过程多阶段决策过程，也可以用动态规划方法方，也可以用动态规划方法方便地求解，因此研究该算法具有很强的实际意义。便地求解，因此研究该算法具有很强的实际意义。动态规划算法动态规划算法通常用于求解具有某种通常用于求解具有某种最优性质最优性质的问题的问题. 动态规划的基本思想动态规划的基本思想基本思想基本思想适合采用动态规划法求解的问题，经适合采用动态规划法求解的问题，经分解分解得到的各个子得到的各个子问题往往问题往往不是相互独立不是相互独立的。的。与分治法不同与分治法不同。在求解过程中，将已解决的在求解过程中，将已解决的子问题子问题的的解进行保存解进行保存，在需，在需要时可以轻松找

4、出。这样就要时可以轻松找出。这样就避免避免了大量的无意义的了大量的无意义的重复重复计算，计算，从而降低算法的时间复杂性。从而降低算法的时间复杂性。如何对已解决的子问题如何对已解决的子问题解的保存解的保存呢？通常呢？通常采用表的形式采用表的形式，即在实际求解过程中，一旦某个子问题被计算过，不管即在实际求解过程中，一旦某个子问题被计算过，不管该问题以后是否用得到，都该问题以后是否用得到，都将其计算结果填入该表，将其计算结果填入该表，需需要的时候就从表中找出该子问题的解，具体的动态规划要的时候就从表中找出该子问题的解，具体的动态规划算法多种多样，但它们具有相同的填表格式算法多种多样，但它们具有相同的

5、填表格式。（参考【例（参考【例4-1】）】）P82-83动态规划的解题步骤动态规划的解题步骤（1）分析最优解的性质分析最优解的性质，刻画最优解的结构特，刻画最优解的结构特征征考察是否适合采用动态规划法。考察是否适合采用动态规划法。（2）递归定义最优值递归定义最优值（即建立递归式或动态规（即建立递归式或动态规划方程）。划方程）。（3）以自底向上以自底向上的方式的方式计算出最优值计算出最优值，并记录，并记录相关信息。相关信息。（4）根据计算最优值时得到的信息，）根据计算最优值时得到的信息，构造出最构造出最优解。优解。动态规划的基本要素最优子结构性质最优子结构性质子问题重叠性质子问题重叠性质递归算法

6、求解问题时，递归算法求解问题时，每次产生的子问题并不每次产生的子问题并不总是新问题，总是新问题，有些子问题有些子问题出现多次出现多次，这种性质，这种性质称为子问题的称为子问题的重叠性质重叠性质。在应用动态规划时，对于重复出现的子问题，在应用动态规划时，对于重复出现的子问题，只需在第一次遇到时就加以解决，并把已解决只需在第一次遇到时就加以解决，并把已解决的的各个子问题的解储存在表中各个子问题的解储存在表中，便于以后遇到，便于以后遇到时时直接引用直接引用，从而不必重新求解，可大大提高，从而不必重新求解，可大大提高解题的效率。解题的效率。自底向上的求解自底向上的求解方式方式矩阵连乘矩阵连乘问题描述问

7、题描述给定给定n个矩阵个矩阵A1,A2,A3,An，其中，其中Ai与与Ai+1，(i=1,2,3, ,n-1)是可乘的。用加括号的方法表是可乘的。用加括号的方法表示示矩阵连乘的次序矩阵连乘的次序，不同加括号的方法所对应，不同加括号的方法所对应的计算次序是不同的。的计算次序是不同的。以【例以【例4-2】P84-85矩阵连乘，乘法次数：矩阵连乘，乘法次数：A1,A2,A3的阶分别为的阶分别为10100，1005，550(A1A2)A3)： 10100 5+ 10 5 50=7500个乘法个乘法(A1(A2A3)： 1005 50+ 10 100 50=75000个乘法个乘法n个矩阵连乘的计算量个矩

8、阵连乘的计算量最少的运算次序最少的运算次序？矩阵连乘矩阵连乘最优子结构性质分析最优子结构性质分析若若n个矩阵连乘的个矩阵连乘的最优计算次序最优计算次序为为(A1A2Ak)(Ak+1Ak+2An)，则，则各部分各部分连乘的计连乘的计算次序算次序也是最优的也是最优的。AiAi+1Aj矩阵连乘，设矩阵矩阵连乘，设矩阵Am的的行数行数为为pm，列数列数为为qm(m=i,i+1,j)且相邻矩阵是可乘的且相邻矩阵是可乘的(即即qm=pm+1)。设设AiAi+1Aj的最佳计算次序所对应的的最佳计算次序所对应的乘法次数乘法次数为为mij，则，则AiAi+1Ak的最佳计算次序对应的的最佳计算次序对应的乘法次数为

9、乘法次数为mik，Ak+1Ak+2Aj的最佳计算次的最佳计算次序对应的乘法次数为序对应的乘法次数为mk+1j。建立最优值的递归关系式 当当i=j时，只有一个矩阵时，只有一个矩阵,故故mii=0；当当ij时，将时，将n个矩阵的行数和列数存储在数组个矩阵的行数和列数存储在数组P0:n（因为（因为qm=pm+1 ）,则：则：jiPPP1jmkmikminji0mijjk1ijki算法设计算法设计步骤步骤1：确定合适的数据结构。采用数组：确定合适的数据结构。采用数组m存放各个子问题的存放各个子问题的最优值最优值，数组，数组P存放存放n个矩阵的行数和列数个矩阵的行数和列数，数组，数组s存放各个子存放各个

10、子问题的最优决策问题的最优决策若若s(i,j)=k，则最优计算次序为，则最优计算次序为(AiAk)(Ak+1Aj)。ikjAikAk+1js(i,j)=k算法设计算法设计步骤步骤2：初始化。令：初始化。令mii=0，sii0，其中，其中i=1,2,n；步骤步骤3：循环阶段。：循环阶段。 3-1：按照递归关系式计算：按照递归关系式计算2个个矩阵矩阵AiAi+1相乘时的相乘时的最优值最优值并将并将其其存入存入mii+1，同时将，同时将最优决策记入最优决策记入sii+1，i=1,2,n-1； 3-2：按照递归关系式计算：按照递归关系式计算3个个矩阵矩阵AiAi+1Ai+2相乘时的相乘时的最优值最优值

11、并将其并将其存入存入mii+2，同时将，同时将最优决策记入最优决策记入sii+2，i=1,2,n-2；依此类推，直到；依此类推，直到 3-(n-1)：按照递归关系式计算：按照递归关系式计算n个个矩阵矩阵A1A2An相乘时的最优相乘时的最优值并将其存入值并将其存入m1n，同时将，同时将最优决策记入最优决策记入s1n。至此，至此，m1n即为原问题的最优值即为原问题的最优值。步骤步骤4：根据数组根据数组s记录的最优决策信息来记录的最优决策信息来构造最优解构造最优解。 4-1：递归构造：递归构造A1As1n最优解，直到包含一个矩阵结束；最优解，直到包含一个矩阵结束； 4-2：递归构造：递归构造As1n

12、+1An最优解，直到包含一个矩阵结束；最优解，直到包含一个矩阵结束； 4-3：将步骤：将步骤4-1和步骤和步骤4-2递归的结果加括号。递归的结果加括号。 构造实例P86-87求矩阵求矩阵A1（32）、）、A2（25）、）、A3（510）、）、A4（102）和和A5（23）连乘的最佳计算次序。则）连乘的最佳计算次序。则P=3,2,5,10,2,3例：例：一、一、计算计算两个两个矩阵相乘矩阵相乘AiAi+1的最优值，的最优值，i=1,4; j=2,5当当i=1时时, j=2; k=1. m(1,2)=m(1,1)+m(2,2)+P(0)P(1)P(2)=325=30, s(1,2)=1同理，同理，

13、m(2,3)= 2510=100, s(2,3)=2;m(3,4)=5102=100, s(3,4)=3 ;m(4,5)=1023=60, s(4,5)=4。jiPPP1jmkmikminji0mijjk1ijkis(i,j)=k构造实例P86-87求矩阵求矩阵A1（32）、）、A2（25）、）、A3（510）、）、A4（102）和和A5（23）连乘的最佳计算次序。则）连乘的最佳计算次序。则P=3,2,5,10,2,3二、二、计算三个矩阵相乘计算三个矩阵相乘AiAi+1Ai+2的最优值，的最优值，i=1,2,3; j=3,4,5 当当i=1时时, j=3; k=12 m(1,3)=minm(1

14、,1)+m(2,3)+P(0)P(1)P(3);m(1,2)+m(3,3)+P(0)P(2)P(3)=min160,180=160, s(1,3)=1;同理，同理，m(2,4)=min120,140 =120, s(2,4)=2;(i=2,j=4,k=23)m(3,5)=130, s(3,5)=4 ;(i=3,j=5,k=34)三、三、计算四个矩阵相乘的最优值，计算四个矩阵相乘的最优值，i=1,2; j=4,5 当当i=1时时, j=4; k=13 改错：改错：P87，（，（4）将）将3改为改为4jiPPP1jmkmikminji0mijjk1ijkis(i,j)=kM(i,j)的计算次序1

15、2 3 4 n1234.nij0m12 m23 mn-1 n m1n-1 m2n m1n构造实例P86-87求矩阵求矩阵A1（32）、）、A2（25）、）、A3（510）、）、A4（102）和和A5（23）连乘的最佳计算次序。）连乘的最佳计算次序。 表4-6 实例最优值最优值mij 表4-7 实例最优决策最优决策sijmijA1A2A3A4A5sijA1A2A3A4A5A1030160132150A101111A20100120132A20224A30100130A3034A4060A404A50A50递归构造最优解算法设计与分析P88-89算法设计算法设计语句语句int t=mik+mk+1

16、j+pi-1*pk*pj; 为算为算法法MatrixChain的基本语句，的基本语句，最坏情况下最坏情况下该语句的执该语句的执行次数为行次数为O(n3)，故该算法的最坏时间复杂性为，故该算法的最坏时间复杂性为O(n3)。构造构造最优解最优解s(i,j)的的Traceback算法的时间主要取决算法的时间主要取决于于递归递归。最坏情况下时间复杂性的递归式为：。最坏情况下时间复杂性的递归式为： 解此递归式得解此递归式得T(n)=O(n)。1nO(1)1)T(n1nO(1)T(n)凸多边形最优三角剖分凸多边形最优三角剖分 基本概念基本概念一个简单一个简单多边形多边形及其内部构成一个及其内部构成一个闭凸

17、集闭凸集时，称时，称该简单多边形为该简单多边形为凸多边形凸多边形 。凸多边形的凸多边形的不相邻不相邻的两个顶点连接的直线段称为的两个顶点连接的直线段称为凸多边形的凸多边形的弦弦 。凸多凸多边形边形内部外部边弦凸多边形最优三角剖分凸多边形最优三角剖分 基本概念基本概念凸多边形的凸多边形的三角剖分三角剖分指将一个凸多边形分割成指将一个凸多边形分割成互互不相交不相交的三角形的的三角形的弦的集合弦的集合 。不唯一。不唯一给定凸多边形及定义在给定凸多边形及定义在边、弦构成的三角形边、弦构成的三角形的的权权函数函数，最优三角剖分最优三角剖分即不同剖分方法所划分的各即不同剖分方法所划分的各三角形上三角形上权

18、函数之和权函数之和最小最小的三角剖分。的三角剖分。三角三角剖分剖分凸多边形最优三角剖分凸多边形最优三角剖分 基本概念基本概念三角形三角形v vi iv vj jv vk k上的上的定义：定义：w(v vi i ,v,vj j ,v,vk k)=| v vi i v vj j |+| v vj j v vk k |+|v vk k v vi i|min其中其中| v vj j v vk k |表示边（表示边（ v vj j ，v vk k ）的）的长度长度。凸多边形最优三角剖分问题：给定一个凸凸多边形最优三角剖分问题：给定一个凸n n（3）边形）边形P(vP(v0 0,v,v1 1,v,vn-1

19、n-1) )及及权函数权函数w，找出找出一个最优三角剖分一个最优三角剖分 。类似于表达式的加括号运算，对应一棵二元树。类似于表达式的加括号运算，对应一棵二元树。三角剖分的结构将图将图4-6中的中的叶子结点叶子结点vivi+1与矩阵与矩阵Ai+1(i=0,1,2,3,4)对应对应，则图，则图4-6和图和图4-4所示的所示的二叉树二叉树是一样的。是一样的。因此，因此，n+1边形的三角剖分与边形的三角剖分与n个矩阵连乘的计算次序是一一对应的。可见，个矩阵连乘的计算次序是一一对应的。可见，凸多边形凸多边形最优剖分最优剖分问题的解决方法和问题的解决方法和矩阵连乘矩阵连乘问题相似。问题相似。类比类比根根(

20、闭合边闭合边)A1A3A4A5A2(A1A2)(A3(A4A5)叶（边）叶（边）弦（内结点）弦（内结点）最优子结构性质分析设设v0vkvn是将是将n+1边形边形P=v0,v1, ,vn分成分成三部分三部分v0,v1,vk、vk,vk+1,vn和和v0,vk,vn的的最佳剖分最佳剖分方法，那么凸多边形方法，那么凸多边形v0,v1,vk的剖分一定是的剖分一定是最优的最优的，vk,vk+1,vn的剖分也一的剖分也一定是定是最优的最优的。设设v0,v1, ,vn三角剖分的三角剖分的权函数之和为权函数之和为c，v0,v1,vk三角三角剖分的剖分的权函数之和为权函数之和为a，vk,vk+1,vn三角剖分的

21、三角剖分的权函数之和权函数之和为为b，三角形，三角形v0vkvn的权函数为的权函数为w(v0vkvn)，则则c=a+b+ w(v0vkvn)。v0vkvnabc最优子结构性质分析如果如果c是最小是最小的，则的，则一定包含一定包含a和和b都是最小都是最小的。的。如果如果a不是不是最小的，则它所对应的最小的，则它所对应的v0,v1,vk的三角剖分就不的三角剖分就不是最优的。是最优的。那么，对于凸多边形那么，对于凸多边形v0,v1,vk来说，肯定来说，肯定存在最优存在最优的三角的三角剖分，设剖分，设v0,v1,vk的最优三角剖分对应的权函数之和为的最优三角剖分对应的权函数之和为a (aa)，用，用a

22、代替代替a得到得到c=a+b+w(v0vkvn)，则，则cc，这说这说明明c对应的对应的v0,v1, ,vn的三角剖分不是最优的，的三角剖分不是最优的，产生矛盾产生矛盾。故故a一定是最小的。一定是最小的。同理，同理，b也是最小的。也是最小的。最优子结构性质得证。最优子结构性质得证。建立最优值的递归关系式设设mij表示表示vi-1vivj最优三角剖分最优三角剖分权函数之权函数之和和，i=j时表示一条时表示一条直线段直线段，将其看作退化多，将其看作退化多边形，其边形，其权函数为权函数为0。则。则ji)vvw(v1jmkmikminji0mijjk1ijki算法设计与分析P91-92最长公共子序列问

23、题基本概念基本概念（1）子序列子序列给定序列给定序列 X=x1, x2, , xn、Z=z1, z2, , zk，若，若Z是是X的子的子序列序列，当且仅当存在一个，当且仅当存在一个严格递增的下标序列严格递增的下标序列 i1, i2, , ik，对，对j1, 2, , k有有例：例：X=A，B，C，B，D，A，B 1， 2，3，4， 5，6， 7子序列：子序列： A，B、B，B，A、A，B，C，D，A i1k: 1，2 2，4，6 1，2，3， 5，6 j: 1，2 1，2，3 1，2，3，4，5jjizx最长公共子序列问题基本概念基本概念（2）公共子序列）公共子序列给定序列给定序列X和和Y，序

24、列，序列Z是是X的子序列，也是的子序列，也是Y的子序的子序列，则称列，则称Z是是X和和Y的的公共子序列公共子序列。例：例：X=ABCBDAB,Y=ACBEDB的公共子序列：的公共子序列：Z=AB,CBD,ACBDB（3）最长公共子序列）最长公共子序列包含元素最多的公共子序列即为包含元素最多的公共子序列即为最长公共子序列最长公共子序列。上例：上例：ACBDB 最长公共子序列最优解性质设设 序列序列 和和 的最长公共子序列。的最长公共子序列。 kkzzzZ,21,1mmxxX,1nnyyY1,mkmnkmnZXyxzxY若则是和的最长公共子序列1,nkmnkmnZxyyzXY若则是和的最长公共子序

25、列111,kmnkmnZYxyXz1k-1若则=z, ,z 是和的最长公共子序列建立最优值的递归关系式设设cij表示序列表示序列Xi和和Yj的的最长公共子序列最长公共子序列的的长度长度。则：。则：1),(jib000cijci 1j 1 1,0;maxcij 1,ci 1j,0;ijijiji ji jxyxy或2),(jib3),(jib( ,)1:ijb ijxy表 示一 个找 到公 共 字 符算法设计步骤步骤1：确定合适的数据结构。采用数组：确定合适的数据结构。采用数组c来存放各个子来存放各个子问题的问题的最优值最优值，数组，数组b来存放各个子问题最优值的来存放各个子问题最优值的来源来源

26、。数组数组x1:m和和y1:n分别存放分别存放X序列和序列和Y序列；序列；步骤步骤2：初始化。：初始化。令令ci00，c0j=0，其中，其中0im，0jn；步骤步骤3：循环阶段。根据递归关系式，确定序列：循环阶段。根据递归关系式，确定序列Xi和和Yj的的最长公共子最长公共子序列长度序列长度；1im3-1：i=1时，求出时，求出c1j，同时记录，同时记录b1j，1jn；3-2：i=2时，求出时，求出c2j，同时记录，同时记录b2j，1jn；依此类推，直到依此类推，直到3-m: i=m时，求出时，求出cmj，同时记录，同时记录bmj，1jn。此。此时，时，cmn便是序列便是序列X和和Y的最长公共子

27、序列的最长公共子序列长度；长度；算法设计步骤步骤4：根据二维数组：根据二维数组b记录的相关信息以记录的相关信息以自底向上自底向上的方的方式来式来构造最优解构造最优解；4-1：初始时，初始时，i=m，j=n；4-2：如果：如果bij=1，则输出，则输出xi，同时递推到，同时递推到bi-1j-1; 如果如果bij=2，则递推到，则递推到bij-1; 如果如果bij=3，则递推到，则递推到bi-1j；重复执行步骤重复执行步骤4-2，直到直到 i=0或或j=0，此时就，此时就可得到序列可得到序列X和和Y的最长公共子序列。的最长公共子序列。实例构造【例【例4-6】给定序列】给定序列X=A, B, C,

28、B, D, A, B和和Y=B, D, C, A, B, A，求它们的最长公共子序列。，求它们的最长公共子序列。 （1）m=7，n=6，将停止条件填入数组将停止条件填入数组c中，中，即即ci00，c0j=0，其中其中0im，0jn。（2）当）当i=1时，时，X1=A，最后一个字符为，最后一个字符为A；Yj的规模从的规模从1逐步放大到逐步放大到6，其最后一个字符，其最后一个字符分别为分别为B、D、C、A、B、A；依此类推，依此类推，直到直到i=7。 找到找到X和和Y的的最长公共子序列的最长公共子序列的长度长度。 b(i,j)=1:b(i,j)=2:b(i,j)=3: c(i-1,j-1)源于 c

29、(i,j-1) c(i-1,j)i=1时（j=1:n）; j=4, c(1,4)=1,b(1,4)=1;j=5, c(1,5)=1,b(1,5)=1 j=6, c(1,6)=1,b(1,6)=1.000cijci 1j 1 1,0;maxcij 1,ci 1j,0;ijijiji ji jxyxy或从从i=7，j=6处向前递推处向前递推 ：b(7,6)=3推到推到b(6,6)=1得得X(6)=A；推；推到到b(5,5)=3推到推到b(4,5)=1得得X(4)=B，找到找到X和和Y的的最长公共子序列为最长公共子序列为B,C,B,A b(i,j)=1:b(i,j)=2:b(i,j)=3: b(i-

30、1,j-1)推出 b(i,j-1) b(i-1,j)算法设计与分析P95-961、构造、构造c(i,j)和和b(i,j) O(nm)2、求、求最长公共子序列最长公共子序列 O(max(m,n)加工顺序问题流水作业调度流水作业调度问题描述问题描述设有设有n个工件需要在机器个工件需要在机器M1和和M2上加工，每个工件的加上加工，每个工件的加工顺序都是工顺序都是先在先在M1上上加工，然加工，然后在后在M2上上加工。加工。t1j，t2j分别表示分别表示工件工件j在在M1，M2上所需的加工时间上所需的加工时间(j=1,2,n)。问应如何在两机器上问应如何在两机器上安排生产安排生产（确定这确定这n个工件的

31、最佳个工件的最佳加工顺序加工顺序），使得第一个工件从在），使得第一个工件从在M1上加工开始到最后上加工开始到最后一个工件在一个工件在M2上加工完上加工完所需的总加工时间最短所需的总加工时间最短？分析：最佳方案是分析：最佳方案是M1没有空闲时间没有空闲时间，且，且M2空闲时空闲时间最短间最短。通常，通常，M2有有空闲和积压空闲和积压两种情况两种情况；M1等待等待时间时间t后才可开始加工。后才可开始加工。最优子结构性质分析将将n个工件的集合看作个工件的集合看作N=1,2,n，设，设P是给定是给定n个工件的个工件的一个最优加工顺序方案一个最优加工顺序方案，P(i)是该调度方案的第是该调度方案的第i个

32、要调度的个要调度的工件工件(i=1,2,n)。从集合从集合S（ ）中的第一个工件）中的第一个工件开始在机器开始在机器M1上加工到最上加工到最后一个工件在机器后一个工件在机器M2上加工结束时上加工结束时所耗的时间为所耗的时间为T(S，t)。集合集合S的最优加工顺序中的最优加工顺序中要加工的工件为要加工的工件为i时时，那么，那么，经过经过t1i的时间，的时间，M1开始加工集合开始加工集合S-i中的工件时，中的工件时，第二台机器第二台机器M2需要需要t2i时间才能空闲下来时间才能空闲下来，这种情况下机器，这种情况下机器M2加工完加工完S-i中中的工件所需的时间为的工件所需的时间为T(S-i，t)，其

33、中，即，其中，即t=t2i+maxt-t1i，0，其中，其中，t为为M2等待时间，等待时间，t为为M1等待时间。等待时间。NS S-it1iM1M2t2itt1i-tttt1i时，t=t2i+t-t1i则加工则加工S集合中工件所需集合中工件所需最小时间最小时间为：为：T(S,t)= t1i +T(S-i,t2i+maxt- t1i,0) （4-1）从式（从式（4-1）可以看出，如果）可以看出，如果T(S,t)是最小是最小的，那么肯定包含的，那么肯定包含T(S-i,t2i +maxt- t1i,0)也是最小的。也是最小的。整体最优一定包含子问题最优。整体最优一定包含子问题最优。建立最优值的递归关

34、系式设设T(S，t)表示从集合表示从集合S中的第一个中的第一个工件开始工件开始在机器在机器M1上加工上加工到最后一个到最后一个工件在机器工件在机器M2上加工结束上加工结束时所耗的时所耗的最短时间最短时间，则：，则：当当S为空集为空集时，耗时为时，耗时为M2闲下来所需要的时闲下来所需要的时间，即间，即T(S，t)=t；当当S不为空集不为空集时，时，,0)tmaxtti,T(Stmint)T(S,1i2i1iSiJohnson-Bellmans Rule（P97） 如果如果加工工件加工工件i和和j满足满足min t1j，t2i min t1i，t2j不等式，称加工工件不等式，称加工工件i和和j满足

35、满足Johnson Bellmans Rule。设设最优加工顺序为最优加工顺序为P，则，则P的任意的任意相邻相邻的两个加工工的两个加工工件件P(i)和和P(i+1)满足：满足： ，1in-1进一步可以证明，最优进一步可以证明，最优加工顺序的第加工顺序的第i个和第个和第j个个要要加工的工件，加工的工件，如果如果ij，则，则即满足即满足Johnson Bellmans Rule的加工顺序方案的加工顺序方案为为最优方案最优方案。t ,mintt ,mint1)2P(i1P(i)2P(i)1)1P(i1P( )2P( )1P( )2jPi(ij)mint,tmint,t算法设计算法设计步骤步骤1：令：

36、令N1=i|t1it2i，N2=i|t1it2i；步骤步骤2：将：将N1中工件按中工件按t1i非减序（非减序（）排序）排序；将将N2中工件按中工件按t2i非增序（非增序（）排序；）排序；步骤步骤3：N1中工件接中工件接N2中工件，即中工件，即N1N2就是就是所求的满足所求的满足Johnson Bellmans Rule的最的最优加工顺序优加工顺序 t1iM1t2iM2N1t2iM2t1iM1N2例：例：P98（7个工件加工时间）个工件加工时间）M1M212810615718263 1029431iittStep1:N1=i|t1it2i=1,4,6N2=i|t1it2i=2,3,5,7N1对应

37、的工件加工时间对应的工件加工时间:t1i=(3,12,9)N2对应的工件加工时间对应的工件加工时间: t2i=(2,6,3,4)Step2: N1增序增序=1,6,4，N2减序减序=3,7,5,2Step3: N1N2=1,6,4,3,7,5,2i: 1 2 3 4 5 6 7算法分析算法分析P99显然，显然，FlowShop算法的时间复杂性取算法的时间复杂性取决于决于Sort函数函数的执行时间，由于的执行时间，由于Sort函函数 的 执 行 时 间 为数 的 执 行 时 间 为 O ( n l o g n ) ， 因 此， 因 此F l o w S h o p 算 法 的 时 间 复 杂 性

38、 为算 法 的 时 间 复 杂 性 为O(nlogn)。0-1背包问题问题描述（问题描述（资本预算、货物装载、存储分配、投资策略资本预算、货物装载、存储分配、投资策略）0-1背包问题可描述为：背包问题可描述为：n个物品和个物品和1个背包个背包。对。对物品物品i，其，其价价值为值为vi，重量为，重量为wi，背包的容量为，背包的容量为W。如何选物品装入背包，使背包所装入物品的如何选物品装入背包，使背包所装入物品的总价值最大总价值最大？约束条件：约束条件： （4-7）目标函数：目标函数： （4-8）问题归结为寻找一个满足问题归结为寻找一个满足约束条件（约束条件（4-7），），并使并使目标函数目标函数

39、（4-8）达到最大的达到最大的解向量解向量X=(x1, x2, xn)。xi=1：物品：物品i装入背包装入背包； xi=0：物品：物品i未装入背包未装入背包niii=1i0,w xWx,(1i1n) niii=1maxv x最优子结构性质分析假设（假设（x1, x2, xn)是所给是所给0-1背包问题的一背包问题的一个最优解，则（个最优解，则（x2, xn）是下面相应）是下面相应子问子问题的一个最优解：题的一个最优解：约束条件：约束条件： 目标函数：目标函数： nii1=21iiw xW-w xx0,1,in()2 i=2niimaxv x运用反证法来证明运用反证法来证明建立最优值的递归关系式

40、令令Cij = 表示表示子问题子问题 的的最优解：最优解：装入装入背包背包的总重的总重j的的i个物品个物品价值价值。则最优解递归定义：则最优解递归定义： C0j=Ci0=0 （4-10)iiiiCi-1jjw maxCi-1j,Ci-1j-w +v jwC ijikkk=1maxv x（4-11)ikkk=1x0,1,1kwjxki第i个没装入算法设计：求装入背包的最大价值步骤步骤1、设计算法所需的、设计算法所需的数据结构数据结构：采用数组采用数组wn存放存放n个物品的个物品的重量重量；数组数组vn存放存放n个物品的个物品的价值价值，背包容量为背包容量为W，数组数组Cn+1W+1存放存放每一次

41、迭代的执行结果每一次迭代的执行结果；数组数组xn 存储装入背包的物品存储装入背包的物品状态状态(0或或1)；步骤步骤2、初始化。按式、初始化。按式(4-10)初始化数组初始化数组C： C0j=Ci0=0算法设计：求装入背包的最大价值步骤步骤3、循环阶段。按式（、循环阶段。按式（4-11）确定）确定前前i个个物品能物品能够装入背包的情况下得到的够装入背包的情况下得到的最优值最优值；步骤步骤3-1：i=1时，求出时，求出C1j，1jW；步骤步骤3-2：i=2时，求出时，求出C2j，1jW；依此类推，直到依此类推，直到步骤步骤3-n：i=n时，求出时，求出CnW。此时，此时，CnW便是最优值便是最优

42、值；iiiiCi-1jj Cn-1W，表明第，表明第n个物品被个物品被装入背包装入背包，则，则xn=1，前前n-1个物品被个物品被装入装入容量为容量为W-wn的背包中；的背包中；否则，否则，第第n个物品个物品没有被装入没有被装入背包，则背包，则xn=0，前前n-1个物品被装个物品被装入容量为入容量为W的背包中。的背包中。依此类推，依此类推，直到确定第直到确定第1个物品个物品是否被装入背包中为止。由此，是否被装入背包中为止。由此，得到下面关系式：得到下面关系式： （4-12） 按照式（按照式（4-12），从），从CnW的值的值向前倒推向前倒推，即，即j初始为初始为W，i初初始为始为n，即可确定装

43、入背包的具体物品。即可确定装入背包的具体物品。1jCiCijwjj , 1x1jCiCijjj ,0 xiii当当构造实例【例【例4-8】有】有5个物品，其重量分别为个物品，其重量分别为2,2,6,5,4，价值分别为，价值分别为6,3,5,4,6。背包容量为。背包容量为10，物品不可分割，求装入背包的物，物品不可分割，求装入背包的物品和获得的最大价值。品和获得的最大价值。行行i表示物品表示物品，列列j表示背包容量表示背包容量，表中数据表示表中数据表示Cij w=(2,2,6,5,4)；v=(6,3,5,4,6)；W=10。012345678910000000000000100666666666

44、200669999999300669999111114400669991011131450066991212151515初始化初始化： C0j=Ci0=0 构造实例P102-104【例【例4-8】 w=(2,2,6,5,4)；v=(6,3,5,4,6)；W=10。 行行i表示物表示物品品，列列j表示背包容量表示背包容量，表中数据表示表中数据表示Cij 。iiiiCi-1jjw maxCi-1j,Ci-1j-w +v jwC ij012345678910000000000000100666666666200669999999300669999111114400669991011131450066

45、991212151515i=1时，j=1w1，c(1,1)=c(0,1)=0j=210：c(1,2)=max0,0+v1=6i=2时，j=1Ci-1j，说明第，说明第i个物品被个物品被装入装入背包，则背包，则xi =1，j=j-wi。iiiiCi-1jjC410=14，说明物品，说明物品5被装入被装入了背包，因此了背包，因此x5=1，且且更新更新j=j-w5=10-4=6。iiiiCi-1jjC16=6，说明物品，说明物品2被装入了背包，因此被装入了背包，因此x2=1，且，且更新更新j=j-w2=6-2=4。由于由于C1j=C14=6C04=0，说明物品，说明物品1被装入了背包，因此被装入了背

46、包，因此x1=1，且更新，且更新j=j-w1=4-2=2。最终求得装入背包的物品最终求得装入背包的物品最优解最优解X=(x1, x2, xn)=(1,1,0,0,1)。012345678910000000000000100666666666200669999999300669999111114400669991011131450066991212151515即即w=(2,2,6,5,4)；v=(6,3,5,4,6)；W=10j=6算法分析P104-105在算法在算法KnapSack中，第中，第3个循环是两层嵌套的个循环是两层嵌套的for循环，为此，可选定语句循环，为此，可选定语句if(j2n时

47、，算法需要时，算法需要O(n2n)的计算时间。的计算时间。问题：怎样改进？克服这两大缺点。问题：怎样改进？克服这两大缺点。 改进算法(自学)改进思路改进思路由由Cij的递归式（的递归式（4-11）容易证明：在一般情）容易证明：在一般情况下，对每一个确定的况下，对每一个确定的i(1in)，函数，函数Cij是关是关于变量于变量j的阶梯状的阶梯状单调不减函数单调不减函数（事实上，计算（事实上，计算Cij的递归式在变量的递归式在变量j是连续变量，即为实数时是连续变量，即为实数时仍成立）。仍成立）。跳跃点是这一类函数的描述特征。在一般情况下，跳跃点是这一类函数的描述特征。在一般情况下，函数函数Cij由其

48、全部跳跃点唯一确定。由其全部跳跃点唯一确定。 改进步骤（a）对每一个确定的）对每一个确定的i，用一个表，用一个表pi来来存储函数存储函数Cij的全的全部跳跃点。部跳跃点。对每一个确定的实数对每一个确定的实数j，可以通过查找，可以通过查找pi来确定来确定函数函数Cij的值。的值。pi中的全部跳跃点中的全部跳跃点(j，Cij)按按j升序排列升序排列。由于函数由于函数Cij是关于是关于j的阶梯状单调不减函数，故的阶梯状单调不减函数，故pi中全中全部跳跃点的部跳跃点的Cij值也是递增排列的值也是递增排列的。（b）pi可通过计算可通过计算pi-1得到。得到。（c）清除受控点。）清除受控点。（d）由此可得

49、，在递归地由）由此可得，在递归地由pi-1计算计算pi时，可先由时，可先由pi-1计算出计算出qi-1，然后合并，然后合并pi-1和和qi-1，并清除其中的受控，并清除其中的受控跳跃点得到跳跃点得到pi。改进后算法的计算时间复杂性为改进后算法的计算时间复杂性为O(minnW，2n ) 最优二叉查找树定义定义若有序序列若有序序列S=s1,sn 对应二叉树对应二叉树T满足满足：T中中每个结点的值均每个结点的值均左子树左子树所有结点的值，所有结点的值，右子树右子树所有结点的值，称所有结点的值，称T为二叉查找树。为二叉查找树。对于每个关键字对于每个关键字si，相应的，相应的查找概率为查找概率为pi；在

50、；在T中中设置设置n+1个虚个虚叶叶结点结点e0,e1,en，相应的，相应的查找概率查找概率为为qi；且；且e0sn, ei(si,si+1),i=1,n。叶小大T叶被查元素的取值范围最优二叉查找树每次查找要么每次查找要么成功成功（找到找到si），要么），要么失败失败（找到找到ei），），故有：故有：最优二叉查找树是在所有表示有序序列最优二叉查找树是在所有表示有序序列S的二叉的二叉查找树中，具有查找树中，具有平均比较次数最小平均比较次数最小的二叉查找树。的二叉查找树。注意：在注意：在查找概率不等的情况下查找概率不等的情况下，最优二叉树并，最优二叉树并不一定是高度最小的二叉查找树不一定是高度最小

51、的二叉查找树。niiniiqp011S对应的二叉查找树对应的二叉查找树T不唯一不唯一，因插入顺序而异。，因插入顺序而异。平均比较次数平均比较次数10(1)nniijjijCp cq d不同二叉不同二叉查找树查找树T的效率的效率由平均比较次数决定由平均比较次数决定，设实，设实结点结点si的深度的深度为为ci(1in) ，叶结点，叶结点ej的深度为的深度为dj,则则平均比较次数为：平均比较次数为：最优二叉查找树：平均比较次数最少的最优二叉查找树：平均比较次数最少的。在。在pi不等的不等的情况下，最优二叉查找树情况下，最优二叉查找树不一定是高度最小的不一定是高度最小的二叉查二叉查找树，尽量将找树，尽

52、量将pi大的结点靠近根；但与大的结点靠近根；但与Huffiman不同。不同。P109例例4-10最优子结构性质分析将由实结点将由实结点s1,s2,sn和虚结点和虚结点e0,e1, ,en构成构成的二叉查找树记为的二叉查找树记为T(1，n)。设定元素设定元素sk作为该树的根结点作为该树的根结点，1kn。则二叉查找树则二叉查找树T(1，n)的的左子树左子树由实结点由实结点s1,sk-1和虚结点和虚结点e0,ek-1组成，记为组成，记为T(1，k-1)，而而右子树右子树由实结点由实结点sk+1,sn和虚结点和虚结点ek,en组成，组成，记为记为T(k+1，n)。实实s1,s2,sk-1实实Sk+1,

53、sn虚虚e0,e1,ek-1虚虚ek+1,enskT(1,k-1)T(k+1,n)T(1,n)最优子结构性质分析如果如果T(1,n)是是最优最优二叉查找树，则左子树二叉查找树，则左子树T(1,k-1)和和右子树右子树T(k+1,n)也是最优也是最优二叉查找树。二叉查找树。证明：证明：如若不然，假设如若不然，假设T (k+1，n)是比是比T(k+1，n)更更优的二叉查找树，则优的二叉查找树，则T (k+1，n)的平均比较次数小的平均比较次数小于于T(k+1，n)的平均比较次数，从而由的平均比较次数，从而由T(1，k-1)、sk和和T (k+1，n)构成的二叉查找树构成的二叉查找树T (1，n)的

54、平均的平均比较次数小于比较次数小于T(1，n)的平均比较次数，这与的平均比较次数，这与T(1，n)是最优二叉树的前提相矛盾。是最优二叉树的前提相矛盾。因此，最优二叉查找树具有最优子结构性质得证。因此，最优二叉查找树具有最优子结构性质得证。建立最优值的递归关系式 (4-20) 当ij时，上式中的k在i,i+1,j中是最优值，即： (4-21)其中 (4-22)初始时： C(i,i-1)=0; wi(i-1)=qi-1 ，1in (4-23)式（4-21）和（）和（4-23）即为建立的最优值递归定义式。）即为建立的最优值递归定义式。i k jC(i,j)w(i,j)minC(i,k 1)C(k1,

55、j) jjqp1)jw(i,j)w(i,ijwjkCkiCjiC), 1() 1,(),(由第i个结点到第j个结点构成的T(i,j)的平均比较次数。算法设计算法设计(构造最优二叉查找树构造最优二叉查找树)步骤步骤1：设计合适的数据结构。：设计合适的数据结构。设有序序列设有序序列S=s1,sn，数组，数组sn存储序列存储序列S中的元素；中的元素；数组数组pn存储序列存储序列S中相应元素的中相应元素的查找概率查找概率；二维数组二维数组Cn+1n+1，其中，其中Cij表示二叉查找树表示二叉查找树T(i,j)的平均的平均比较次数；比较次数；二维数组二维数组Rn+1n+1，其中，其中Rij表示二叉查找树

56、表示二叉查找树T(i,j)中作为中作为根结点根结点的元素在序列的元素在序列S中中的位置。的位置。数组数组qn存储虚结点存储虚结点e0,e1,en的的查找概率查找概率。为了提高效率，不是每次计算为了提高效率，不是每次计算C(i,j)时都计算时都计算wij的值，而是把的值，而是把这些值存储在二维数组这些值存储在二维数组Wij中；中； 步骤步骤2：初始化。设置：初始化。设置Cii-1=0；Wii-1=qi-1；算法设计步骤步骤3：循环阶段。采用：循环阶段。采用自底向上自底向上的方式逐步构造最优二叉查的方式逐步构造最优二叉查找树；找树；步骤步骤3-1：字符集：字符集规模为规模为1的时候，即的时候，即Sij=si，i=1,2, ,n且且j=i，显然这种，显然这种规模的子问题有规模的子问题有n个个，即首先要构造出，即首先要构造出n棵最优棵最优二叉查找树：二叉查找树：T(1,1)，T(2,2), ,T(n,n)。依据公式。依据公式(4-20)(4-22)，很容易，很容易求得求