动态规划DynamicProgrammingDP.ppt

动态规划(Dynamic Programming:DP),宫秀军天津大学计算机科学与技术学院,主要内容,引论基本思想解决方案典型应用0/1 背包问题（0/1 Knapsack）矩阵乘法链问题(Matrix Multiplication Chains)最短路径(All Pairs Shortest Paths)最大非交叉子集问题(Maximum Non-crossing Subset nets:MNS)其他应用最长公共子序列问题(Longest Common Subsequence)隐马尔可夫模型(Hidden Markov Model),一个简单的例子：多段图,最短路(1-3-5-7)上的子路径也是到目的节点7的最短路.例如,(3-5-7)无论最短路的下一跳是2,3,4中的那个节点,其后的路径也应是最短路,1,2,3,4,6,5,7,1,4,6,7,6,5,8,1,2,1,任务描述：找出从起点1到终点7的最短路径,动态规划基本原理,优化原理（Principle of Optimal）优化解包含的子问题的解也是优化的No matter what the first decision,the remaining decisions are optimal with respect to the state that results from this decision动态规划常用来解优化问题动态规划是解决多阶段决策过程最优化的一种方法该方法是由美国数学家贝尔曼（R.E.Bellman)等人在20世纪50年代初提出的。用于解决生产管理、工程技术等方面的许多问题，并建立了运筹学的一个新的分支，即动态规划Bellman在1957年出版了Dynamic Programming一书，是动态规划领域中的第一本著作广泛应用于人工智能、生物信息学等诸多领域,多段图：一般情形,设c(i)为结点i到目的节点e的最短路长度,A(i)为与i相邻的节点集合,有:c(s)为所求最短路径长度c(e)=0 c(i)=minj A(i)c(j)+cost(i,j)sie,1,2,3,4,6,5,7,1,4,6,7,6,5,8,1,2,1,任务描述：找出从起点s到终点e的最短路径,多段图：算例,初始化c(7)=0迭代计算c(6),c(1)：c(6)=1 c(5)=2c(4)=8+c(6)=9c(3)=min1+c(5),5+c(6)=3,6=3c(2)=min7+c(5),6+c(6)=9,7=7c(1)=min1+c(2),4+c(3),6+c(4)=8,7,15=7递归还可从前向后c(i)=节点1到节点i的最短路的长度递归从c(1)=0开始,1,2,3,4,6,5,7,1,4,6,7,6,5,8,1,2,1,0/1背包问题(0/1 Knapsack),问题描述有n种可选物品1,n，放入容量为c的背包内，使装入的物品具有最大效益表示n,c 分别为物品个数和背包容量p1,p2,pn为个体物品效益值w1,w2,，wn为个体物品容量问题解析0/1背包问题的解指物品1,n的一种放法(x1,xn的0/1赋值),使得效益值最大假定背包容量不足以装入所有物品:面临选择 优化原理:无论优化解是否放物品1,优化解对物品2,n的放法,相对剩余背包容量,也是优化解,背包问题满足的优化原理,(1,1,0,0,1)为其优化解,即放物品1,2,5物品1占背包容量2,剩下容量为8考虑子问题:n=4,c=8,物品为2,3,4,5(1,0,0,1),即放物品1和5,是子问题的优化解因而背包问题满足优化原理,假设：n=5,c=10p=6,3,5,4,6w=2,2,6,5,4,优化值间的递归式,虽然不知道优化解是否放物品1,但从优化原理我们能建立优化值间的递归式设f(i,y)为以背包容量y,放物品i,n,得到的优化效益值,以下递归关系成立:f(1,c)=maxf(2,c),f(2,c-w1)+p1先求子问题的优化值(递归),再从2种可能性中求出最优的.须对任意给定容量y,任意i,n 种物品求解子问题.,0/1背包问题：一个简单的例子,放进物品1(x1=1),背包容量还剩r=16 x2,x3=1,0 为子问题的优化解,值为18，总效益值为20+18=38不放物品1(x1=0)则对于剩下的两种物品而言,容量限制条件为116，1,1为子问题优化解,值为33前者效益值为38,后者为33;所以优化解为1,1,0,优化值为38,例题：n=3,c=116 w=100,14,10p=20,18,15,0/1背包问题：递归关系,令f(i,y)表示容量为y,物品i,i+1,n 的优化效益值,按优化原理可列递归关系如下：,初始背包问题的递归方程 f(1,c)=maxf(2,c),f(2,c-w1)+p1 迭代计算从f(n,*)开始(15-1)式)然后应用(15-2)式递归计算f(i,*)(i=n-1,n-2，,2)，最后得出 f(1,c),0/1背包问题：例15-4,初始化：,利用递归式（15-2），可得：,因此最优解f(1,116)=maxf(2,116)，f(2,116-w1)+p1=maxf(2,116),f(2,16)+20=max33,38=38,例题 n=3,w=100,14,10,p=20,18,15,c=116,0/1背包问题：例15-4（解续2）,求解优化解：traceback方法计算x1,xn值:f(1,c)=f(2,c)=x1=0；否则x1=1,c=c-w1。x2:f(2,c)=f(3,c)=x2=0否则x2=1,c=c-w2Xi:f(i,c)=f(i+1,c)=xi=0否则xi=1,c=c-wi该例中,f(2,116)=33f(1,116),所以x1=1.剩余容量=116-100=16,f(2,16)=18,f(3,16)=14f(2,16),因此x2=1此时r=16-14=2,不足以放物品3,所以x3=0,动态规划小结:,一般步骤确定决策序列(Decision sequences)明确问题状态(Problem states)验证优化原理(Principle of optimal)构造、求解优化值递归方程(Recurrence equation)回溯(traceback)构造优化解(Optimal solution)算法复杂性动态规划递归方程往往不能直接用递归实现,会引发大量重复计算,算法的计算量将非常可观。最好是用迭代法求解动态规划法列出的递归方程迭代实现需要存贮所有子问题的优化解的值，因此动态规划法设计的算法往往需要较大的存储空间算法的复杂性来自子问题的数目,通常子问题的数目往往很大,动态规划：应用,0/1背包问题矩阵乘法链最短路径网络的无交叉子集,0/1背包问题-设计策略,1.递归方法2.权为整数的迭代方法3.元组方法,递归方法,程序的最坏时间复杂性t(n)t(1)=a；t(n)=2t(n-1)+b(n1)，其中a,b为常数求解可得t(n)=(2n),递归方法：例15-5,为了确定f(1,10),调用函数F(1,10)比较F(i+1,y),F(i+1,y-wi)+pi递归调用关系如图树型结构所示:其中每个节点用y值来标记;第j层的节点对应F(j,*);根节点表示F(1,10),而它有左、右子节点,分别对应F(2,10)和F(2,8)。,n=5,c=10p=6,3,5,4,6w=2,2,6,5,4,求f(1,10).,10,10,8,10,8,8,6,10,8,4,2,8,6,2,0,10,4,5,8,8,3,2,2,6,3,1,0,递归方法：例15-5（续）,通过递归调用树,可以看到程序总共执行了26次递归调用重复计算的节点,如f(3,8)，f(4,8),f(4,2),f(5,8),f(5,3),f(5,2)如果保留以前的计算结果,则可将节点数减至20,因为可以丢弃图中的阴影节点,10,10,8,10,8,8,6,10,8,4,2,8,6,2,0,10,4,5,8,8,3,2,2,6,3,1,0,W取整数时的迭代方法(1),该算法用二维数组f iy来保存各个f 的值因此每个f(i,y)只计算一次二维数组需(nc)空间该算法的复杂性(nc)-伪多项式算法:c是算法输入的一部分,c的二进制表示的长度为log2c,W取整数时的迭代方法(2),函数Traceback从fiy产生优化的xi值Traceback的复杂性为(n).,上述程序有两个缺点:1)要求物品重量为整数;2)当背包容量c 很大时,例如c2n,程序的复杂性为(n2n).,元组法：元组描述,对于每个i,将f(i,y)的跳跃点以元组(y,f(i,y)形式存于表P(i)中.P(i)中元组(y,f(i,y)按y的增序排列.元组(a,b)代表一种装物品i,n的方案:以容量a,能得到效益值b.,如何只使用最少的计算从P(i+1)获得P(i)？,元组法：元组合并,令Q=(s,t)|wisc的元组(w,v),元组法：例15-6,P(5)=(0,0),(4,6)，Q=(5,4),(9,10)合并得：P(4)=(0,0),(4,6),(9,10)计算 Q=(6,5),(10,11)合并得 P(3)=(0,0),(4,6),(9,10),(10,11)计算 Q=(2,3),(6,9)合并得 P(2)=(0,0),(2,3),(4,6),(6,9),(9,10),(10,11)计算 Q=(2,6),(4,9),(6,12),(8,15)合并得P(1)=(0,0),(2,6),(4,9),(6,12),(8,15)最优效益值为15回溯求解为1,1,0,0,1,设n=5，c=10 p=6,3,5,4,6 w=2,2,6,5,4 求f(1,10),P(i)中的元组个数至多为P(i+1)中元组个数的2倍.初始P(n)=2,所以:P(i)中的元组个数不超过2(n-i+1)计算Q需O(|P(i+1)|)的时间,合并P(i+1)和Q需要O(|P(i1)|+|Q|)=O(2|P(i+1)|)的时间.所以计算P(i)需O(2n-i+1)时间 计算所有P(i)时所需要的总时间O(2n)。存在输入使算法最坏情形为2n量级,元组法：性能分析,矩阵乘法链（Matrix multiPlication Chains:MPC）,mn矩阵A与np矩阵B相乘需元素乘法数 mnp 计算三个矩阵A(mn),B(np)和C(pq)的乘积有两种方式:第一种方式中先用A乘以B然后乘以C,这种乘法的顺序可写为(A*B)*C第二种方式为A*(B*C)尽管这两种不同的计算顺序所得的结果相同,但所需元素乘法数却不同第一种方式乘法数：mp(n+q)第一种方式乘法数：nq(m+p),MPC 示例,假定A为1001矩阵,B为1100矩阵,C为1001矩阵,(A*B)*C需乘法数为 1001100100100120000而 A*(B*C)所需乘法数为1100110011200长度q的矩阵乘法链有指数量级(2q)的可能的相乘方式找一种相乘方式,使得元素乘法数最少,MPC动态规划解,用M(i,j)表示链Mi,Mj(ij)的乘积.假设优化的乘法顺序先计算M(i,k)和M(k+1,j),再将二者相乘则计算M(i,j)的优化乘法顺序在计算M(i,k)和M(k+1,j)时也是优化的考虑5个矩阵的乘法链,其行列数为r=(10,5,1,10,2,10),即M1为105的矩阵,等等优化的乘法顺序为(M1M2)(M3M4)M5)=190子链M(3,5)=M3M4M5的优化乘法顺序为(M3M4)M5),是上述长度5的链的优化解在子链上的乘法顺序,MPC动态规划解(续),设c(i,j)为计算M(i,j)的优化乘法数(优化值),根据优化原理,优化值之间满足:c(i,j)=minikjc(i,k)+c(k+1,j)+rirk+1rj+1c(i,j)的性质c(i,i)=0c(i,i+1)=ri*ri+1*ri+2令kay(i,j)为使c(i,j)达到最小值的k，则Kay(i,i+1)=i基本思路MPC满足优化原理用递归算法计算c(1,q)用kay(i,j)回溯找到优化的乘法顺序,MPC 例15-13,设q=5和r=（10,5,1,10,2,10）求解MPC,c(2,5)=minc(2,2)+c(3,5)+50,c(2,3)+c(4,5)+500,c(2,4)+c(5,5)+100,c(1,5)=min c(1,1)+c(2,5)+500，c(1,2)+c(3,5)+100,c(1,3)+c(4,5)+1000,c(1,4)+c(5,5)+200,c(1,5)=190,kay(1,5)=2,c(3,5)=minc(3,3)+c(4,5)+100,c(3,4)+c(5,5)+20=min300,40,c(3,5)=40,kay(3,5)=4,c(2,4)=minc(2,2)+c(3,4)+10,c(2,3)+c(4,4)+100=min30,150,c(2,4)=30,kay(2,4)=2,c(2,5)=90,kay(2,5)=2,c(1,3)=150,kay(1,3)=2,c(1,4)=90,kay(1,4)=2,M(1,5)=M(1,2)M(3,5),M(3,5)=M(3,4)M(5,5),在函数C中,r 为全局一维数组，kay是全局二维数组.函数C返回c(i j)之值且置kayi j=kay(i,j).函数Traceback 利用函数C中已算出的kay值来推导出最优乘法算法的步骤存储ci,j以避免重复计算,MPC 递归算法,/检查c(i,j)是否已计算If cij0 return cij;,cij=u;,MPC 迭代算法,函数c 的动态规划递归式可用迭代的方法来求解.若按s=2,3,q-1 的顺序计算 c(i,i+s),每个c 和kay 仅需计算一次.但需很大的存储空间。,MPC 迭代算法:示例,设q=5和r=（10,5,1,10,2,10）求解MPC,MPC 迭代程序,时间复杂度,复杂性为O(q3).计算C(i,i+s)需(s)时间.对s2,q-1,要 计算q-s个C(i,i+s),时间复杂度为(q-s)s).所以时间复杂度为(q3)计算出kay 后同样可用程序15-6中的Traceback 函数算出相应的最优乘法顺序,最短路径(All Pairs Shortest Paths:APSP),最短路径:假设G为有向图,其中每条边都有一个成本(cost),图中每条有向路径的长度(或成本)定义为该路径上各边的成本之和对于每对顶点(i,j),定义从i 到j 的所有路径中,具有最小长度的路径为从i 到j 的最短路径求每对点间的最短路假定图上无负成本的环路,APSP:例15-15,如图15-4所示。从顶点1到顶点3的路径有1)1,2,5,3 2)1,4,3 3)1,2,5,8,6,3 4)1,4,6,3由该图可知,各路径相应的长度为1 0,28,9,2 7.因而路径3)是该图中顶点1到顶点3的最短路径。,APSP:动态规划解,将节点按1到n编号.定义c(i,j,k)=i到j的中间节点编号不超过k的最短路长度.c(i,j,0)=cost(i,j)if G else c(i,j,0)=c(i,i,k)=0 for all kc(i,j,n)是要求的i到j的最短路长度我们建立c(i,j,k)和c(i,j,k-1)之间的递归关系,APSP:递归式,对于任意k0，c(i,j,k)=minc(i,j,k-1),c(i,k,k-1)+c(k,j,k-1)性质c(i,k,k-1)=c(i,k,k)c(k,j,k)=c(k,j,k-1)如果直接用递归程序求解上式,则计算c(i,j,n)的复杂度极高.利用迭代方法.可将计算c 值的时间减少到O(n3).迭代算法的伪代码如图15-5所示。,APSP：迭代算法,令C(k)代表矩阵(c(i,j,k)i,j=1,n初始C(0)=(c(i,j),即图的邻接矩阵.算法迭代计算C(k):对k行k列的元素C(k)(i,k)=C(k-1)(i,k)C(k)(k,j)=C(k-1)(k,j).对k行k列以外的元素C(k)(i,j)=maxC(k-1)(i,j),C(k-1)(i,k)+C(k-1)(k,j),APSP：改进的递归算法(1),Kayij是从i到j的最短路径中编号最大的节点,通过该节点可以回溯最短路径节点,APSP：改进的递归算法(2),APSP:例15-17,图15-6a 给出某图的长度矩阵a，15-6b 给出由程序15-9所计算出的c 矩阵，15-6c 为对应的kay值。根据15-6c 中的kay 值，可知从1到5的最短路径是从1到kay15=4的最短路径再加上从4到5的最短路径，因为kay45=0，所以从4到5的最短路径无中间顶点。从1到4的最短路径经过kay14=3。重复以上过程，最后可得1到5的最短路径为：1，2，3，4，5。,APSP:习题（1）,APSP:习题（2）,C(0)(i,j)=c(i,j)C(1)(3,2)=minC(0)(3,2),C(0)(3,1)+C(0)(1,2)=7C(2)(1,3)=minC(1)(1,3),C(1)(1,2)+C(1)(2,3)=min11,4+2=6C(3)(1,2)=min4,6+7=4C(3)(2,1)=min6,2+3=5,Maximum Noncrossing Subset of Nets:MNS,1 2 3 4 5 6 7 8 9 10,1 2 3 4 5 6 7 8 9 10,每个i 有唯一一个Ci对应，称为网(i,Ci)(i,Ci)与(j,Cj)组成非交叉子网，若（ij）有(CiCj)定义MNS(i,j)=(u,Cu)|u i Cu j且任何两个子网是非交叉子网size(i,j)=|MNS(i,j)|上图中MNS(5,7)=(4,2)(5,5)size(5,7)=2,i,Ci,MNS:递归关系,MNS 例题1,对上图有:size(1,j)=0,j=1,2,3,4,5,6,7 size(1,j)=1,j=8,9,10 因 C2=7,所以size(2,j)=0 for j=1,6 size(2,7)=size(1,6)+1=0 size(2,8)=maxsize(1,8),size(1,6)+1=1,1 2 3 4 5 6 7 8 9 10,1 2 3 4 5 6 7 8 9 10,Ci,i,MNS 例题2,MNS:taceback,Nets 按i 编号如果size(i,j)!=size(i-1,j)则MNS(i,j)包含net i令jCi1；重复上述过程2.,LCS:Longest Common Subsequences,Given two sequences x1.m and y1.n,find a longest subsequence common to them bothStrategy:Consider prefixes of x and yDefine ci,j=|LCS(x1.i,y1.j)|Then,cm,n=|LCS(x,y)|.Recursive formulation,ci1,j1+1 if xi=yj,maxci1,j,ci,j1 otherwise.,ci,j=,Hidden Markov Model,HMM=(I,O,A,B,)I=i1,.iN：set of stateO=v1,.,vM：set of observationA=aij，aij=p(It+1=ij|It=ii):transition probability B=bik，bik=p(Ot=vk|It=ii):symbol probability=i，i=p(I1=ii):init state distributionWhere:I=is the state sequenceO=is the output sequence,Three Problems of HMM,Evaluation:Given model and output sequence O,computing p(O|)Decoding:Given model and output sequence O,to find the state sequence X such that:maximize p(O,I|)Learning Given output sequence O,to find the model such that:maximize p(O,I|),复习要求,根据优化原理列递归式设计实现递归式的迭代算法(列表)应用0/1背包问题矩阵乘法链求各对点之间的最短路MNS要求会做实例；分析算法的复杂度,课堂练习(1),0/1背包问题:n=4,c=20,w=(10,15,6,9)p=(2,5,8,1)产生元组集合P(1),P(2),P(3)和该背包问 实例的解证明当重量和效益值均为整数时动态规划算法的时间复杂度为 O(min2n,n1inpi,nc)提示:|P(i)|1+ijnpj,课堂练习(2),子集和数问题:设S=s1,s2,.,sn 为n个正数的集合,试找出和数不超过M且最大的S的子集该问题是NP-难度问题,试用动态规划法设计一算法,练习(3),r=(10,20,50,1,100),给出优化的乘法顺序和元素乘法数目,练习(4),习题19,T(i,j)=任务i 按第j种方式所需时间(j=1,2)C(i,j)=任务i 按第j种方式所需成本(j=1,2)任务是拓扑排序的，必须先完成任务1才能完成任务2要求在时间t之前完成所有任务且成本最小cost(i,j)任务1到i能在j时间内完成的最小成本cost(1,j)=jT(1,1)=C(1,1)T(1,1)=jT(1,2)=minC(1,1),C(1,2)T(1,2)=j cost(i,j)=mincost(i-1,j-T(i,1)+C(i,1),cost(i-1,j-T(i,2)+C(i,2)表示在时间j内无法安排前i个任务；,练习(4),上述列递归的方式称为从前向后(backward)也可按书上提示从后向前列递归设n3,T=(2,1,4;3,2,1)C=(1,5,2;2,3,4)，t=8 分号前为第一种选择；分号后为第二种选择。计算优化的完成任务的方案。分析算法的复杂性,练习(5),习题20,假定一机器由n种元件组成。现有三个供应商：w(i,j)=供应商j提供的元件i的重量；c(i,j)=供应商j提供的元件i的成本(取整数值)；求成本不超过c，机器重量最轻的采购方案同于习题19,