第6章 动态规划法ppt课件.ppt

1,第6章 动态规划法,教学内容动态规划的定义及历史动态规划求解问题的步骤动态规划计算二项式系数图问题中的动态规划法组合问题中的动态规划法组合问题中的动态规划法要求掌握动态规划的思想及文体求解步骤，掌握动态规划求解常见问题如：每对节点间的最短距离、最优二分检索树、背包问题等中的应用。,第6章 动态规划法,6.5 实验项目最大子段和问题,6.4 查找问题中的动态规划法,6.3 组合问题中的动态规划法,6.1 概 述,6.2 图问题中的动态规划法,6.1 概 述,6.1.1 最优化问题,6.1.2 最优性原理,6.1.3 动态规划法的设计思想,约束条件：有n个输入，它的解由这n个输入的一个子集组成，这个子集必须满足某些事先给定的条件，这些条件称为约束条件可行解：满足约束条件的解称为问题的可行解目标函数：满足约束条件的可行解可能不只一个，为了衡量这些可行解的优劣，事先给出一定的标准，这些标准通常以函数的形式给出，这些标准函数称为目标函数最优解：使目标函数取得极值（极大或极小）的可行解称为最优解最优化问题：这类问题就称为最优化问题,6.1.1 最优化问题,什么是最优化问题？,例：自动柜员机（POS机）付款问题：超市的自动柜员机（POS机）要找给顾客数量最少的现金。 假定POS机中有n张面值为pi(1in)的货币，用集合P=p1, p2, , pn表示，如果POS机需支付的现金为A，那么，它必须从P中选取一个最小子集S，使得 （式6.1）,向量X=( x1, x2, , xn)表示S中所选取的货币，则 （式6.2）,POS机支付的现金必须满足 （式6.3）,并且 （式6.4）,集合P：问题的输入可行解：满足式6.1的解称为可行解解的表现形式：式6.2是解的表现形式，因为向量X中有n个元素，每个元素的取值为0或1，所以，可以有2n个不同的向量，所有这些向量的全体构成该问题的解空间约束条件：式6.3是该问题的约束条件目标函数：式6.4是该问题的目标函数最优解：使式6.4取得极小值的解称为该问题的最优解,6.1.2 最优性原理,多阶段决策： 对于一个具有n个输入的最优化问题，其求解过程往往可以划分为若干个阶段 每一阶段的决策仅依赖于前一阶段的状态，由决策所采取的动作使状态发生转移，成为下一阶段决策的依据 一个决策序列在不断变化的状态中产生,分析最优化问题！, School of Computer Science and Technology, SWUST,9,最优性原理(Principle of Optimality)无论过程的初始状态和初始决策是什么，其余的决策都必须相对于初始决策所产生的状态构成一个最优决策序列。原理告诉我们，一个最优问题的任何实例的最优解是由该实例的子实例的最优解组成的。重要结论： 一般来说，如果所求解问题对于最优性原理成立，则说明用动态规划方法有可能解决该问题。 而解决问题的关键在于获取各阶段问的递推关系式（动态规划函数）。,6.1.3 动态规划法的设计思想,将原问题分解为若干个子问题，先求子问题的解，然后从这些子问题的解得到原问题的解。这些子问题的解往往不是相互独立的。在求解的过程中，许多子问题的解被反复地使用。为了避免重复计算，动态规划算法采用了填表来保存子问题解的方法。在算法中用表格来保存已经求解的子问题的解，无论它是否会被用到。当以后遇到该子问题时即可查表取出其解，避免了重复计算。,动态规划法的求解过程,分治法：n=5时计算斐波那契数的过程,例：计算斐波那契数：,求解斐波那契数F(9)的填表过程 ：,动态规划法：分析：计算F(n)是以计算它的两个重叠子问题 F(n-1)和F(n-2)的形式来表达的，所以，可以设计一张表填入n+1个F(n)的值。,动态规划的基本要素,最优子结构：问题的最优解是由其子问题的最优解所构成的。重叠子问题：子问题之间并非相互独立的，而是彼此有重叠的。,最优子结构性质使我们能够以自底向上的方式递归地从子结构的最优解构造出问题的最优解。,因为子问题重叠，所以存在着重复计算。这样就可以用填表保存子问题解的方法来提高效率。,如何证明问题是否满足最优性原理？用反证法！ 先假设由问题的最优解导出的子问题的解不是最优的; 然后再证明在这个假设下可构造出比原问题最优解更好的解，从而导致矛盾。,动态规划的基本方法,动态规划通常可以按以下几个步骤进行：(1)找出最优解的性质，并刻画其结构特征；(2)递归地定义最优值；(3)以自底向上的方式计算出各子结构的最优值并添入表格中保存；(4)根据计算最优值时得到的信息，构造最优解。步骤13是动态规划算法的基本步骤。若需要最优解，则必须执行第4步，为此还需要在第3步中记录构造最优解所必需的信息。,6.2 图问题中的动态规划法,6.2.1 TSP问题,6.2.2 多段图的最短路径问题,6.2.1 TSP问题,TSP问题：旅行家要旅行n个城市，要求各个城市经历且仅经历一次然后回到出发城市，并要求所走的路程最短。 各个城市间的距离可以用代价矩阵来表示。,0,3,2,1,设s, s1, s2, , sp, s是从s出发的一条路径长度最短的简单回路，假设从s到下一个城市s1已经求出，则问题转化为求从s1到s的最短路径，显然s1, s2, , sp, s一定构成一条从s1到s的最短路径。 如若不然，设s1, r1, r2, , rq, s是一条从s1到s的最短路径且经过n-1个不同城市，则s, s1, r1, r2, , rq, s将是一条从s出发的路径长度最短的简单回路且比s, s1, s2, , sp, s要短，从而导致矛盾。 所以，TSP问题满足最优性原理。,证明TSP问题满足最优性原理,构造动态规划函数： 假设从顶点i出发，令d(i, V)表示从顶点i出发经过V中各个顶点一次且仅一次，最后回到出发点i的最短路径长度 开始时，VVi， 于是，TSP问题的动态规划函数为： d(i,V)=mincik+d(k,Vk)(kV) （式6.5） d(k,)=cki(ki) （式6.6）,这一阶段的决策又依赖于下面的计算结果：d(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, ),最后一个阶段的决策：从城市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, )=c10=5(10) d(2, )=c20=6(20) d(3, )=c30=3(30),再向前倒推，有：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, )=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),d(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(01) 所以，从顶点0出发的TSP问题的最短路径长度为10，路径是01230。,假设n个顶点用0n-1的数字编号，首先生成1n-1个元素的子集存放在数组V2n-1中，设数组dn2n-1存放迭代结果，其中dij表示从顶点i经过子集Vj中的顶点一次且仅一次，最后回到出发点0的最短路径长度。,动态规划法求解TSP问题的填表过程,0,3,2,1,算法6.1的时间复杂性为O(2n)。蛮力法求解TSP问题:时间复杂性是O(n!),算法描述 设顶点之间的代价存放在数组cnn中,25,6.2.2 多段图的最短路径问题,多段图G(V，E)是个有向图。它具有如下特性：图中的结点被划分成k 2个不相交的集合Vi ,1ik,其中V1和Vk分别只有一个结点s(源点)和t(汇点)。图中所有的边均具有如下性质：若uVi ，则v Vi+1 ,1ik,且每条边均附有成本c(u，v)。从s到t的一条路径成本是这条路径上边的成本和。多段图问题(multistage graph problem)是求由s到t的最小成本路径。,设s, s1, s2, , sp, t是从s到t的一条最短路径，从源点s开始，设从s到下一段的顶点s1已经求出，则问题转化为求从s1到t的最短路径，显然s1, s2, , sp, t一定构成一条从s1到t的最短路径。 如若不然， 设s1, r1, r2, , rq, t是一条从s1到t的最短路径，则s, s1, r1, r2, , rq, t将是一条从s到t的路径且比s, s1, s2, , sp, t的路径长度要短，从而导致矛盾。 所以，多段图的最短路径问题满足最优性原理。,证明多段图问题满足最优性原理,对多段图的边(u, v)，用cuv表示边上的权值，将从源点s到终点t的最短路径记为d(s, t)，则从源点0到终点9的最短路径d(0, 9)由下式确定：d(0, 9)=minc01+d(1, 9), c02+d(2, 9), c03+d(3, 9)这一阶段的决策又依赖于下面的计算结果：d(1, 9)=minc14+d(4, 9), c15+d(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)=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)=c797(79)d(8, 9)=c893(89)而d(7, 9)和d(8, 9)可以直接获得括号中给出了决策产生的状态转移,这一阶段的决策又依赖于下面的计算结果：,第二阶段：迭代再向前推导，有：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)再向前推导，有：d(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。,下面考虑多段图的最短路径问题的填表形式。 用一个数组costn作为存储子问题解的表格，costi表示从顶点i到终点n-1的最短路径，数组pathn存储状态，pathi表示从顶点i到终点n-1的路径上顶点i的下一个顶点。则： costi=mincij+costj (ijn且顶点j是顶点i的邻接点) （式6.7）pathi=使cij+costj最小的j （式6.8）,算法6.2主要由三部分组成：第一部分是初始化部分，其时间性能为O(n)；第二部分是依次计算各个顶点到终点的最短路径，由两层嵌套的循环组成，外层循环执行n-1次，内层循环对所有出边进行计算，并且在所有循环中，每条出边只计算一次。假定图的边数为m，则这部分的时间性能是O(m)；第三部分是输出最短路径经过的顶点，其时间性能是O(n)。所以，算法6.2的时间复杂性为O(n+m)。,6.3 组合问题中的动态规划法,6.3.1 0/1背包问题,6.3.2 最长公共子序列问题,34,6.3.1 0/1背包问题 (The Knapsack Problem),n个物品，背包容量W,最大化：,限制条件：, School of Computer Science and Technology, SWUST,35,背包问题(The Knapsack Problem),动态规划分析设Vi,j为前i个物品放到背包容量为j的背包中时最优解的物品总价值。则目标是：Vn,W。对于n个物品，要得到Vn,W，有两种情况：a. 第n个物品不在背包中，则最优解物品总价值为Vn-1,Wb. 第n个物品在背包中，则最优解物品总价值为前n-1个物品的最优解总价值Vn-1,W-vn与第n个物品价值的和，或者就是前n-1个物品的最优解总价值，这里取两个中的最大值，即Vn,W=MaxVn-1,W-Vn+vn,Vn-1,W, School of Computer Science and Technology, SWUST,36,背包问题(The Knapsack Problem),对于一般情况有：设Vi,j为前i个物品放到背包容量为j的背包中时最优解的物品总价值。有两种情况：a. 第i个物品不在背包中，则最优解物品总价值为Vi-1,j（如果 ）b. 第i个物品在背包中，则最优解物品总价值为前i-1个物品的最优解总价值Vi-1,W-vi与第i个物品价值的和，或者就是前i-1个物品的最优解总价值，这里取两个中的最大值，即Vi,j=MaxVi-1,j-Vi+vi,Vi-1,j, School of Computer Science and Technology, SWUST,37,背包问题(The Knapsack Problem),承重量W=5,V4,5V3,5，物品4包含在最有解中，后者由V3,3确定；V3,3V2,3，表明3不在最有解里，又因为V2,3 V1,3，物品2在最有解中，V1,2 V0,2，物品 1在最有解中。最有解1,2,4,6.3.1 0/1背包问题,在0/1背包问题中，物品i或者被装入背包，或者不被装入背包，设xi表示物品i装入背包的情况，则当xi=0时，表示物品i没有被装入背包，xi=1时，表示物品i被装入背包。根据问题的要求，有如下约束条件和目标函数：,（式6.9）,（式6.10）,于是，问题归结为寻找一个满足约束条件式6.9，并使目标函数式6.10达到最大的解向量X=(x1, x2, , xn)。,证明0/1背包问题满足最优性原理。 设(x1, x2, , xn)是所给0/1背包问题的一个最优解，则( x2, , xn)是下面一个子问题的最优解：,如若不然，设(y2, , yn)是上述子问题的一个最优解，则 因此， 这说明(x1, y2, , yn)是所给0/1背包问题比(x1, x2, , xn)更优的解，从而导致矛盾。,0/1背包问题可以看作是决策一个序列(x1, x2, , xn)，对任一变量xi的决策是决定xi=1还是xi=0。在对xi-1决策后，已确定了(x1, , xi-1)，在决策xi时，问题处于下列两种状态之一：（1）背包容量不足以装入物品i，则xi=0，背包不增加价值；（2）背包容量可以装入物品i，则xi=1，背包的价值增加了vi。 这两种情况下背包价值的最大者应该是对xi决策后的背包价值。令V(i, j)表示在前i(1in)个物品中能够装入容量为j（1jC）的背包中的物品的最大值，则可以得到如下动态规划函数： V(i, 0)= V(0, j)=0 （式6.11）,（式6.12）,式6.11表明：把前面i个物品装入容量为0的背包和把0个物品装入容量为j的背包，得到的价值均为0。式6.12的第一个式子表明：如果第i个物品的重量大于背包的容量，则装入前i个物品得到的最大价值和装入前i-1个物品得到的最大价值是相同的，即物品i不能装入背包；第二个式子表明：如果第i个物品的重量小于背包的容量，则会有以下两种情况：（1）如果把第i个物品装入背包，则背包中物品的价值等于把前i-1个物品装入容量为j-wi的背包中的价值加上第i个物品的价值vi；（2）如果第i个物品没有装入背包，则背包中物品的价值就等于把前i-1个物品装入容量为j的背包中所取得的价值。显然，取二者中价值较大者作为把前i个物品装入容量为j的背包中的最优解。,根据动态规划函数，用一个(n+1)(C+1)的二维表V，Vij表示把前i个物品装入容量为j的背包中获得的最大价值。,0,例如，有5个物品，其重量分别是2, 2, 6, 5, 4，价值分别为6, 3, 5, 4, 6，背包的容量为10。,按下述方法来划分阶段：第一阶段，只装入前1个物品，确定在各种情况下的背包能够得到的最大价值；第二阶段，只装入前2个物品，确定在各种情况下的背包能够得到的最大价值；依此类推，直到第n个阶段。最后，V(n,C)便是在容量为C的背包中装入n个物品时取得的最大价值。为了确定装入背包的具体物品，从V(n,C)的值向前推，如果V(n,C)V(n-1,C)，表明第n个物品被装入背包，前n-1个物品被装入容量为C-wn的背包中；否则，第n个物品没有被装入背包，前n-1个物品被装入容量为C的背包中。依此类推，直到确定第1个物品是否被装入背包中为止。由此，得到如下函数：,（式6.13）,设n个物品的重量存储在数组wn中，价值存储在数组vn中，背包容量为C，数组Vn+1C+1存放迭代结果，其中Vij表示前i个物品装入容量为j的背包中获得的最大价值，数组xn存储装入背包的物品，动态规划法求解0/1背包问题的算法如下：,在算法6.3中，第一个for循环的时间性能是O(n)，第二个for循环的时间性能是O(C)，第三个循环是两层嵌套的for循环，其时间性能是O(nC)，第四个for循环的时间性能是O(n)，所以，算法6.3的时间复杂性为O(nC)。,