第6章-动态规划法(1)

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(1≤i≤n)的货币，用集合P={p1,p2,…,pn}表示，如果POS机需支付的现金为A，那么，它必须从P中选取一个最小子集S，使得（式6.1）miiiSmApSp1|)|(,向量X=(x1,x2,…,xn)表示S中所选取的货币，则（式6.2）SpSpxiii01POS机支付的现金必须满足（式6.3）Apxniii1并且（式6.4）niixd1min集合P：问题的输入可行解：满足式6.1的解称为可行解解的表现形式：式6.2是解的表现形式，因为向量X中有n个元素，每个元素的取值为0或1，所以，可以有2n个不同的向量，所有这些向量的全体构成该问题的解空间约束条件：式6.3是该问题的约束条件目标函数：式6.4是该问题的目标函数最优解：使式6.4取得极小值的解称为该问题的最优解6.1.2最优性原理多阶段决策：对于一个具有n个输入的最优化问题，其求解过程往往可以划分为若干个阶段每一阶段的决策仅依赖于前一阶段的状态，由决策所采取的动作使状态发生转移，成为下一阶段决策的依据一个决策序列在不断变化的状态中产生S0P1P2Pn多阶段决策过程S1S2Sn-1Sn分析最优化问题！！！Sn-1SnS1S0s1,1sn,knp1,1s1,k1p1,k1s1,r1………sn-1,kn-1pn,kn…pn-1,kn-1…动态规划的决策过程sn-1,1……sn-1,rn-1sn,1sn,rn……©SchoolofComputerScienceandTechnology,SWUST9•最优性原理(PrincipleofOptimality)–无论过程的初始状态和初始决策是什么，其余的决策都必须相对于初始决策所产生的状态构成一个最优决策序列。–原理告诉我们，一个最优问题的任何实例的最优解是由该实例的子实例的最优解组成的。重要结论：一般来说，如果所求解问题对于最优性原理成立，则说明用动态规划方法有可能解决该问题。而解决问题的关键在于获取各阶段问的递推关系式（动态规划函数）。6.1.3动态规划法的设计思想•将原问题分解为若干个子问题，先求子问题的解，然后从这些子问题的解得到原问题的解。•这些子问题的解往往不是相互独立的。在求解的过程中，许多子问题的解被反复地使用。为了避免重复计算，动态规划算法采用了填表来保存子问题解的方法。•在算法中用表格来保存已经求解的子问题的解，无论它是否会被用到。当以后遇到该子问题时即可查表取出其解，避免了重复计算。原问题的解原问题……填表子问题1子问题2子问题n动态规划法的求解过程分治法：n=5时计算斐波那契数的过程F(5)F(4)F(3)F(3)F(2)F(2)F(1)F(2)F(1)F(1)F(0)F(1)F(0)F(1)F(0)例：计算斐波那契数：2)2()1(1100)(nnFnFnnnF01234567890112358132134求解斐波那契数F(9)的填表过程：动态规划法：分析：计算F(n)是以计算它的两个重叠子问题F(n-1)和F(n-2)的形式来表达的，所以，可以设计一张表填入n+1个F(n)的值。动态规划的基本要素•最优子结构：问题的最优解是由其子问题的最优解所构成的。•重叠子问题：子问题之间并非相互独立的，而是彼此有重叠的。最优子结构性质使我们能够以自底向上的方式递归地从子结构的最优解构造出问题的最优解。因为子问题重叠，所以存在着重复计算。这样就可以用填表保存子问题解的方法来提高效率。如何证明问题是否满足最优性原理？用反证法！！先假设由问题的最优解导出的子问题的解不是最优的;然后再证明在这个假设下可构造出比原问题最优解更好的解，从而导致矛盾。动态规划的基本方法•动态规划通常可以按以下几个步骤进行：•(1)找出最优解的性质，并刻画其结构特征；•(2)递归地定义最优值；•(3)以自底向上的方式计算出各子结构的最优值并添入表格中保存；•(4)根据计算最优值时得到的信息，构造最优解。•步骤1~3是动态规划算法的基本步骤。若需要最优解，则必须执行第4步，为此还需要在第3步中记录构造最优解所必需的信息。6.2图问题中的动态规划法6.2.1TSP问题6.2.2多段图的最短路径问题6.2.1TSP问题TSP问题：旅行家要旅行n个城市，要求各个城市经历且仅经历一次然后回到出发城市，并要求所走的路程最短。各个城市间的距离可以用代价矩阵来表示。0321C=∞3675∞2364∞2375∞带权图的代价矩阵设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的最短路径长度开始时，V‘＝V－{i}，于是，TSP问题的动态规划函数为：d(i,V')=min{cik+d(k,V－{k})}(k∈V')（式6.5）d(k,{})=cki(k≠i)（式6.6）这一阶段的决策又依赖于下面的计算结果：d(1,{2,3})=min{c12+d(2,{3}),c13+d(3,{2})}d(2,{1,3})=min{c21+d(1,{3}),c23+d(3,{1})}d(3,{1,2})=min{c31+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})=min{c01+d(1,{2,3}),c02+d(2,{1,3}),c03+d(3,{1,2})}而下式可以直接获得（括号中是该决策引起的状态转移）：d(1,{})=c10=5(1→0)d(2,{})=c20=6(2→0)d(3,{})=c30=3(3→0)再向前倒推，有：d(1,{2})=c12+d(2,{})=2+6=8(1→2)d(1,{3})=c13+d(3,{})=3+3=6(1→3)d(2,{3})=c23+d(3,{})=2+3=5(2→3)d(2,{1})=c21+d(1,{})=4+5=9(2→1)d(3,{1})=c31+d(1,{})=7+5=12(3→1)d(3,{2})=c32+d(2,{})=5+6=11(3→2)再向前倒退，有：d(1,{2,3})=min{c12+d(2,{3}),c13+d(3,{2})}=min{2+5,3+11}=7(1→2)d(2,{1,3})=min{c21+d(1,{3}),c23+d(3,{1})}=min{4+6,2+12}=10(2→1)d(3,{1,2})=min{c31+d(1,{2}),c32+d(2,{1})}=min{7+8,5+9}=14(3→2)最后有：d(0,{1,2,3})=min{c01+d(1,{2,3}),c02+d(2,{1,3}),c03+d(3,{1,2})}=min{3+7,6+10,7+14}=10(0→1)所以，从顶点0出发的TSP问题的最短路径长度为10，路径是0→1→2→3→0。假设n个顶点用0～n-1的数字编号，首先生成1～n-1个元素的子集存放在数组V[2n-1]中，设数组d[n][2n-1]存放迭代结果，其中d[i][j]表示从顶点i经过子集V[j]中的顶点一次且仅一次，最后回到出发点0的最短路径长度。ji{}{1}{2}{3}{1,2}{1,3}{2,3}{1,2,3}0101586726951033121114动态规划法求解TSP问题的填表过程0321C=∞3675∞2364∞2375∞算法6.1——TSP问题1．for(i=1;in;i++)//初始化第0列d[i][0]=c[i][0];2．for(j=1;j2n-1-1;j++)for(i=1;in;i++)//依次进行第i次迭代if(子集V[j]中不包含i)对V[j]中的每个元素k，计算d[i][j]=min(c[i][k]+d[k][j-1]);3.对V[2n-1-1]中的每一个元素k，计算d[0][2n-1-1]=min(c[0][k]+d[k][2n-1-2]);4．输出最短路径长度d[0][2n-1-1];算法6.1的时间复杂性为O(2n)。蛮力法求解TSP问题:时间复杂性是O(n!)算法描述设顶点之间的代价存放在数组c[n][n]中256.2.2多段图的最短路径问题•多段图G＝(V，E)是—个有向图。它具有如下特性：–图中的结点被划分成k≥2个不相交的集合Vi,1≤i≤k,其中V1和Vk分别只有一个结点s(源点)和t(汇点)。–图中所有的边u,v均具有如下性质：若u∈Vi，则v∈Vi+1,1≤i≤k,且每条边u,v均附有成本c(u，v)。–从s到t的一条路径成本是这条路径上边的成本和。–多段图问题(multistagegraphproblem)是求由s到t的最小成本路径。123458761110912st9732227111118654356524V1V2V3V4V52120345678949387684756866537一个多段图设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)=min{c01+d(1,9),c02+d(2,9),c03+d(3,9)}这一阶段的决策又依赖于下面的计算结果：d(1,9)=min{c14+d(