《背包问题之动态规划法ppt课件》由会员分享，可在线阅读，更多相关《背包问题之动态规划法ppt课件（54页珍藏版）》请在金锄头文库上搜索。
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划划分分成成k个个互互不不
2、相相交交的的子子集集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的最短路径记为的最短路径记为d(s,t)，则从源点，则从源点0到终点到终点9的的最短
5、路径最短路径d(0,9)由下式确定：由下式确定：d d(0, (0, 9)=min9)=minc c0101+ +d d(1, (1, 9), 9), c c0202+ +d d(2, (2, 9), 9), c c0303+ +d d(3, (3, 9)9)这这是是最最后后一一个个阶阶段段的的决决策策，它它依依赖赖于于d d(1, (1, 9)9)、d d(2, 9)(2, 9)和和d d(3, 9)(3, 9)的计算结果，而的计算结果，而d d(1, 9)=min(1, 9)=minc c1414+ +d d(4, 9), (4, 9), c c1515+ +d d(5, 9)(5, 9)
6、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)这这一一阶阶段段的的决决策策依依赖赖于于d(7,9)和和d(8,9)的的计计算算，而而d(7,9)和和d(8,9)可以直接获得（括号中给出了决策产生的状态转
7、移）：可以直接获得（括号中给出了决策产生的状态转移）：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,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),c
8、26+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算法、广度算法、广度优先搜索算法，都渗透着动态规划的思想。优先搜索算法，都渗透着动态规划的思想。因此，动态规划不像深度或广度优先那样可以提因此，动态规划不像深度或广度优先那样可以提供一套模式，需要的时候，取来就可以使用；它必须供一套模式，需要的时候，取来就可以使用；它必须对具体问题进行具体分析处理，需要丰富的想象力去对具体问题进行具体分析处理，需要丰富的想象力去建立模型，需要创造性的思想去求解。建立模型，需要创造性的思想去求解。10 准确地说，动态规划不是万能的，它只适于解决准确地说，动态规划不是万能的，它只适于解决一定条
11、件的最优策略问题。一定条件的最优策略问题。 或许，大家听到这个结论或许，大家听到这个结论会很失望：其实，这个结论并没有削减动态规划的光辉，会很失望：其实，这个结论并没有削减动态规划的光辉，因为属于上面范围内的问题极多，还有许多看似不是这因为属于上面范围内的问题极多，还有许多看似不是这个范围中的问题都可以转化成这类问题。个范围中的问题都可以转化成这类问题。 上面所说的上面所说的“满足一定条件满足一定条件”主要指下面两点：主要指下面两点： (1)状状态必必须满足最足最优化原理化原理； (2)状状态必必须满足无后效性足无后效性。 这条特征说明什么呢这条特征说明什么呢?它说明动态规划适于解决当前它说明
12、动态规划适于解决当前决策和过去状态无关的问题。状态，出现在策略的任何决策和过去状态无关的问题。状态，出现在策略的任何一个位置，它的地位都是相同的，都可以实施同样的决一个位置，它的地位都是相同的，都可以实施同样的决策。这就是无后效性的内涵。策。这就是无后效性的内涵。 1.3 动态规划适于解决什么样的问题动态规划适于解决什么样的问题 11作作为为整整个个过过程程的的最最优优策策略略具具有有如如下下性性质质：无无论论过过去去的的状状态态和和决决策策如如何何，对对前前面面的的决决策策所所形形成成的的当当前前状状态态而而言，余下的诸决策必须构成最优策略。言，余下的诸决策必须构成最优策略。可可以以通通俗俗
13、地地理理解解为为子子问问题题的的局局部部最最优优将将导导致致整整个个问问题题的的全全局局最最优优，即即问问题题具具有有最最优优子子结结构构的的性性质质，也也就就是是说说一一个个问问题题的的最最优优解解只只取取决决于于其其子子问问题题的的最最优优解解，非非最最优优解解对对问问题题的的求求解解没没有有影影响响。在在 例例题题1 1 最最短短路路径径问问题题中中，A A到到E E的的最最优优路路径径上上的的任任一一点点到到终终点点E E的的路路径径也也必必然然是是该该点点到到终终点点E E的的一一条条最最优优路路径径，满满足足最最优优化化原原理理。下面来讨论另外一个问题。下面来讨论另外一个问题。1.
14、4 最优性原理最优性原理 12例例题 余数最少的路径余数最少的路径 如图所示，有如图所示，有4个点，分个点，分别是别是A、B、C、D，相邻两，相邻两点用两条连线点用两条连线 C2k，C2k-1(1k3)表示两条通行的道路。连线表示两条通行的道路。连线上的数字表示道路的长度。上的数字表示道路的长度。定义从定义从A到到D的所有路径中，的所有路径中，长度除以长度除以4所得余数最小的所得余数最小的路径为最优路径。路径为最优路径。 求一条最优路径。求一条最优路径。13【分析】在【分析】在这个个问题中，如果中，如果还按照例按照例题1中的方法去中的方法去求解就会发生错误。按照例题求解就会发生错误。按照例题1
15、的思想，的思想，A的最优取值可的最优取值可以由以由B的最优取值来确定，而的最优取值来确定，而B的最优取值为的最优取值为(1+3) mod 4 = 0，所以，所以A的最优值应为的最优值应为2，而实际上，路径，而实际上，路径C1C3C5可得最优值为可得最优值为(2+1+1) mod 4 = 0，所以，所以，B的最的最优路径并不是优路径并不是A的最优路径的子路径，也就是说，的最优路径的子路径，也就是说，A的的最优取值不是由最优取值不是由B的最优取值决定的，即其不满足最优的最优取值决定的，即其不满足最优化原理，问题不具有最优子结构的性质。化原理，问题不具有最优子结构的性质。 由此可见，并不是所有的由此
16、可见，并不是所有的“决策问题决策问题”都可以用都可以用“动动态规划态规划”来解决，运用来解决，运用“动态规划动态规划”来处理问题来处理问题必必须满足足最最优化原理。化原理。14所谓无后效性原则，指的是这样一种性质：所谓无后效性原则，指的是这样一种性质：某某阶阶段段的的状状态态一一旦旦确确定定，则则此此后后过过程程的的演演变变不不再再受受此此前前各各状状态态及及决决策策的的影影响响。也也就就是是说说，“未未来来与与过过去去无无关关”，当当前前的的状状态态是是此此前前历历史史的的一一个个完完整整总总结结，此此前前的的历历史史只只能能通通过过当当前前的的状状态态去去影影响响过过程程未未来来的的演演变
17、变。具具体体地地说说，如如果果一一个个问问题题被被划划分分各各个个阶阶段段之之后后，阶阶段段 I I 中中的的状状态态只只能能由由阶阶段段 I+1 I+1 中中的的状状态态通通过过状状态态转转移移方方程程得得来来，与与其其他他状状态态没没有有关关系系，特特别别是是与与未未发发生的状态没有关系，这就是无后效性。生的状态没有关系，这就是无后效性。1.5 无后效性原则无后效性原则151.6动态规划法的设计思想动态规划法的设计思想动态规划法将待求解问题分解成若干个相互重叠的子问动态规划法将待求解问题分解成若干个相互重叠的子问题，每个子问题对应决策过程的一个阶段，一般来说，题，每个子问题对应决策过程的一
18、个阶段，一般来说，子问题的重叠关系表现在对给定问题求解的递推关系子问题的重叠关系表现在对给定问题求解的递推关系（也就是动态规划函数）中，将子问题的解求解一次并（也就是动态规划函数）中，将子问题的解求解一次并填入表中，当需要再次求解此子问题时，可以通过查表填入表中，当需要再次求解此子问题时，可以通过查表获得该子问题的解而不用再次求解，从而避免了大量重获得该子问题的解而不用再次求解，从而避免了大量重复计算。为了达到这个目的，可以用一个表来记录所有复计算。为了达到这个目的，可以用一个表来记录所有已解决的子问题的解，这就是动态规划法的设计思想。已解决的子问题的解，这就是动态规划法的设计思想。具体的动态
19、规划法是多种多样的，但他们具有相同的填具体的动态规划法是多种多样的，但他们具有相同的填表形式。表形式。16原问题的解原问题的解原问题原问题图图2动态规划法的求解过程动态规划法的求解过程填填表表子问题子问题1子问题子问题2子问题子问题n17一、划分阶段：一、划分阶段：按照问题的时间或空间特征，把问题分为若干个阶段。按照问题的时间或空间特征，把问题分为若干个阶段。二、选择状态：二、选择状态：将问题发展到各个阶段时所处于的各种客观情况用不同将问题发展到各个阶段时所处于的各种客观情况用不同的状态表示出来。的状态表示出来。三、确定决策并写出状态转移方程：三、确定决策并写出状态转移方程：状态转移就是根据上
20、一阶段的状态和决策来导出本阶段状态转移就是根据上一阶段的状态和决策来导出本阶段的状态。的状态。四、写出规划方程（包括边界条件）：四、写出规划方程（包括边界条件）：动态规划的基本方程是规划方程的通用形式化表达式。动态规划的基本方程是规划方程的通用形式化表达式。动态规划算法的基本步骤动态规划算法的基本步骤18可以用动态规划法求解的问题除了能够分解为相互重叠的可以用动态规划法求解的问题除了能够分解为相互重叠的若干子问题外，还要满足最优性原理（也称最优子结构性若干子问题外，还要满足最优性原理（也称最优子结构性质），这类问题具有如下特征：该问题的最优解中也包含质），这类问题具有如下特征：该问题的最优解中
21、也包含着其子问题的最优解。在分析问题是否满足最优性原理时，着其子问题的最优解。在分析问题是否满足最优性原理时，通常先假设由问题的最优解导出的子问题的解不是最优的，通常先假设由问题的最优解导出的子问题的解不是最优的，然后再设法说明在这个假设下可构造出比原问题最优解更然后再设法说明在这个假设下可构造出比原问题最优解更好的解，从而导致矛盾。好的解，从而导致矛盾。动动态态规规划划法法利利用用问问题题的的最最优优性性原原理理，以以自自底底向向上上的的方方式式从从子子问问题题的的最最优优解解逐逐步步构构造造出出整整个个问问题题的的最最优优解解。应应用用动态规划法设计算法一般分成三个阶段：动态规划法设计算法
22、一般分成三个阶段：（1 1）分段：将原问题分解为若干个相互重叠的子问题；）分段：将原问题分解为若干个相互重叠的子问题；（2 2）分分析析：分分析析问问题题是是否否满满足足最最优优性性原原理理，找找出出动动态态规规划划函数的递推式；函数的递推式；（3 3）求解：利用递推式自底向上计算，实现动态规划过程。）求解：利用递推式自底向上计算，实现动态规划过程。 192. 组合问题中的动态规划法组合问题中的动态规划法 2.1 0/12.1 0/1背包问题背包问题 2.2 2.2 最长公共子序列问题最长公共子序列问题202.10/1背包问题背包问题给给定定n种种物物品品和和一一个个背背包包，物物品品i的的重
23、重量量是是wi，其其价价值值为为vi，背背包包的的容容量量为为C。背背包包问问题题是是如如何何选选择择装装入入背背包包的的物物品品，使使得得装装入入背背包包中中物物品品的的总总价价值值最最大大?如如果果在在选选择择装装入入背背包包的的物物品品时时，对对每每种种物物品品i只只有有两两种种选选择择：装装入入背背包包或或不不装装入入背背包包，即即不不能能将将物物品品i装装入入背背包包多多次次，也也不不能能只只装装入入物物品品i的的一一部部分分，则则称称为为0/1背包问题。背包问题。21在在0/1背背包包问问题题中中，物物品品i或或者者被被装装入入背背包包，或或者者不不被被装装入入背背包包，设设xi表
24、表示示物物品品i装装入入背背包包的的情情况况，则则当当xi=0时时，表表示示物物品品i没没有有被被装装入入背背包包，xi=1时时，表表示示物物品品i被被装装入入背背包包。根根据据问问题题的的要要求求，有有如如下下约约束束条条件件和和目标函数：目标函数：（式（式1）（式（式2）问问题题归归结结为为寻寻找找一一个个满满足足约约束束条条件件式式1，并并使使目目标标函数式函数式2达到最大的解向量达到最大的解向量X=(x1,x2,xn)。22首先证明首先证明0/1背包问题满足最优性原理。背包问题满足最优性原理。设设(x1,x2,xn)是是所所给给0/1背背包包问问题题的的一一个个最最优优解，则解，则(x
25、2,xn)是下面一个子问题的最优解：是下面一个子问题的最优解：如若不然，设如若不然，设(y2,yn)是上述子问题的一个最优解，是上述子问题的一个最优解，则则 ，且，且 。因此，。因此， ，这说明，这说明(x1,y2,yn)是所给是所给0/1背包问题比背包问题比(x1,x2,xn)更优的解，从而导致矛更优的解，从而导致矛盾。盾。230/1背包问题可以看作是决策一个序列背包问题可以看作是决策一个序列(x1,x2,xn)，对任一变量对任一变量xi的决策是决定的决策是决定xi=1还是还是xi=0。在对。在对xi-1决策后，决策后，已确定了已确定了(x1,xi-1)，在决策，在决策xi时，问题处于下列两
26、种时，问题处于下列两种状态之一：状态之一：a.背包容量不足以装入物品背包容量不足以装入物品i，则，则xi=0背包不增加价值；背包不增加价值；b.背包容量可以装入物品背包容量可以装入物品i，则，则xi=1背包的价值增加了背包的价值增加了vi。这这两两种种情情况况下下背背包包价价值值的的最最大大者者应应该该是是对对xi决决策策后后的的背背包包价价值值。令令V(i, j)表表示示在在前前i(1in)个个物物品品中中能能够够装装入入容容量量为为j（1jC）的的背背包包中中的的物物品品的的最最大大值值，则则可可以以得得到到如如下下动态规划函数：动态规划函数： V(i,0)= V(0,j)=0（式（式3）
27、24式式3表明：把前面表明：把前面i个物品装入容量为个物品装入容量为0的背包和把的背包和把0个物品装入个物品装入容量为容量为j的背包，得到的价值均为的背包，得到的价值均为0。式。式4的第一个式子表明：如的第一个式子表明：如果第果第i个物品的重量大于背包的容量，则装入前个物品的重量大于背包的容量，则装入前i个物品得到的个物品得到的最大价值和装入前最大价值和装入前i- -1个物品得到的最大价值是相同的，即物品个物品得到的最大价值是相同的，即物品i不能装入背包；第二个式子表明：如果第不能装入背包；第二个式子表明：如果第i个物品的重量小于背个物品的重量小于背包的容量，则会有以下两种情况：（包的容量，则
28、会有以下两种情况：（1）如果把第）如果把第i个物品装入个物品装入背包，则背包中物品的价值等于把前背包，则背包中物品的价值等于把前i- -1个物品装入容量为个物品装入容量为j- -wi的背包中的价值加上第的背包中的价值加上第i个物品的价值个物品的价值vi；（；（2）如果第）如果第i个物品个物品没有装入背包，则背包中物品的价值就等于把前没有装入背包，则背包中物品的价值就等于把前i- -1个物品装入个物品装入容量为容量为j的背包中所取得的价值。显然，取二者中价值较大者作的背包中所取得的价值。显然，取二者中价值较大者作为把前为把前i个物品装入容量为个物品装入容量为j的背包中的最优解。的背包中的最优解。
29、（式（式4）25第一阶段第一阶段，只装入前，只装入前1个物品，确定在各种情况下的背包能够得个物品，确定在各种情况下的背包能够得到的最大价值；到的最大价值；第二阶段第二阶段，只装入前，只装入前2个物品，确定在各种情况下的背包能够得个物品，确定在各种情况下的背包能够得到的最大价值；依此类推，直到第到的最大价值；依此类推，直到第n个阶段。个阶段。最后最后，V(n,C)便是在容量为便是在容量为C的背包中装入的背包中装入n个物品时取得的最大个物品时取得的最大价值。为了确定装入背包的具体物品，从价值。为了确定装入背包的具体物品，从V(n,C)的值向前推，如的值向前推，如果果V(n,C)V(n- -1,C)
30、，表明第，表明第n个物品被装入背包，前个物品被装入背包，前n- -1个物品被个物品被装入容量为装入容量为C- -wn的背包中；否则，第的背包中；否则，第n个物品没有被装入背包，个物品没有被装入背包，前前n- -1个物品被装入容量为个物品被装入容量为C的背包中。依此类推，直到确定第的背包中。依此类推，直到确定第1个物品是否被装入背包中为止。由此，得到如下函数：个物品是否被装入背包中为止。由此，得到如下函数：（式（式5）26例如，有例如，有5个物品，其重量分别是个物品，其重量分别是2,2,6,5,4，价值，价值分别为分别为6,3,5,4,6，背包的容量为，背包的容量为10，求装入背包，求装入背包的
31、物品和获得的最大价值。的物品和获得的最大价值。根据动态规划函数，用一个根据动态规划函数，用一个(n+1)(C+1)的二维表的二维表V，Vij表示把前表示把前i个物品装入容量为个物品装入容量为j的背包中获得的最大价的背包中获得的最大价值，根据式值，根据式3把表的第把表的第0行和第行和第0列初始化为列初始化为0，然后一行一，然后一行一行地计算行地计算Vij，如图，如图3所示。所示。27x5=1x4=0x3=0x2=1x1=10123456789 1000000000000w1=2v1=6100666666666w2=2v2=3200669999999w3=6v3=5300669999111114w
32、4=5v4=44006699910111314w5=5v5=6500669912 12151515可可以以看看到到，装装入入背背包包的的物物品品的的最最大大价价值值是是15，根根据据式式5，装装入背包的物品为入背包的物品为X=1,1,0,0,1。图3 0/1背包求解（填表）过程28设设n个个物物品品的的重重量量存存储储在在数数组组wn中中，价价值值存存储储在在数数组组vn中中，背背包包容容量量为为C，数数组组Vn+1C+1存存放放迭迭代代结结果果，其其中中Vij表表示示前前i个个物物品品装装入入容容量量为为j的的背背包包中中获获得得的的最最大大价价值值，数数组组xn存存储储装装入入背背包包的的
33、物物品品，动动态态规规划法求解划法求解0/1背包问题的算法如下：背包问题的算法如下：29算法算法10/1背包问题背包问题intKnapSack(intn,intw,intv)for(i=0;i=n;i+)/初始化第初始化第0列列Vi0=0;for(j=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;elsexi=0;returnVnC;/返回背包取得的最大价值返回背包取得的最大价值 302.2最长公共子序列问题最长
34、公共子序列问题对对给给定定序序列列X=(x1,x2,xm)和和序序列列Z=(z1,z2,zk)，Z是是X的的子子序序列列当当且且仅仅当当存存在在一一个个严严格格递递增增下下标标序序列列(i1,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,
35、3,4,5,7)。可见，一个给定序列的子序列可以有多个。可见，一个给定序列的子序列可以有多个。 给定两个序列给定两个序列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的公共子序列。最长公共子序列问题就是在序列的公共子序列
36、。最长公共子序列问题就是在序列X和和Y的公共子序列中查找长度最长的公共子序列。的公共子序列中查找长度最长的公共子序列。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的最长公共子序列；
37、的最长公共子序列；（2）若）若xmyn且且zkxm，则，则Z是是Xm-1和和Y的最长公共子序列；的最长公共子序列；（3）若）若xmyn且且zkyn，则，则Z是是X和和Yn-1的最长公共子序列。的最长公共子序列。可可见见，两两个个序序列列的的最最长长公公共共子子序序列列包包含含了了这这两两个个序序列列的的前前缀缀序序列列的的最长公共子序列。因此，最长公共子序列问题满足最优性原理。最长公共子序列。因此，最长公共子序列问题满足最优性原理。要要找找出出序序列列X=x1,x2,xm和和Y=y1,y2,yn的的最最长长公公共共子子序序列列，可按下述递推方式计算：当可按下述递推方式计算：当xm=yn时，找出
38、时，找出Xm-1和和Yn-132的最长公共子序列，然后在其尾部加上的最长公共子序列，然后在其尾部加上xm即可得到即可得到X和和Y的最长的最长公共子序列；当公共子序列；当xmyn时，必须求解两个子问题：找出时，必须求解两个子问题：找出Xm-1和和Y的最长公共子序列以及的最长公共子序列以及Xm和和Yn-1的最长公共子序列，这两个公共的最长公共子序列，这两个公共子序列中的较长者即为子序列中的较长者即为X和和Y的最长公共子序列。用的最长公共子序列。用Lij表示子表示子序列序列Xi和和Yj的最长公共子序列的长度，可得如下动态规划函数：的最长公共子序列的长度，可得如下动态规划函数：L00=Li0=L0j=
39、0(1L00=Li0=L0j=0(1i im,1m,1j jn) n) （式（式6 6） （式（式7 7） 由此，把序列由此，把序列X=x1,x2,xm和和Y=y1,y2,yn的最长的最长公共子序列的搜索分为公共子序列的搜索分为m个阶段，第个阶段，第1阶段，按照式阶段，按照式7计算计算X1和和Yj的最长公共子序列长度的最长公共子序列长度L1j（1jn），第），第2阶段，按照式阶段，按照式7计算计算X2和和Yj的最长公共子序列长度的最长公共子序列长度L2j（1jn），依此类推，），依此类推，最后在第最后在第m阶段，计算阶段，计算Xm和和Yj的最长公共子序列长度的最长公共子序列长度Lmj（1jn）
40、，则），则Lmn就是序列就是序列Xm和和Yn的最长公共子序的最长公共子序列的长度。列的长度。33 为了得到序列为了得到序列Xm和和Yn具体的最长公共子序列，设二维表具体的最长公共子序列，设二维表Sm+1n+1，其中，其中Sij表示在计算表示在计算Lij的过程中的搜索状态，的过程中的搜索状态，并且有：并且有：若若Sij=1，表明，表明ai=bj，则下一个搜索方向是，则下一个搜索方向是Si- -1j- -1；若若Sij=2，表明，表明aibj且且Lij- -1Li- -1j，则下一个搜索方向是，则下一个搜索方向是Sij- -1；若若Sij=3，表明，表明aibj且且Lij- -1Li- -1j，则
41、下一个搜索方向，则下一个搜索方向是是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中。计算结果如图中。计算结果如图4所所示。示。34(a)长度矩度矩阵L(b)状状态矩矩阵S图4最最长公共子序列求解示意公共子序列求解示意图01
42、234567890123456789000000000000000000000101111111111012221222220112222222203211212113012222222230312222222401233333334033113131150123333444503332221226012344445560331131211353.图问题中的动态规划法图问题中的动态规划法3.1TSP问题问题3.2多段图的最短路径问题多段图的最短路径问题363.1TSP问题问题TSP问题是指旅行家要旅行是指旅行家要旅行n个城市，要个城市，要求各个城市求各个城市经历且且仅经历一次然后回到一次然后回
43、到出出发城市，并要求所走的路程最短。城市，并要求所走的路程最短。各个城市各个城市间的距离可以用代价矩的距离可以用代价矩阵来表来表示，如果示，如果(i,j)E，则cij。37假设从顶点假设从顶点i出发，令出发，令d(i,V)表示从顶点表示从顶点i出发经过出发经过V中各个顶点一次且仅一次，最后回到出发点中各个顶点一次且仅一次，最后回到出发点i的最短路的最短路径长度，开始时，径长度，开始时，VVi，于是，于是，TSP问题的动问题的动态规划函数为：态规划函数为：d(i,V)=mincik+d(k,Vk)(kV)（式（式8）d(k,)=cki(ki)（式（式9）38从城市从城市0出发，经城市出发，经城市
44、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)的计算结果，而：的计算结果，而：39d(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)这一阶段的决策又依赖于下面的计算结果：这一阶段的决策又依赖
45、于下面的计算结果：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,)而而下下式式可可以以直直接接获获得得（括括号号中中是是该该决决策策引引起起的的状状态态转转移移）：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
46、+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,)=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,
47、3)=minc01+ d(1,2,3),c02+ d(2,1,3),c03+ d(3,1,2)=min3+7,6+10,7+14=10(01)从从顶顶点点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=
48、4n=4时，时，V1=1, V2=2, V3=3, V4=1, 2, V5=1, 3, V1=1, V2=2, V3=3, V4=1, 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
49、所示。所示。ji1231,21,32,31,2,30101586726951033121114图5动态规划法的填表过程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
50、-1=min(c0k+dk2n-1- -2);4输出最短路径长度输出最短路径长度d02n-1- -1;算法算法2的时间复杂性为的时间复杂性为O(2n)。和蛮力法相比，动态规划法求。和蛮力法相比，动态规划法求解解TSP问题，把原来的时间复杂性是问题，把原来的时间复杂性是O(n!)的排列问题，转的排列问题，转化为组合问题，从而降低了算法的时间复杂性，但它仍需要化为组合问题，从而降低了算法的时间复杂性，但它仍需要指数时间。指数时间。44454. 查找问题中的动态规划法查找问题中的动态规划法4.1最优二叉查找树最优二叉查找树4.2近似串匹配问题近似串匹配问题46 设设r1,r2,rn是是n个个记记录录
51、的的集集合合，其其查查找找概概率率分分别别是是p1, p2, , pn，最最优优二二叉叉查查找找树树（Optimal BinarySearchTrees）是是以以这这n个个记记录录构构成成的的二二叉叉查查找找树树中中具具有有最最少少平平均均比比较较次次数数的的二二叉叉查查找找树树，即即 最最小小，其其中中pi是是记记录录ri的查找概率，的查找概率，ci是在二叉查找树中查找是在二叉查找树中查找ri的比较次数。的比较次数。 例例如如，集集合合 A A, , B B, , C C, , D D 的的查查找找概概率率是是0.1, 0.1, 0.2, 0.2, 0.4, 0.4, 0.30.3，图图6.
52、116.11给给出出了了三三棵棵二二叉叉查查找找树树，在在查查找找成成功功的的情情况况下下，二二叉叉查查找找树树(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.13 30.20.22+0.42+0.41+0.31+0.32=1.72=1.7。 4.1最优二叉查找树最优二叉
53、查找树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)也是最优二叉查找树，如若不然，假设也是最优二叉查找树，如若不然，假设T(1,k- -1)是是比比T
54、(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)是最优二叉查找树的假设相矛盾。因此最优二是最优二叉查找树的假设相矛盾。因此最优二叉查找树满足最优性原理。叉查找树满足最优性原理。48rkT(1,n)图7以rk为根的二叉查找树T(k+1,n)T(1,k- -1) 设T(i,j)是由记
55、录ri,rj(1ijn)构成的二叉查找树，C(i,j)是这棵二叉查找树的平均比较次数。虽然最后的结果是C(1,n)，但遵循动态规划法的求解方法,需要求出所有较小子问题C(i,j)的值，考虑从ri,rj中选择一个记录rk作为二叉查找树的根结点，可以得到如下关系：49 因此，得到如下动态规划函数：因此，得到如下动态规划函数：C(i,i-1)=0(1in+1)（式（式10）C(i,i)=pi (1in)（式（式11）C(i,j)=minC(i,k-1)+C(k+1,j)+(1ijn,ikj)（式（式12）式式10解解释释为为空空树树的的比比较较次次数数为为0，式式11解解释释为为只只包包含含记记录录
56、ri的的二二叉叉查查找找树树。设设一一个个二二维维表表Cn+1n+1，其其中中Cij表表示示二二叉叉查查找找树树T(i,j)的的平平均均比比较较次次数数。注注意意到到在在式式12中中，当当k=1时时，求求 Cij需需 要要 用用 到到 Ci0， 当当 k=n时时 ， 求求 Cij需需 要要 用用 到到Cn+1j，所所以以，二二维维表表Cn+1n+1行行下下标标的的范范围围为为1n+1，列列下下标标的的范范围围为为0n。为为了了在在求求出出由由r1,r2,rn构构成成的的二二叉叉查查找找树树的的平平均均比比较较次次数数的的同同时时得得到到最最优优二二叉叉查查找找树树，设设一一个个二二维维表表Rn
57、+1n+1，其其下下标标范范围围与与二二维维表表C相相同同，Rij表表示示二二叉叉查找树查找树T(i,j)的根结点的序号。的根结点的序号。50 例例如如，集集合合A,B,C,D的的查查找找概概率率是是0.1,0.2,0.4,0.3，二维表，二维表C和和R的初始情况如图的初始情况如图8所示。所示。(a)二维表二维表C(b)二维表二维表R图图8初始表的状态初始表的状态01234100.1200.2300.4400.35001234112233445 在二维表在二维表C和和R中只需计算主对角线以上的元素，首中只需计算主对角线以上的元素，首先计算先计算C(1,2)：51 因此，在前两个记录构成的最优二
58、叉查找树的根结点的因此，在前两个记录构成的最优二叉查找树的根结点的序号是序号是2，按对角线逐条计算每一个，按对角线逐条计算每一个C(i,j)和和R(i,j)，得到如，得到如图图9所示的最终表。所示的最终表。01234100.10.41.11.7200.20.81.4300.41.0400.35001234112332233333445(a)二维表二维表C(b)二维表二维表R图图9最终表的状态最终表的状态d=1d=2d=3d=1d=2d=352适用条件适用条件动态规划法的有效性依赖于问题本身所具动态规划法的有效性依赖于问题本身所具 有的两个重要有的两个重要的适用性质的适用性质1.最优子结构最优子
59、结构 如果问题的最优解是由其子问题的最优解来构造，如果问题的最优解是由其子问题的最优解来构造，则称则称 该问题具有最优子结构性质。该问题具有最优子结构性质。2.重叠子问题重叠子问题 在用递归算法自顶向下解问题时，每次产生的子问在用递归算法自顶向下解问题时，每次产生的子问题并不总是新问题，有些子问题被反复计算多次。动态题并不总是新问题，有些子问题被反复计算多次。动态规划规划 算法正是利用了这种子问题的重叠性质，对每一个算法正是利用了这种子问题的重叠性质，对每一个子问子问 题只解一次，而后将其解保存在一个表格中，在以题只解一次，而后将其解保存在一个表格中，在以后该后该 子问题的求解时直接查表。子问
60、题的求解时直接查表。53动态规划的思想实质是分治思想和解决冗余。动态规划的思想实质是分治思想和解决冗余。与分治法类似的与分治法类似的是将原问题分解成若干个子问题，是将原问题分解成若干个子问题，先求解子问题，然后从先求解子问题，然后从 这些子问题的解得到原问题这些子问题的解得到原问题的解。的解。与分治法不同的与分治法不同的是经分解的子问题往往不是互相独是经分解的子问题往往不是互相独立的。若用分治法来立的。若用分治法来 解，有些共同部分（子问题或解，有些共同部分（子问题或子子问题）被重复计算了子子问题）被重复计算了 很多次。很多次。如果能够保存已解决的子问题的答案，在需要时再如果能够保存已解决的子问题的答案，在需要时再查找，这样就可以避免重复计算、节省时间。动态查找，这样就可以避免重复计算、节省时间。动态规划法用一个表来记录所有已解的子问题的答案。规划法用一个表来记录所有已解的子问题的答案。这就是动态规划法的基本思路。具体的动态规划算这就是动态规划法的基本思路。具体的动态规划算法多种多样，但它们具有相同的填表方式。法多种多样，但它们具有相同的填表方式。54
