动态规划DynamicProgrammingDP.ppt
《动态规划DynamicProgrammingDP.ppt》由会员分享,可在线阅读,更多相关《动态规划DynamicProgrammingDP.ppt(60页珍藏版)》请在三一文库上搜索。
1、动态规划 (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),一个简单的例子:多段图,最
2、短路(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 th
3、is 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)+
4、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)=2 c(4)=8+c(6)=9 c(3)=min1+c(5),5+c(6)=3,6=3 c(2)=min7+c(5),6+c(6)=9,7=7 c(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
5、/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
6、=4,c=8,物品为2,3,4,5 (1,0,0,1),即放物品1和5,是子问题的优化解 因而背包问题满足优化原理,假设: n=5,c=10 p=6,3,5,4,6 w=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),背包
7、容量还剩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,10 p=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)式)
8、 然后应用(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)=
9、f(3,c)= x2=0否则x2=1,c=c-w2 Xi: 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 equa
10、tion) 回溯(traceback)构造优化解(Optimal solution) 算法复杂性 动态规划递归方程往往不能直接用递归实现, 会引发大量重复计算,算法的计算量将非常可观。最好是用迭代法求解动态规划法列出的递归方程 迭代实现需要存贮所有子问题的优化解的值,因此动态规划法设计的算法往往需要较大的存储空间 算法的复杂性来自子问题的数目,通常子问题的数目往往很大,动态规划:应用,0/1背包问题 矩阵乘法链 最短路径 网络的无交叉子集,0/1背包问题-设计策略,1. 递归方法 2. 权为整数的迭代方法 3. 元组方法,递归方法,程序的最坏时间复杂性t(n) t(1)=a; t(n)=2t(
11、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=10 p=6,3,5,4,6 w=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
12、-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取整
13、数时的迭代方法(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
14、,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,
15、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)的
16、乘积有两种方式: 第一种方式中先用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
- 配套讲稿:
如PPT文件的首页显示word图标,表示该PPT已包含配套word讲稿。双击word图标可打开word文档。
- 特殊限制:
部分文档作品中含有的国旗、国徽等图片,仅作为作品整体效果示例展示,禁止商用。设计者仅对作品中独创性部分享有著作权。
- 关 键 词:
- 动态 规划 DynamicProgrammingDP
链接地址:https://www.31doc.com/p-2557357.html