算法7_动态规划法

第7章 动态规划法,学习要点：理解动态规划算法的概念。掌握动态规划算法的基本要素（1）最优子结构性质（2）重叠子问题性质掌握设计动态规划算法的步骤。理解动态规划算法与分治法、贪心法的异同通过应用范例学习动态规划算法设计策略。（1）多段图问题、关键路径问题（2）每对结点间的最短路径（3）最长公共子序列（4）0/1背包,章节内容7.1 一般方法和基本要素7.2 每对结点间的最短路径7.4 最长公共子序列7.6 0/1背包,7.1 一般方法和基本要素,动态规划算法总体思想动态规划算法的基本要素设计动态规划算法的步骤动态规划法与分治法、贪心法的区别,动态规划算法与分治法类似，其基本思想也是将待求解问题分解成若干个子问题,动态规划算法总体思想,但是经分解得到的子问题往往不是互相独立的。不同子问题的数目常常只有多项式量级。在用分治法求解时，有些子问题被重复计算了许多次。,动态规划算法总体思想,如果能够保存已解决的子问题的答案，而在需要时再找出已求得的答案，就可以避免大量重复计算，从而得到多项式时间算法。,动态规划算法总体思想,T(n),动态规划算法的基本要素,（1）子问题重叠性质（递归算法求解问题时）每次产生的子问题并不总是新问题，有些子问题被反复计算多次，这种性质称为子问题重叠性质。动态规划算法对每一个子问题只解一次，而后将其解保存在一个表格（通常用二维数组）中，当再次需要解此子问题时，只是简单地用常数时间查看一下结果。 通常不同的子问题个数随问题的大小呈多项式增长。因此用动态规划算法只需要多项式级时间，从而获得较高的解题效率。,动态规划算法的基本要素,（2）最优子结构性质用动态规划法求解的前提。当一个问题的最优解包含了其子问题的最优解时，称该问题具有最优子结构性质。一个问题的活动过程可以分为若干个阶段，每个阶段可包含一个或多个状态，从初始阶段的初始状态出发做出每个阶段的决策，形成一个决策序列。利用问题的最优子结构性质，以自底向上的方式递归地从子问题的最优解逐步构造出整个问题的最优解。,设计动态规划算法的步骤,用动态规划算法求解问题的步骤：1、找出最优解的性质，并刻划其结构特征；2、递归地定义最优解值；3、自底向上求最优解值；4、根据计算最优解值时得到的信息构造一个最优解（此步只在要求得到最优解时才需要做） 。动态规划法是一种求解最优化问题的重要算法策略。,动态规划法的子问题往往是重叠的。如果采用与分治法类似的直接递归方法求解将十分费时。为了避免重复计算，动态规划算法一般采用自底向上方式进行计算，并保存已经求解的子问题的最优解值。,利用最优子结构性质及所获得的递推关系式（较小子问题最优解与较大子问题最优解之间存在的数值关系）去求取最优解，可以使计算量较之穷举法急剧减少。,动态规划法与分治法,共同点：将待求解的问题分解成若干子问题，先求解子问题，然后再从这些子问题的解得到原问题的解。不同点：1、适合于用动态规划法求解的问题，分解得到的各子问题往往不是相互独立的；而分治法中子问题相互独立。2、动态规划法用表保存已求解过的子问题的解，再次碰到同样的子问题时不必重新求解，而只需查询答案，故可获得多项式级时间复杂度，效率较高；而分治法中对于每次出现的子问题均求解，导致同样的子问题被反复求解，故产生指数增长的时间复杂度，效率较低。,共同点：都是求解最优化问题；都具有最优子结构性质。不同点：1、求解方式不同：动态规划法：自底向上；贪心法：自顶向下。以迭代的方式作出相继的贪心选择，每作一次贪心选择就将所求问题简化为一个规模更小的子问题。2、对子问题的依赖不同：动态规划法：依赖于各子问题的解。只有在解出相关子问题后,才能作出选择；应使各子问题最优，才能保证整体最优；贪心法：不依赖于子问题的解。仅在当前状态下作出最好选择，即局部最优选择。,动态规划法与贪心法,多段图问题,一种特殊的有向无环图的最短路径问题。（例7-1）带权有向图G=(V,E)中的结点被划分成k个互不相交的子集Vi (1ik) 。其中：V1只包含源点s，Vk只包含汇点t ；图中的边均满足：若uVi则vVi+1 。求从s到t的一条长度最短的路径（P137 图7-1）。由每个阶段所作出的决策组成的决策序列，产生一条从s到t的路径多段图问题的一个可行解。目标函数（每条路径上所有边的权值之和，即路径长度）最小的一条路径为最优解，该路径长度为最优解值。,多段图的最优子结构证明,假设(s,v2,v3,.,vk-1,t)是一条从s到t的最短路径，并假定由源点s经过初始决策已经到达状态v2 。则将v2看成某个子问题的初始状态，该子问题寻找一条从v2到t的最短路径。证明（多段图具有最优子结构性质）如果(s,v2,v3,.,vk-1,t)是一条从s到t的最短路径，则(v2,v3,.,vk-1,t)必是一条从v2到t的最短路径。（反证）假如(v2,v3,.,vk-1,t)不是从v2到t的最短路径，另有(v2,q3,.,qk-1,t)是从v2到t的最短路径，那么路径(s,v2,q3,.,qk-1,t)显然比(s,v2,v3,.,vk-1,t)更短。与假设矛盾！多段图的最优子结构性质得证！,在分析（证明）问题的最优子结构性质时，所用的方法具有普遍性：首先假设由问题的最优解导出的子问题的解不是最优的，然后再设法说明在这个假设下可构造出比原问题最优解更好的解，从而导致矛盾。,多段图问题的递推式（向前递推）,由多段图问题的最优子结构性质，容易得到多段图问题的递推式，从而由子问题的最优解来计算原问题的最优解：多段图问题的向前递推式：（式7-1）cost(i,j)是从第i阶段中的结点j，到汇点t的最短路径长度。cost(i+1,p)是从后继结点（第i+1阶段中的结点）p到汇点t的最短路径长度。（子问题的最优解）c(j,p)+cost(i+1,p)是从第i阶段结点j，经过第i+1阶段结点p到达汇点t的路径长度。cost(i,j)则是这些路径中的最短路径长度。,E表示j,p之间有边,使用式（7-1）向前递推式，由后向前计算最优解值cost(1,0)cost(5,11)=0,cost(4,10)=5, cost(4,9)=2, cost(4,8)=4,cost(3,7)=min6+cost(4,10),5+cost(4,9)=7, cost(3,6)=.=5, cost(3,5)=.=7,cost(2,4)=min8+cost(3,7),11+cost(3,6)=15, cost(2,3)=18, cost(2,2)=.=9, cost(2,1)=.=7, cost(1,0)=min9+cost(2,1),7+cost(2,2),3+cost(2,3),2+cost(2,4)=16,若想求最优解，必须在计算最优解值的过程中保存一些必要信息。可用d(i,j)来记录从第i阶段结点j到汇点t的最短路径上该结点的下一个结点编号。,根据前面例7-1求最优解值cost(1,0)的过程中，产生的中间结果：cost(5,11)=0,cost(4,10)=5, cost(4,9)=2, cost(4,8)=4,cost(3,7)=min6+cost(4,10),5+cost(4,9)=7, cost(3,6)=.=5, cost(3,5)=.=7,cost(2,4)=min8+cost(3,7),11+cost(3,6)=15, cost(2,3)=18, cost(2,2)=.=9, cost(2,1)=.=7,cost(1,0)=min9+cost(2,1),7+cost(2,2),3+cost(2,3),2+cost(2,4)=16,可知：d(4,10)=d(4,9)=d(4,8)=11,d(3,7)=d(3,6)=d(3,5)=9,d(2,4)=d(2,3)=7,d(2,2)=5,d(2,1)=6,d(1,0)=1或2,很容易从d的值确定最短路径上的结点，得到两条最短路径：,(0, d(1,0)=1, d(2,1)=6, d(3,6)=9, d(4,9)=11) 和(0, d(1,0)=2, d(2,2)=5, d(3,5)=9, d(4,9)=11),多段图显然具有重叠子问题性质：计算cost(3,7)、cost(3,6)、cost(3,5)时都要用到cost(4,9)的值，因此保存cost(4,9)的值可以避免重复计算。,程序7-1：多段图的向前递推动态规划算法FMultiGraph(int k,int*p) /共k个阶段，n个结点 /带权有向图G （多段图）采用邻接表存储（见程序6-8） float *cost=new floatn; /一维数组costj保存结点j到汇点t的最短路径 int *d=new intn; /一维数组dj保存costj 对应的最短路径上的下一个结点 costn-1=0；dn-1=-1; /设置向前递推的初值(最大结点编号为n-1) for (int j=n-2;j>=0;j-) /按结点编号n-2,.,0的顺序计算cost j和dj float min=INFTY; / min求得的最小值，即为当前结点j的costjfor (ENode *r=aj;r;r=r->nextArc) /用指针r遍历邻接表中aj的邻接结点int v=r->adjVex; / 当前阶段的结点j与下一阶段的结点v之间有边if (r->w+costvw+costv; q=v; costj=min; dj=q; /q是最短子路径上j的下一个结点编号 c=cost0; p0=0;/c保存的是最优解值, p0 是源点0 for (j=1;j<=k-1;j+) pj=dpj-1;/数组p保存最优解，pi是最短路径上第i阶段结点,前提：结点已按拓扑顺序排序。思考：如何得到？,程序7-1：多段图的向前递推动态规划算法FMultiGraph(int k,int*p) /共k个阶段，n个结点 /带权有向图G （多段图）采用邻接表存储（见程序6-8） float *cost=new floatn; /一维数组costj保存结点j到汇点t的最短路径 int *d=new intn; /一维数组dj保存costj 对应的最短路径上的下一个结点 costn-1=0；dn-1=-1; /设置向前递推的初值(最大结点编号为n-1) for (int j=n-2;j>=0;j-) /按结点编号n-2,.,0的顺序计算cost j和dj float min=INFTY; / min求得的最小值，即为当前结点j的costjfor (ENode *r=aj;r;r=r->nextArc) /用指针r遍历邻接表中aj的邻接结点int v=r->adjVex; / 当前阶段的结点j与下一阶段的结点v之间有边if (r->w+costvw+costv; q=v; costj=min; dj=q; /q是最短子路径上j的下一个结点编号 c=cost0; p0=0;/c保存的是最优解值, p0 是源点0 for (j=1;j<=k-1;j+) pj=dpj-1;/数组p保存最优解，pi是最短路径上第i阶段结点,