动态规划DynamicProgrammingDP.ppt

动态规划(DynamicProgramming:DP)宫秀军天津大学计算机科学与技术学院******@(0/1Knapsack)矩阵乘法链问题(MatrixMultiplicationChains)最短路径(AllPairsShortestPaths)最大非交叉子集问题(MaximumNon-s:MNS)其他应用最长公共子序列问题(monSubsequence)隐马尔可夫模型(HiddenMarkovModel)一个简单的例子:多段图最短路(1->3->5->7),(3->5->7)无论最短路的下一跳是{2,3,4}中的那个节点,其后的路径也应是最短路12346571467658121任务描述:找出从起点1到终点7的最短路径动态规划基本原理优化原理(PrincipleofOptimal)优化解包含的子问题的解也是优化的Nomatterwhatthefirstdecision,theremainingdecisionsareoptimalwithrespecttothestatethatresultsfromthisdecision动态规划常用来解优化问题动态规划是解决多阶段决策过程最优化的一种方法该方法是由美国数学家贝尔曼()等人在20世纪50年代初提出的。用于解决生产管理、工程技术等方面的许多问题,并建立了运筹学的一个新的分支,即动态规划Bellman在1957年出版了《DynamicProgramming》一书,是动态规划领域中的第一本著作广泛应用于人工智能、生物信息学等诸多领域多段图:一般情形设c(i)为结点i到目的节点e的最短路长度,A(i)为与i相邻的节点集合,有:c(s)为所求最短路径长度c(e)=0c(i)=minj∈A(i){c(j)+cost(i,j)}s<i<e12346571467658121任务描述:找出从起点s到终点e的最短路径多段图:算例初始化c(7)=0迭代计算c(6),…,c(1):c(6)=1c(5)=2c(4)=8+c(6)=9c(3)=min{1+c(5),5+c(6)}={3,6}=3c(2)=min{7+c(5),6+c(6)}={9,7}=7c(1)=min{1+c(2),4+c(3),6+c(4)}={8,7,15}=7递归还可从前向后c(i)=节点1到节点i的最短路的长度递归从c(1)=0开始1234657**********/1背包问题(0/1Knapsack)问题描述有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,6]w=[2,2,6,5,4]优化值间的递归式虽然不知道优化解是否放物品1,但从优化原理我们能建立优化值间的递归式设f(i,y)为以背包容量y,放物品i,…,n,得到的优化效益值,以下递归关系成立:f(1,c)=max{f(2,c),f(2,c-w1)+p1}先求子问题的优化值(递归),,任意i,…,:一个简单的例子放进物品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=116w=[100,14,10]p=[20,18,15],