背包问题之动态规划法ppt课件

1、 动态规划动态规划1. 概述概述3. 图问题中的动态规划法图问题中的动态规划法2. 组合问题中的动态规划法组合问题中的动态规划法4. 查找问题中的动态规划法查找问题中的动态规划法1.1. 概概 述述 1.1 例题（多段图）例题（多段图） 1.4 最优性原理最优性原理1.6 动态规划法的设计思想动态规划法的设计思想1.5 无后效性原则无后效性原则1.3 动态规划适于解决什么样的问题动态规划适于解决什么样的问题1.2 什么是动态规划什么是动态规划21.1 多段图的最短路径问题多段图的最短路径问题设图设图G=(V, E)是一个带权有向连通图，如果把顶点集合是一个带权有向连通图，如果把顶点集合V划分成

2、划分成k个互不相交的子集个互不相交的子集Vi（2kn, 1ik），使得），使得E中的任何一中的任何一条边条边(u, v)，必有，必有uVi，vVi+m（1ik, 1i+mk），则称），则称图图G为多段图，称为多段图，称sV1为源点，为源点，tVk为终点。多段图的最短路为终点。多段图的最短路径问题是求从源点到终点的最小代价路径。径问题是求从源点到终点的最小代价路径。 由于多段图将顶点划分为由于多段图将顶点划分为k个互不相交的子集，所以，多段个互不相交的子集，所以，多段图划分为图划分为k段，每一段包含顶点的一个子集。根据多段图的定义，段，每一段包含顶点的一个子集。根据多段图的定义，每个子集中的顶点

3、互不邻接。不失一般性，将多段图的顶点按每个子集中的顶点互不邻接。不失一般性，将多段图的顶点按照段的顺序进行编号，同一段内顶点的相互顺序无关紧要。假照段的顺序进行编号，同一段内顶点的相互顺序无关紧要。假设图中的顶点个数为设图中的顶点个数为n，则源点，则源点s的编号为的编号为0，终点，终点t的编号为的编号为n-1，并且，对图中的任何一条边并且，对图中的任何一条边(u, v)，顶点，顶点u的编号小于顶点的编号小于顶点v的编的编号。号。32120345678949387684756866537图图1 一个多段图一个多段图4设设G是一个有向加权图，则是一个有向加权图，则G从顶点从顶点i到顶点到顶点j之间

4、的之间的最短路径问题满足最优性原理。最短路径问题满足最优性原理。证明：设证明：设iipiqj是一条最短路径，但其中子路径是一条最短路径，但其中子路径 ipiqj不是最优的，不是最优的，假设最优的路径为假设最优的路径为ipiqj，则我们重新构造一条路径：则我们重新构造一条路径：iipiqj显然该路径长度小于显然该路径长度小于iipiqj，与，与iipiqj 是顶是顶点点i到顶点到顶点j的最短路径相矛盾的最短路径相矛盾.所以，原问题满足最优性原理。所以，原问题满足最优性原理。 5对多段图的边对多段图的边(u, v)，用，用cuv表示边上的权值，将从源点表示边上的权值，将从源点s到终点到终点t的最短

5、路径记为的最短路径记为d(s, t)，则从源点，则从源点0到终点到终点9的最的最短路径短路径d(0, 9)由下式确定：由下式确定：d d(0, 9)=min(0, 9)=minc c0101+ +d d(1, 9), (1, 9), c c0202+ +d d(2, 9), (2, 9), c c0303+ +d d(3, 9)(3, 9) 这是最后一个阶段的决策，它依赖于这是最后一个阶段的决策，它依赖于d d(1, 9)(1, 9)、d d(2, 9)(2, 9)和和d d(3, 9)(3, 9)的计算结果，而的计算结果，而d d(1, 9)=min(1, 9)=minc c1414+ +d

6、 d(4, 9), (4, 9), c c1515+ +d d(5, 9)(5, 9)d(2, 9)=minc24+d(4, 9), c25+d(5, 9), c26+d(6, 9)d(3, 9)=minc35+d(5, 9), c36+d(6, 9) 这一阶段的决策又依赖于这一阶段的决策又依赖于d(4, 9)、d(5, 9)和和d(6, 9)的计算结果：的计算结果：6d(4, 9)=minc47+d(7, 9), c48+d(8, 9)d(5, 9)=minc57+d(7, 9), c58+d(8, 9)d(6, 9)=minc67+d(7, 9), c68+d(8, 9) 这一阶段的决策依

7、赖于这一阶段的决策依赖于d(7, 9)和和d(8, 9)的计算，而的计算，而d(7, 9)和和d(8, 9)可以直接获得（括号中给出了决策产生的状态转移）：可以直接获得（括号中给出了决策产生的状态转移）：d(7, 9)=c797(79)d(8, 9)=c893(89) 再向前推导，有：再向前推导，有：d(6, 9)=minc67+d(7, 9), c68+d(8, 9)=min6+7, 5+3=8(68)d(5, 9)=minc57+d(7, 9), c58+d(8, 9)=min8+7, 6+3=9(58)d(4, 9)=minc47+d(7, 9), c48+d(8, 9)=min5+7,

8、 6+3=9(48)7d(3, 9)=minc35+d(5, 9), c36+d(6, 9)=min4+9, 7+8=13(35)d(2, 9)=minc24+d(4, 9), c25+d(5, 9), c26+d(6, 9)=min6+9, 7+9, 8+8=15(24)d(1, 9)=minc14+d(4, 9), c15+d(5, 9)=min9+9, 8+9=17(15)d(0, 9)=minc01+d(1, 9), c02+d(2, 9), c03+d(3, 9)=min4+17, 2+15, 3+13=16(03) 得到最短路径为得到最短路径为03589，长度为，长度为16。 8

9、在上例的多阶段决策问题中，各个阶段采取的在上例的多阶段决策问题中，各个阶段采取的决策，一般来说是与时间有关的，决策依赖于当前状决策，一般来说是与时间有关的，决策依赖于当前状态，又随即引起状态的转移，一个决策序列就是在变态，又随即引起状态的转移，一个决策序列就是在变化的状态中产生出来的，故有化的状态中产生出来的，故有“动态动态”的含义，称这的含义，称这种解决多阶段决策最优化问题的方法为动态规划方法。种解决多阶段决策最优化问题的方法为动态规划方法。 1.2 什么是动态规划什么是动态规划9动态规划是运筹学的一个分支。与其说动态规动态规划是运筹学的一个分支。与其说动态规划是一种算法，不如说是一种思维方

10、法来得更贴切。划是一种算法，不如说是一种思维方法来得更贴切。因为动态规划没有固定的框架，即便是应用到同一道因为动态规划没有固定的框架，即便是应用到同一道题上，也可以建立多种形式的求解算法。许多隐式图题上，也可以建立多种形式的求解算法。许多隐式图上的算法，例如求单源最短路径的上的算法，例如求单源最短路径的Dijkstra算法、广算法、广度优先搜索算法，都渗透着动态规划的思想。度优先搜索算法，都渗透着动态规划的思想。因此，动态规划不像深度或广度优先那样可以因此，动态规划不像深度或广度优先那样可以提供一套模式，需要的时候，取来就可以使用；它必提供一套模式，需要的时候，取来就可以使用；它必须对具体问题

11、进行具体分析处理，需要丰富的想象力须对具体问题进行具体分析处理，需要丰富的想象力去建立模型，需要创造性的思想去求解。去建立模型，需要创造性的思想去求解。10 准确地说，动态规划不是万能的，它只适于解决准确地说，动态规划不是万能的，它只适于解决一定条件的最优策略问题。一定条件的最优策略问题。 或许，大家听到这个结或许，大家听到这个结论会很失望：其实，这个结论并没有削减动态规划的光论会很失望：其实，这个结论并没有削减动态规划的光辉，因为属于上面范围内的问题极多，还有许多看似不辉，因为属于上面范围内的问题极多，还有许多看似不是这个范围中的问题都可以转化成这类问题。是这个范围中的问题都可以转化成这类问

12、题。 上面所说的上面所说的“满足一定条件满足一定条件”主要指下面两点：主要指下面两点： (1)状态必须满足最优化原理状态必须满足最优化原理； (2)状态必须满足无后效性状态必须满足无后效性。 这条特征说明什么呢这条特征说明什么呢?它说明动态规划适于解决当前它说明动态规划适于解决当前决策和过去状态无关的问题。状态，出现在策略的任何决策和过去状态无关的问题。状态，出现在策略的任何一个位置，它的地位都是相同的，都可以实施同样的决一个位置，它的地位都是相同的，都可以实施同样的决策。这就是无后效性的内涵。策。这就是无后效性的内涵。 1.3 动态规划适于解决什么样的问题动态规划适于解决什么样的问题 11作

13、为整个过程的最优策略具有如下性质：无论过去的作为整个过程的最优策略具有如下性质：无论过去的状态和决策如何，对前面的决策所形成的当前状态而状态和决策如何，对前面的决策所形成的当前状态而言，余下的诸决策必须构成最优策略。言，余下的诸决策必须构成最优策略。 可以通俗地理解为子问题的局部最优将导致整个问题可以通俗地理解为子问题的局部最优将导致整个问题的全局最优，即问题具有最优子结构的性质，也就是的全局最优，即问题具有最优子结构的性质，也就是说一个问题的最优解只取决于其子问题的最优解，非说一个问题的最优解只取决于其子问题的最优解，非最优解对问题的求解没有影响。在最优解对问题的求解没有影响。在 例题例题1

14、 1 最短路径最短路径问题中，问题中，A A到到E E的最优路径上的任一点到终点的最优路径上的任一点到终点E E的路径的路径也必然是该点到终点也必然是该点到终点E E的一条最优路径，满足最优化的一条最优路径，满足最优化原理。下面来讨论另外一个问题。原理。下面来讨论另外一个问题。1.4 最优性原理最优性原理 12例题例题 余数最少的路径余数最少的路径 如图所示，有如图所示，有4个点，个点，分别是分别是A、B、C、D，相邻，相邻两点用两条连线两点用两条连线 C2k，C2k-1(1k3)表示两条通行的道路。连线表示两条通行的道路。连线上的数字表示道路的长度。上的数字表示道路的长度。定义从定义从A到到

15、D的所有路径中，的所有路径中，长度除以长度除以4所得余数最小的所得余数最小的路径为最优路径。路径为最优路径。 求一条最优路径。求一条最优路径。13【分析】在这个问题中，如果还按照例题【分析】在这个问题中，如果还按照例题1中的方法中的方法去求解就会发生错误。按照例题去求解就会发生错误。按照例题1的思想，的思想，A的最优取的最优取值可以由值可以由B的最优取值来确定，而的最优取值来确定，而B的最优取值为的最优取值为(1+3) mod 4 = 0，所以，所以A的最优值应为的最优值应为2，而实际上，路径，而实际上，路径C1C3C5可得最优值为可得最优值为(2+1+1) mod 4 = 0，所以，所以，B

16、的最优路径并不是的最优路径并不是A的最优路径的子路径，也就是说，的最优路径的子路径，也就是说，A的最优取值不是由的最优取值不是由B的最优取值决定的，即其不满足的最优取值决定的，即其不满足最优化原理，问题不具有最优子结构的性质。最优化原理，问题不具有最优子结构的性质。 由此可见，并不是所有的由此可见，并不是所有的“决策问题决策问题”都可以用都可以用“动态规划动态规划”来解决，运用来解决，运用“动态规划动态规划”来处理问题来处理问题必必须满足最优化原理。须满足最优化原理。14所谓无后效性原则，指的是这样一种性质：所谓无后效性原则，指的是这样一种性质：某阶段的状态一旦确定，则此后过程的演变不某阶段的

17、状态一旦确定，则此后过程的演变不再受此前各状态及决策的影响。也就是说，再受此前各状态及决策的影响。也就是说，“未来与未来与过去无关过去无关”，当前的状态是此前历史的一个完整总结，当前的状态是此前历史的一个完整总结，此前的历史只能通过当前的状态去影响过程未来的演此前的历史只能通过当前的状态去影响过程未来的演变。具体地说，如果一个问题被划分各个阶段之后，变。具体地说，如果一个问题被划分各个阶段之后，阶段阶段 I I 中的状态只能由阶段中的状态只能由阶段 I+1 I+1 中的状态通过状态中的状态通过状态转移方程得来，与其他状态没有关系，特别是与未发转移方程得来，与其他状态没有关系，特别是与未发生的状

18、态没有关系，这就是无后效性。生的状态没有关系，这就是无后效性。1.5 无后效性原则无后效性原则151.6 动态规划法的设计思想动态规划法的设计思想 动态规划法将待求解问题分解成若干个相互重叠的子动态规划法将待求解问题分解成若干个相互重叠的子问题，每个子问题对应决策过程的一个阶段，一般来问题，每个子问题对应决策过程的一个阶段，一般来说，子问题的重叠关系表现在对给定问题求解的递推说，子问题的重叠关系表现在对给定问题求解的递推关系（也就是动态规划函数）中，将子问题的解求解关系（也就是动态规划函数）中，将子问题的解求解一次并填入表中，当需要再次求解此子问题时，可以一次并填入表中，当需要再次求解此子问题

19、时，可以通过查表获得该子问题的解而不用再次求解，从而避通过查表获得该子问题的解而不用再次求解，从而避免了大量重复计算。为了达到这个目的，可以用一个免了大量重复计算。为了达到这个目的，可以用一个表来记录所有已解决的子问题的解，这就是动态规划表来记录所有已解决的子问题的解，这就是动态规划法的设计思想。具体的动态规划法是多种多样的，但法的设计思想。具体的动态规划法是多种多样的，但他们具有相同的填表形式。他们具有相同的填表形式。16原问题的解原问题的解原问题原问题 图图2 动态规划法的求解过程动态规划法的求解过程 填填 表表子问题子问题1子问题子问题2子问题子问题n17一、划分阶段：一、划分阶段：按照

20、问题的时间或空间特征，把问题分为若干个阶段。按照问题的时间或空间特征，把问题分为若干个阶段。二、选择状态：二、选择状态：将问题发展到各个阶段时所处于的各种客观情况用不同将问题发展到各个阶段时所处于的各种客观情况用不同的状态表示出来。的状态表示出来。三、确定决策并写出状态转移方程：三、确定决策并写出状态转移方程：状态转移就是根据上一阶段的状态和决策来导出本阶段状态转移就是根据上一阶段的状态和决策来导出本阶段的状态。的状态。四、写出规划方程（包括边界条件）：四、写出规划方程（包括边界条件）：动态规划的基本方程是规划方程的通用形式化表达式。动态规划的基本方程是规划方程的通用形式化表达式。动态规划算法

21、的基本步骤动态规划算法的基本步骤18可以用动态规划法求解的问题除了能够分解为相互重叠的可以用动态规划法求解的问题除了能够分解为相互重叠的若干子问题外，还要满足最优性原理（也称最优子结构性若干子问题外，还要满足最优性原理（也称最优子结构性质），这类问题具有如下特征：该问题的最优解中也包含质），这类问题具有如下特征：该问题的最优解中也包含着其子问题的最优解。在分析问题是否满足最优性原理时，着其子问题的最优解。在分析问题是否满足最优性原理时，通常先假设由问题的最优解导出的子问题的解不是最优的，通常先假设由问题的最优解导出的子问题的解不是最优的，然后再设法说明在这个假设下可构造出比原问题最优解更然后再

22、设法说明在这个假设下可构造出比原问题最优解更好的解，从而导致矛盾。好的解，从而导致矛盾。 动态规划法利用问题的最优性原理，以自底向上的方动态规划法利用问题的最优性原理，以自底向上的方式从子问题的最优解逐步构造出整个问题的最优解。应用式从子问题的最优解逐步构造出整个问题的最优解。应用动态规划法设计算法一般分成三个阶段：动态规划法设计算法一般分成三个阶段：（1 1）分段：将原问题分解为若干个相互重叠的子问题；）分段：将原问题分解为若干个相互重叠的子问题；（2 2）分析：分析问题是否满足最优性原理，找出动态规划）分析：分析问题是否满足最优性原理，找出动态规划函数的递推式；函数的递推式；（3 3）求解

23、：利用递推式自底向上计算，实现动态规划过程。）求解：利用递推式自底向上计算，实现动态规划过程。 192. 组合问题中的动态规划法组合问题中的动态规划法 2.1 0/12.1 0/1背包问题背包问题 2.2 2.2 最长公共子序列问题最长公共子序列问题202.1 0/1背包问题背包问题 给定给定n种物品和一个背包，种物品和一个背包，物品物品i的重量是的重量是wi，其价值为，其价值为vi，背包的容量为，背包的容量为C。背包。背包问题是如何选择装入背包的问题是如何选择装入背包的物品，使得装入背包中物品物品，使得装入背包中物品的总价值最大的总价值最大?如果在选择如果在选择装入背包的物品时，对每种装入背

24、包的物品时，对每种物品物品i只有两种选择：装入只有两种选择：装入背包或不装入背包，即不能背包或不装入背包，即不能将物品将物品i装入背包多次，也装入背包多次，也不能只装入物品不能只装入物品i的一部分，的一部分，则称为则称为0/1背包问题。背包问题。21在在0/1背包问题中，物品背包问题中，物品i或者被装入背包，或者不被或者被装入背包，或者不被装入背包，设装入背包，设xi表示物品表示物品i装入背包的情况，则当装入背包的情况，则当xi=0时，表示物品时，表示物品i没有被装入背包，没有被装入背包，xi=1时，表示物品时，表示物品i被装入背包。根据问题的要求，有如下约束条件和被装入背包。根据问题的要求，

25、有如下约束条件和目标函数：目标函数： )1(1 ,01nixCxwiniii（式（式1）niiixv1max（式（式2）问题归结为寻找一个满足约束条件式问题归结为寻找一个满足约束条件式1，并使目标，并使目标函数式函数式2达到最大的解向量达到最大的解向量X=(x1, x2, , xn)。22首先证明首先证明0/1背包问题满足最优性原理。背包问题满足最优性原理。 设设(x1, x2, , xn)是所给是所给0/1背包问题的一个最优解，背包问题的一个最优解，则则( x2, , xn)是下面一个子问题的最优解：是下面一个子问题的最优解：)2(1 , 0112nixxwCxwiniii如若不然，设如若不

26、然，设(y2, , yn)是上述子问题的一个最优解，是上述子问题的一个最优解，则则 ，且，且 。因此，。因此， ，这说明，这说明(x1, y2, , yn)是所给是所给0/1背包问题比背包问题比(x1, x2, , xn)更优的解，从而导致矛盾。更优的解，从而导致矛盾。 niiiniiixvyv22Cywxwniii211niiiniiiniiixvxvxvyvxv1211211230/1背包问题可以看作是决策一个序列背包问题可以看作是决策一个序列(x1, x2, , xn)，对，对任一变量任一变量xi的决策是决定的决策是决定xi=1还是还是xi=0。在对。在对xi-1决策后，决策后，已确定了

27、已确定了(x1, , xi-1)，在决策，在决策xi时，问题处于下列两种状时，问题处于下列两种状态之一：态之一：a.背包容量不足以装入物品背包容量不足以装入物品i，则，则xi=0背包不增加价值；背包不增加价值；b.背包容量可以装入物品背包容量可以装入物品i，则，则xi=1背包的价值增加了背包的价值增加了vi。这两种情况下背包价值的最大者应该是对这两种情况下背包价值的最大者应该是对xi决策后的背包决策后的背包价值。令价值。令V(i, j)表示在前表示在前i(1in)个物品中能够装入容量为个物品中能够装入容量为j（1jC）的背包中的物品的最大值，则可以得到如下）的背包中的物品的最大值，则可以得到如

28、下动态规划函数：动态规划函数： V(i, 0)= V(0, j)=0 （式（式3）24iiiiwjvwjiVjiVwjjiVjiV), 1(), 1(max), 1(),(式式3表明：把前面表明：把前面i个物品装入容量为个物品装入容量为0的背包和把的背包和把0个物品装入个物品装入容量为容量为j的背包，得到的价值均为的背包，得到的价值均为0。式。式4的第一个式子表明：如的第一个式子表明：如果第果第i个物品的重量大于背包的容量，则装入前个物品的重量大于背包的容量，则装入前i个物品得到的个物品得到的最大价值和装入前最大价值和装入前i- -1个物品得到的最大价值是相同的，即物品个物品得到的最大价值是相

29、同的，即物品i不能装入背包；第二个式子表明：如果第不能装入背包；第二个式子表明：如果第i个物品的重量小于个物品的重量小于背包的容量，则会有以下两种情况：（背包的容量，则会有以下两种情况：（1）如果把第）如果把第i个物品装个物品装入背包，则背包中物品的价值等于把前入背包，则背包中物品的价值等于把前i- -1个物品装入容量为个物品装入容量为j- -wi的背包中的价值加上第的背包中的价值加上第i个物品的价值个物品的价值vi；（；（2）如果第）如果第i个物个物品没有装入背包，则背包中物品的价值就等于把前品没有装入背包，则背包中物品的价值就等于把前i- -1个物品装个物品装入容量为入容量为j的背包中所取

30、得的价值。显然，取二者中价值较大者的背包中所取得的价值。显然，取二者中价值较大者作为把前作为把前i个物品装入容量为个物品装入容量为j的背包中的最优解。的背包中的最优解。 （式（式4）25第一阶段第一阶段，只装入前，只装入前1个物品，确定在各种情况下的背包能够得个物品，确定在各种情况下的背包能够得到的最大价值；到的最大价值；第二阶段第二阶段，只装入前，只装入前2个物品，确定在各种情况下的背包能够得个物品，确定在各种情况下的背包能够得到的最大价值；依此类推，直到第到的最大价值；依此类推，直到第n个阶段。个阶段。最后最后，V(n,C)便是在容量为便是在容量为C的背包中装入的背包中装入n个物品时取得的

31、最个物品时取得的最大价值。为了确定装入背包的具体物品，从大价值。为了确定装入背包的具体物品，从V(n,C)的值向前推，的值向前推，如果如果V(n,C)V(n- -1,C)，表明第，表明第n个物品被装入背包，前个物品被装入背包，前n- -1个物个物品被装入容量为品被装入容量为C- -wn的背包中；否则，第的背包中；否则，第n个物品没有被装入背个物品没有被装入背包，前包，前n- -1个物品被装入容量为个物品被装入容量为C的背包中。依此类推，直到确的背包中。依此类推，直到确定第定第1个物品是否被装入背包中为止。由此，得到如下函数：个物品是否被装入背包中为止。由此，得到如下函数： ), 1(),(,

32、1), 1(),(0jiVjiVwjjjiVjiVxii（式（式5）26例如，有例如，有5个物品，其重量分别是个物品，其重量分别是2, 2, 6, 5, 4，价值，价值分别为分别为6, 3, 5, 4, 6，背包的容量为，背包的容量为10，求装入背包，求装入背包的物品和获得的最大价值。的物品和获得的最大价值。 根据动态规划函数，用一个根据动态规划函数，用一个(n+1)(C+1)的二维表的二维表V，Vij表示把前表示把前i个物品装入容量为个物品装入容量为j的背包中获得的最大价值，根的背包中获得的最大价值，根据式据式3把表的第把表的第0行和第行和第0列初始化为列初始化为0，然后一行一行地计，然后一

33、行一行地计算算Vij，如图，如图3所示。所示。 27x5=1x4=0 x3=0 x2=1x1=1 0123456789 10 00000000000w1=2 v1=6100666666666w2=2 v2=3200669999999w3=6 v3=5300669999111114w4=5 v4=44006699910111314w5=5 v5=6500669912 12151515可以看到，装入背包的物品的最大价值是可以看到，装入背包的物品的最大价值是15，根据式，根据式5，装，装入背包的物品为入背包的物品为X=1, 1, 0, 0, 1。图3 0/1背包求解（填表）过程28设设n个物品的重量

34、存储在数组个物品的重量存储在数组wn中，价值存储在数组中，价值存储在数组vn中，背包容量为中，背包容量为C，数组，数组Vn+1C+1存放迭代结存放迭代结果，其中果，其中Vij表示前表示前i个物品装入容量为个物品装入容量为j的背包中获的背包中获得的最大价值，数组得的最大价值，数组xn存储装入背包的物品，动态存储装入背包的物品，动态规划法求解规划法求解0/1背包问题的算法如下：背包问题的算法如下： 29算法算法10/1背包问题背包问题 int KnapSack(int n, int w , int v ) for (i=0; i=n; i+) /初始化第初始化第0列列 Vi0=0; for (j=

35、0; j=C; j+) /初始化第初始化第0行行 V0j=0; for (i=1; i=n; i+) /计算第计算第i行，进行第行，进行第i次迭代次迭代 for (j=1; j=C; j+) if (j0; i-) if (VijVi-1j) xi=1; j=j-wi; else xi=0; return VnC; /返回背包取得的最大价值返回背包取得的最大价值 302.2 最长公共子序列问题最长公共子序列问题 对给定序列对给定序列X=(x1, x2, xm)和序列和序列Z=(z1, z2, zk)，Z是是X的的子序列当且仅当存在一个严格递增下标序列子序列当且仅当存在一个严格递增下标序列(i1

36、, i2, ik)，使得，使得对于所有对于所有j=1, 2, , k，有，有zj=xij（1ijm）。例如，对于序列）。例如，对于序列X=(a, b, c, b, d, a, b)，序列，序列(b, c, d, b)是是X的一个长度为的一个长度为4的子序的子序列，相应的递增下标序列为列，相应的递增下标序列为(2, 3, 5, 7)，序列，序列(a, c, b, d, b)是是X的的一个长度为一个长度为5的子序列，相应的递增下标序列为的子序列，相应的递增下标序列为(1, 3, 4, 5, 7)。可见，一个给定序列的子序列可以有多个。可见，一个给定序列的子序列可以有多个。 给定两个序列给定两个序列

37、X和和Y，当另一个序列，当另一个序列Z既是既是X的子序列又是的子序列又是Y的子序列时，称的子序列时，称Z是序列是序列X和和Y的公共子序列。例如，序列的公共子序列。例如，序列X=(a, b, c, b, d, b)，Y=(a, c, b, b, a, b, d, b, b)，序列，序列(a, c, b)是序列是序列X和和Y的一个长度为的一个长度为3的公共子序列，序列的公共子序列，序列(a, b, b, d, b)是序列是序列X和和Y的的一个长度为一个长度为5的公共子序列。最长公共子序列问题就是在序列的公共子序列。最长公共子序列问题就是在序列X和和Y的公共子序列中查找长度最长的公共子序列。的公共子

38、序列中查找长度最长的公共子序列。 31 设序列设序列X=x1, x2, xm和和Y=y1, y2, yn的最长公共子序列为的最长公共子序列为Z=z1, z2, zk，记，记Xk为序列为序列X中前中前k个连续字符组成的子序列，个连续字符组成的子序列，Yk为序列为序列Y中前中前k个连续字符组成的子序列，个连续字符组成的子序列，Zk为序列为序列Z中前中前k个连续字个连续字符组成的子序列，显然有下式成立：符组成的子序列，显然有下式成立：（1）若）若xm=yn，则，则zk=xm=yn，且，且Zk-1是是Xm-1和和Yn-1的最长公共子序列；的最长公共子序列；（2）若）若xmyn且且zkxm，则，则Z是是

39、Xm-1和和Y的最长公共子序列；的最长公共子序列；（3）若）若xmyn且且zkyn，则，则Z是是X和和Yn-1的最长公共子序列。的最长公共子序列。 可见，两个序列的最长公共子序列包含了这两个序列的前缀序列可见，两个序列的最长公共子序列包含了这两个序列的前缀序列的最长公共子序列。因此，最长公共子序列问题满足最优性原理。的最长公共子序列。因此，最长公共子序列问题满足最优性原理。 要找出序列要找出序列X=x1, x2, xm和和Y=y1, y2, yn的最长公共子序列，的最长公共子序列，可按下述递推方式计算：当可按下述递推方式计算：当xm=yn时，找出时，找出Xm-1和和Yn-132的最长公共子序列

40、，然后在其尾部加上的最长公共子序列，然后在其尾部加上xm即可得到即可得到X和和Y的最长的最长公共子序列；当公共子序列；当xmyn时，必须求解两个子问题：找出时，必须求解两个子问题：找出Xm-1和和Y的最长公共子序列以及的最长公共子序列以及Xm和和Yn-1的最长公共子序列，这两个公共的最长公共子序列，这两个公共子序列中的较长者即为子序列中的较长者即为X和和Y的最长公共子序列。用的最长公共子序列。用Lij表示子表示子序列序列Xi和和Yj的最长公共子序列的长度，可得如下动态规划函数：的最长公共子序列的长度，可得如下动态规划函数：L00=Li0=L0j=0(1L00=Li0=L0j=0(1i im,1

41、m,1j jn) n) （式（式6 6） （式（式7 7）1, 1,1jLi1,Lijmax1, 1,111jLiLijjiyxjiyxjiji 由此，把序列由此，把序列X=x1, x2, xm和和Y=y1, y2, yn的最长公的最长公共子序列的搜索分为共子序列的搜索分为m个阶段，第个阶段，第1阶段，按照式阶段，按照式7计算计算X1和和Yj的最长公共子序列长度的最长公共子序列长度L1j（1jn），第），第2阶段，按照式阶段，按照式7计算计算X2和和Yj的最长公共子序列长度的最长公共子序列长度L2j（1jn），依此），依此类推，最后在第类推，最后在第m阶段，计算阶段，计算Xm和和Yj的最长公共

42、子序列长度的最长公共子序列长度Lmj（1jn），则），则Lmn就是序列就是序列Xm和和Yn的最长公共子的最长公共子序列的长度。序列的长度。 33 为了得到序列为了得到序列Xm和和Yn具体的最长公共子序列，设二维表具体的最长公共子序列，设二维表Sm+1n+1，其中，其中Sij表示在计算表示在计算Lij的过程中的搜索状态，的过程中的搜索状态，并且有：并且有： 1jLi1Lij31jLi1Lij21Sij且且jijijiyxyxyx若若Sij=1，表明，表明ai=bj，则下一个搜索方向是，则下一个搜索方向是Si- -1j- -1；若若Sij=2，表明，表明aibj且且Lij- -1Li- -1j，则

43、下一个搜索方向，则下一个搜索方向是是Sij- -1；若若Sij=3，表明，表明aibj且且Lij- -1Li- -1j，则下一个搜索方向，则下一个搜索方向是是Si- -1j。 如：序列如：序列X=(a, b, c, b, d, b)，Y=(a, c, b, b, a, b, d, b, b)，建立两，建立两个个(m+1)(n+1)的二维表的二维表L和表和表S，分别存放搜索过程中得到的子，分别存放搜索过程中得到的子序列的长度和状态。首先把表序列的长度和状态。首先把表L和表和表S的第的第0行和第行和第0列初始化为列初始化为0，然后根据式然后根据式6和和7 7逐行计算填入表逐行计算填入表L和表和表S

44、中。计算结果如图中。计算结果如图4所示。所示。 34(a) 长度矩阵长度矩阵L (b) 状态矩阵状态矩阵S图图4 最长公共子序列求解示意图最长公共子序列求解示意图01234567890123456789000000000000000000000101111111111012221222220112222222203211212113012222222230312222222401233333334033113131150123333444503332221226012344445560331131211353. 图问题中的动态规划法图问题中的动态规划法 3.1 TSP问题问题 3.2 多段图的

45、最短路径问题多段图的最短路径问题363.1 TSP问题问题 TSP问题是指旅行家要旅行问题是指旅行家要旅行n个城市，要个城市，要求各个城市经历且仅经历一次然后回到求各个城市经历且仅经历一次然后回到出发城市，并要求所走的路程最短。出发城市，并要求所走的路程最短。各个城市间的距离可以用代价矩阵来表各个城市间的距离可以用代价矩阵来表示，如果示，如果(i, j) E，则，则cij。37573246325763)(ijcC假设从顶点假设从顶点i出发，令出发，令d(i, V)表示从顶点表示从顶点i出发经过出发经过V中各个顶点一次且仅一次，最后回到出发点中各个顶点一次且仅一次，最后回到出发点i的最短的最短路

46、径长度，开始时，路径长度，开始时，VVi，于是，于是，TSP问题的问题的动态规划函数为：动态规划函数为：d(i,V)=mincik+d(k,Vk)(kV) （式（式8）d(k,)=cki(ki) （式（式9）38从城市从城市0出发，经城市出发，经城市1、2、3然后回到城市然后回到城市0的最短路的最短路径长度是：径长度是：d(0, 1, 2, 3)=minc01+ d(1, 2, 3), c02+ d(2, 1, 3), c03+ d(3, 1, 2)这是最后一个阶段的决策，它必须依据这是最后一个阶段的决策，它必须依据d(1, 2, 3)、d(2, 1, 3)和和d(3, 1, 2)的计算结果，

47、而：的计算结果，而： 573246325763)(ijcC39d(1, 2, 3)=minc12+d(2, 3), c13+ d(3, 2)d(2, 1, 3)=minc21+d(1, 3), c23+ d(3, 1)d(3, 1, 2)=minc31+d(1, 2), c32+ d(2, 1)这一阶段的决策又依赖于下面的计算结果：这一阶段的决策又依赖于下面的计算结果：d(1, 2)= c12+d(2, ) d(2, 3)=c23+d(3, ) d(3, 2)= c32+d(2, ) d(1, 3)= c13+d(3, ) d(2, 1)=c21+d(1, ) d(3, 1)=c31+d(1,

48、 ) 而下式可以直接获得（括号中是该决策引起的状态转而下式可以直接获得（括号中是该决策引起的状态转移）：移）：d(1, )= c10 =5(10) d(2, )= c20 =6(20) d(3, )= c30 =3(30) 40再向前推导，有：再向前推导，有：d(1, 2)= c12+d(2, )=2+6=8(12) d(1, 3)= c13+d(3, )=3+3=6(13) d(2, 3)= c23+d(3, )=2+3=5(23) d(2, 1)= c21+d(1, )=4+5=9(21)d(3, 1)= c31+d(1, )=7+5=12(31) d(3, 2)= c32+d(2, )=

49、5+6=11(32)再向推导，有：再向推导，有：d(1, 2, 3)=minc12+d(2, 3), c13+ d(3, 2)=min2+5, 3+11=7(12)d(2, 1, 3)=minc21+d(1, 3), c23+ d(3, 1)=min4+6, 2+12=10(21)41d(3, 1, 2)=minc31+d(1, 2), c32+ d(2, 1)=min7+8, 5+9=14(32)最后有：最后有：d(0, 1, 2, 3)=minc01+ d(1, 2, 3), c02+ d(2, 1, 3), c03+ d(3, 1, 2) =min3+7, 6+10, 7+14=10(0

50、1)从顶点从顶点0出发的出发的TSP问题的最短路径长度为问题的最短路径长度为10，路径是，路径是01230。42假设对假设对n n个顶点分别用个顶点分别用0 0n-1n-1的数字编号，考虑从顶点的数字编号，考虑从顶点0 0出发求解出发求解TSPTSP问题的填表形式。首先，按个数为问题的填表形式。首先，按个数为1 1、2 2、n-1n-1的顺序生成的顺序生成1 1n-1n-1个元素的子集存放在数组个元素的子集存放在数组V2n-1V2n-1中，例如当中，例如当n=4n=4时，时，V1=1, V2=2, V3=3, V4=1, 2, V5=1, 3, V1=1, V2=2, V3=3, V4=1,

51、2, V5=1, 3, V6=2, 3, V7=1, 2, 3V6=2, 3, V7=1, 2, 3。设数组。设数组dn2n-1存放迭代结果，存放迭代结果，其中其中dij表示从顶点表示从顶点i经过子集经过子集Vj中的顶点一次且仅一次，最后中的顶点一次且仅一次，最后回到出发点回到出发点0的最短路径长度。首先，根据式的最短路径长度。首先，根据式9将数组将数组d的第的第0列初列初始化，然后根据式始化，然后根据式8逐列计算，其填表过程如图逐列计算，其填表过程如图5 5所示。所示。ji 1231, 21, 32, 31, 2, 30 1015 86 7 269 5 10 331211 14 图5 动态规

52、划法的填表过程43设顶点之间的代价存放在数组cnn中，动态规划法求解TSP问题的算法如下： 算法算法2TSP问题问题 1for (i=1; in; i+) /初始化第初始化第0列列 di0=ci0; 2for (j=1; j2n-1- -1; j+) for (i=1; in; i+) /依次进行第依次进行第i次迭代次迭代 if (子集子集Vj中不包含中不包含i) 对对Vj中的每个元素中的每个元素k，计算，计算dij=min(cik+dkj- -1); 3对对V2n-1- -1中的每一个元素中的每一个元素k，计算，计算d02n-1-1=min(c0k+dk2n-1- -2);4输出最短路径长度

53、输出最短路径长度d02n-1- -1;算法算法2的时间复杂性为的时间复杂性为O(2n)。和蛮力法相比，动态规划法求。和蛮力法相比，动态规划法求解解TSP问题，把原来的时间复杂性是问题，把原来的时间复杂性是O(n!)的排列问题，转的排列问题，转化为组合问题，从而降低了算法的时间复杂性，但它仍需要化为组合问题，从而降低了算法的时间复杂性，但它仍需要指数时间。指数时间。 44练练454. 查找问题中的动态规划法查找问题中的动态规划法 4.1 最优二叉查找树最优二叉查找树 4.2 近似串匹配问题近似串匹配问题46 设设r1, r2, , rn是是n个记录的集合，其查找概率分别是个记录的集合，其查找概率

54、分别是p1, p2, , pn，最优二叉查找树（，最优二叉查找树（Optimal Binary Search Trees）是以这）是以这n个记录构成的二叉查找树中具有最少平均个记录构成的二叉查找树中具有最少平均比较次数的二叉查找树，即比较次数的二叉查找树，即 最小，其中最小，其中pi是记录是记录ri的的查找概率，查找概率，ci是在二叉查找树中查找是在二叉查找树中查找ri的比较次数。的比较次数。 例如，集合例如，集合 A A, , B B, , C C, , D D 的查找概率是的查找概率是0.1, 0.2, 0.1, 0.2, 0.4, 0.30.4, 0.3，图，图6.116.11给出了三棵

55、二叉查找树，在查找成功的给出了三棵二叉查找树，在查找成功的情况下，二叉查找树情况下，二叉查找树(a)(a)的平均比较次数是的平均比较次数是0.10.11 10.20.22+0.42+0.43+0.33+0.34=2.94=2.9，二叉查找树，二叉查找树(b)(b)的平均比较次的平均比较次数是数是0.10.12 20.20.21+0.41+0.42+0.32+0.33=2.13=2.1，最优二叉查找，最优二叉查找树 是树 是 ( c )( c ) ， 平 均 比 较 次 数 是， 平 均 比 较 次 数 是 0 . 10 . 1 3 3 0.20.22+0.42+0.41+0.31+0.32=1

56、.72=1.7。 4.1 最优二叉查找树最优二叉查找树 47ABCD(a) (b) (c)图6 二叉查找树示例BCDAABCD 将由将由r1, r2, , rn构成的二叉查找树记为构成的二叉查找树记为T(1, n)，其中，其中rk（1kn）是）是T(1, n)的根结点，则其左子树的根结点，则其左子树T(1, k- -1)由由r1, , rk-1构成，其右子树构成，其右子树T(k+1, n)由由rk+1, , rn构成，如图构成，如图7所示。所示。显然，若显然，若T(1, n)是最优二叉查找树，则其左子树是最优二叉查找树，则其左子树T(1, k- -1)和右子和右子树树T(k+1, n)也是最优

57、二叉查找树，如若不然，假设也是最优二叉查找树，如若不然，假设T(1, k- -1)是是比比T(1, k- -1)更优的二叉查找树，则更优的二叉查找树，则T(1, k- -1)的平均比较次数小的平均比较次数小于于T(1, k- -1)的平均比较次数，从而由的平均比较次数，从而由T(1, k- -1)、rk和和T(k+1, n)构构成的二叉查找树成的二叉查找树T(1, n)的平均比较次数小于的平均比较次数小于T(1, n)的平均比较的平均比较次数，这与次数，这与T(1, n)是最优二叉查找树的假设相矛盾。因此最优是最优二叉查找树的假设相矛盾。因此最优二叉查找树满足最优性原理。二叉查找树满足最优性原

58、理。 48rkT(1, n)图7 以rk为根的二叉查找树T(k+1,n)T(1,k- -1) 设T(i, j)是由记录ri, , rj(1ijn)构成的二叉查找树，C(i, j)是这棵二叉查找树的平均比较次数。虽然最后的结果是C(1, n)，但遵循动态规划法的求解方法,需要求出所有较小子问题C(i, j)的值，考虑从ri, , rj中选择一个记录rk作为二叉查找树的根结点，可以得到如下关系： ), 1() 1,(min), 1() 1,(min), 1() 1,(min ) 1), 1() 1) 1,(1min),(11111111jissjkijisskisjksssssjkijksskisjkssskisssskjkikisjkssssskjkipjkCkiCpnkTrpkiTrppnkTrppkiTrppnkTrpkiTrppjiC中的层数在中的层数在中的层数在中的层数在中的层数在中的层数在49 因此，得到如下动态规划函数：因此，得到如下动态规划函数： C(i, i-1)=0 (1in+1) （式（