《动态规划DynamicProgrammingDPppt课件.ppt》由会员分享,可在线阅读,更多相关《动态规划DynamicProgrammingDPppt课件.ppt(73页珍藏版)》请在三一文库上搜索。
1、动态规划 (Dynamic Programming: DP) 宫秀军 天津大学计算机科学与技术学院 http:/ http:/ Outline nWhat is the DP qDefinition qSolutions nTypical applications q0/1 Knapsack qMatrix Multiplication Chains qAll Pairs Shortest Paths qMaximum Non-crossing Subset nets: MNS qLongest Common Subsequence nAdvanced topics qHidden Mark
2、ov Model qMathematics optimization 一个简单的例子:多段图 n最短路(1-3-5-7)上的子路径也是到目的节 点7的最短路.例如, (3-5-7) n无论最短路的下一跳是2,3,4中的那个节点, 其后的路径也应是最短路 1 2 3 4 6 5 7 1 4 6 7 6 5 8 12 1 任务描述:找出从起点1到终点7的最短路径 多段图:一般情形 n设c(i)为结点i到目的节点e的最短路长度, A(i)为与i相邻的节点集合,有: qc(s)为所求最短路径长度 qc(e)=0 q c(i)=minj A(i)c(j)+cost(i, j) s D 所以优化解为 1,
3、1,0, 优化值为38 例题: n=3, c=116 w=100,14,10 p=20,18,15, 0/1背包问题:递归关系 n令f(i,y) 表示容量为y,物品i,i+1,n 的优化效益值 ,按优化原理可列递归关系如下: n初始背包问题的递归方程 q f(1,c)=maxf(2,c),f(2,c-w1)+p1 n迭代 q计算从f(n, *)开始(15-1)式) q然后应用(15-2)式递归计算f(i,*) ( i=n-1,n-2,,2 ), q最后得出 f(1,c) 0/1背包问题:例15-4 n初始化: n利用递归式(15-2),可得: n因此最优解 f(1,116 )=maxf(2,1
4、16),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) n求解优化解:traceback方法计算x1,xn值: qf(1,c) =f(2,c)=x1=0;否则x1=1,c=c-w1。 qx2: f(2,c)=f(3,c)= x2=0否则x2=1,c=c-w2 qXi: f(i,c)=f(i+1,c)= xi=0否则xi=1,c=c-wi n该例中, qf(2,116)=33f(1,116),所以x1=1. 剩余容量=116
5、- 100=16, qf(2,16)=18,f(3,16)= 14f(2,16),因此x2=1 q此时r=16-14=2,不足以放物品3,所以x3= 0 动态规划小结: n一般步骤 q确定决策序列(Decision sequences) q明确问题状态(Problem states) q验证优化原理(Principle of optimal) q构造、求解优化值递归方程(Recurrence equation) q回溯(traceback)构造优化解(Optimal solution) n算法复杂性 q动态规划递归方程往往不能直接用递归实现, 会引发大量 重复计算,算法的计算量将非常可观。最好
6、是用迭代法求 解动态规划法列出的递归方程 q迭代实现需要存贮所有子问题的优化解的值,因此动态规 划法设计的算法往往需要较大的存储空间 q算法的复杂性来自子问题的数目,通常子问题的数目往往 很大 动态规划:应用 n0/1背包问题 n矩阵乘法链 n最短路径 n网络的无交叉子集 0/1背包问题-设计策略 n1. 递归方法 n2. 权为整数的迭代方法 n3. 元组方法 递归方法 n程序的最坏时间复杂性t(n) qt(1)=a; qt(n)=2t(n-1)+b (n1),其中a,b为常数 q求解可得t(n)=(2n) 递归方法:例15-5 n为了确定f (1,10),调 用函数F(1,10) n比较F(
7、i+1,y), F(i+1,y -wi)+pi n递归调用关系如图树 型结构所示: q其中每个节点用y值 来标记; q第j层的节点对应 F(j,*); q根节点表示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 108 10886 108428620 1045883226310 递归方法:例15-5(续) n通过递归调用树,可 以看到程序总共执行 了26次递归调用 n重复计算的节点,如 f(3,8),f(4,8), f(4,2), f(5,8), f(5,3),
8、f(5,2) n如果保留以前的计算 结果,则可将节点数 减至20,因为可以丢 弃图中的阴影节点 10 10 8 10886 108428620 1045883226310 W取整数时的迭代方法(1) n该算法用二维数组f iy来保存各个f 的值 因此每个f(i,y) 只计算 一次 n二维数组需(nc)空间 n该算法的复杂性(nc) -伪多项式算法: c是算 法输入的一部分, c的 二进制表示的长度为 log2c W取整数时的迭代方法(2) n函数Traceback 从fiy产生优 化的xi值 nTraceback的复 杂性为(n). 上述程序有两个缺点: 1)要求物品重量为整数; 2)当背包容
9、量c 很大时, 例如c2n,程序的复杂性为(n2n). 元组法:元组描述 n对于每个i,将f(i, y)的跳跃点以元组(y, f(i, y)形式存于表P(i)中. qP(i)中元组(y,f(i, y) 按y的增序排列. q元组(a,b)代表一种装物品i,n的方案:以 容量a,能得到效益值b. 如何只使用最少的计算从P(i+1)获得P(i)? 元组法:元组合并 n令Q=(s,t)|wisc的元组(w,v) 元组法:例15-6 nP(5)=(0,0), (4,6) ,Q=(5,4),(9,10) n合并得:P(4)=(0,0),(4,6),(9,10) n计算 Q=(6,5),(10,11) n合
10、并得 P(3)=(0,0),(4,6),(9,10),(10,11) n计算 Q=(2,3),(6,9) n合并得 P(2)=(0,0),(2,3),(4,6),(6,9),(9,10),(10,11) n计算 Q=(2,6),(4,9),(6,12),(8,15) n合并得P(1)=(0,0),(2,6),(4,9),(6,12),(8,15) n最优效益值为15 n回溯求解为1,1,0,0,1 设n=5,c=10 p=6,3,5,4,6 w=2,2,6,5,4 求f(1,10) nP(i) 中的元组个数至多为P(i+1)中元组个数的2 倍.初始P(n)=2,所以: P(i)中的元组个数不超
11、过2(n-i+1) n计算Q需O(|P(i+1)|)的时间,合并P(i+1) 和Q需 要O(|P(i1)|+|Q|)=O(2|P(i+1)|)的时间.所以计 算P(i)需O(2n-i+1)时间 n计算所有P(i) 时所需要的总时间O(2n)。 n存在输入使算法最坏情形为2n量级 元组法:性能分析 矩阵乘法链(Matrix multiPlication Chains: MPC) nmn矩阵A与np矩阵B相乘需元素乘法数 mnp n计算三个矩阵A(mn),B(np)和C(pq)的乘积 有两种方式: q第一种方式中先用A乘以B然后乘以C,这种乘法的顺 序可写为(A*B)*C q第二种方式为A* (B
12、*C) n尽管这两种不同的计算顺序所得的结果相同, 但所需元素乘法数却不同 q第一种方式乘法数:mp(n+q) q第二种方式乘法数:nq(m+p) MPC 示例 n假定A为1001矩阵,B为1100矩阵,C为1001 矩阵,(A*B) *C需乘法数为 1001100100100120000 n而 A* (B*C) 所需乘法数为1100110011 200 n长度q的矩阵乘法链有指数量级(2q)的可能的 相乘方式 n找一种相乘方式,使得元素乘法数最少 MPC动态规划解 n用M(i,j)表示链Mi,Mj (ij)的乘积.假设优化的乘法 顺序先计算M(i, k)和M(k+1,j),再将二者相乘 n则
13、计算M(i,j)的优化乘法顺序在计算M(i,k)和M(k+1,j) 时也是优化的 n考虑5个矩阵的乘法链,其行列数为r =(10, 5, 1, 10, 2, 10),即M1为105的矩阵,等等 q优化的乘法顺序为(M1M2)(M3M4)M5)=190 q子链M(3,5)=M3M4M5的优化乘法顺序为 (M3M4)M5),是上述长度5的链的优化解在子链上的乘法顺 序 MPC动态规划解(续) n设c(i,j)为计算M(i,j)的优化乘法数(优化值),根据优化原 理,优化值之间满足: qc(i,j)=minik0 return cij; cij=u; A deep look at the struc
14、tures of MPC MPC 迭代算法 n函数c 的动态规划递归式可用迭代的方法来 求解.若按s = 2, 3, , q-1 的顺序计算 c(i,i+s),每个c 和kay 仅需计算一次.但需很 大的存储空间。 MPC 迭代算法:示例 12345 105015090190 20503090 302040 40200 50 设q = 5和r =(10 , 5 , 1 , 10 , 2 , 10)求解MPC MPC 迭代程序 时间复杂度 n复杂性为O(q3) . q计算C(i, i+s)需 (s)时间. q对s2,q-1,要 计算q-s个C(i,i+s),时间复杂度 为(q-s)s). q所以
15、时间复杂度为(q3) n计算出kay 后同样可用程序15-6中的 Traceback 函数算出相应的最优乘法顺序 最短路径(All Pairs Shortest Paths: APSP) n最短路径:假设G为有向图,其中每条边都有一 个成本(cost),图中每条有向路径的长度(或成 本)定义为该路径上各边的成本之和 n对于每对顶点(i, j),定义从i 到j 的所有路径中, 具有最小长度的路径为从i 到j 的最短路径 n求每对点间的最短路 n假定图上无负成本的环路 APSP: 例15-15 n如图15-4所示。从顶点1到顶点3的路径有 1) 1,2,5,3 2) 1,4,3 3) 1,2,5,
16、8,6,3 4) 1,4,6,3 n由该图可知,各路径相应的长度为1 0,28, 9,2 7. 因而路径3) 是该图中顶点1到顶点3的最短路 径。 APSP: 动态规划解 n将节点按1到n编号. n定义c(i,j,k)=i到j的中间节点编号不超过k的最短 路长度. qc(i,j,0)=cost(i,j) if G else c(i,j,0)= qc(i,i,k)=0 for all k qc(i, j, n)是要求的i到j的最短路长度 n我们建立c(i,j,k)和c(i,j,k-1)之间的递归关系 APSP:递归式 n对于任意k0, q c(i,j,k)=minc(i, j, k-1), c(
17、i, k, k-1)+ c(k, j, k-1) n性质 qc(i,k,k-1)=c(i,k,k) qc(k,j,k)=c(k,j,k-1) n如果直接用递归程序求解上式,则计算c(i,j,n)的 复杂度极高.利用迭代方法.可将计算c 值的时 间减少到O(n3). n迭代算法的伪代码如图15-5所示。 APSP:迭代算法 n令C(k)代表矩阵 (c(i,j,k)i,j=1,n n初始C(0)=(c(i, j),即图 的邻接矩阵. n算法迭代计算C(k) : q对k行k列的元素 nC(k) (i,k)=C(k-1)(i,k) nC(k) (k,j)=C(k-1)(k,j). q对k行k列以外的元
18、素 nC(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 n图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的最短路径经过k
19、ay14=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)=7 C(2)(1,3)=minC(1)(1,3), C(1)(1,2)+C(1)(2,3) =min11,4+2=6 C(3)(1,2)=min4,6+7=4 C(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
20、8 9 10 n每个i 有唯一一个Ci对应,称为网(i,Ci) n(i,Ci)与(j,Cj)组成非交叉子网,若(i=ci,j-1 then 12. ci,j=ci-1,j 13. bi,j=2; 14. else ci,j=ci,j-1 15. bi,j=3; 14 bi,j stores the directions. 1diagnal, 2-up, 3-forward. Example 1 of an LCS X=BDCABA and Y=ABCBDAB Constructing an LCS PrintLCS(b,X,i,j) 1. i=m 2. j=n; 3. if i=0 or j=
21、0 then exit; 4. if bi,j=1 then i=i-1; j=j-1; print “xi”; 5. if bi,j=2 i=i-1 6. if bi,j=3 j=j-1 7. Goto Step 3. The time complexity: O(nm). 0 1 2 3 4 i Xi A B C YjBBACD 0 0 00000 0 0 0 10001 1211 112 1 22 1122 3 B B C BLCS (reversed order): B C B LCS (straight order): Hidden Markov Model HMM = (I , O
22、, A, B, ) nI= i1,iN:set of state nO = v1,.,vM:set of observation nA = aij,aij = p(It+1 = ij |It = ii): transition probability nB = bik,bik = p(Ot = vk | It = ii): symbol probability n = i, i = p(I1 = ii): init state distribution Where: I= is the state sequence O= is the output sequence Three Problem
23、s of HMM nEvaluation: Given model and output sequence O, computing p(O| ) nDecoding: Given model and output sequence O, to find the state sequence X such that: maximize p(O, I| ) nLearning Given output sequence O, to find the model such that: maximize p(O, I| ) 复习要求 n根据优化原理列递归式 n设计实现递归式的迭代算法(列表) n应用
24、 q0/1背包问题 q矩阵乘法链 q求各对点之间的最短路 qMNS n要求会做实例;分析算法的复杂度 课堂练习(1) n0/1背包问题: n=4,c=20,w=(10,15,6,9) p=(2,5,8,1) 产生元组集合P(1),P(2),P(3)和该背包问 实例的解 n证明当重量和效益值均为整数时动态规划算法 的时间复杂度为 O(min2n,n1inpi ,nc) 提示:|P(i)| 1+ijnpj 课堂练习(2) n子集和数问题:设S=s1,s2,.,sn 为n个正数的 集合,试找出和数不超过M且最大的S的子集 n该问题是NP-难度问题,试用动态规划法设计一 算法 练习(3) nr=(10
25、,20,50,1,100),给出优化的乘法顺序和元 素乘法数目 练习(4),习题19 nT(i,j)=任务i 按第j种方式所需时间(j=1,2) nC(i,j)=任务i 按第j种方式所需成本(j=1,2) n任务是拓扑排序的,必须先完成任务1才能完成任务 2 n要求在时间t之前完成所有任务且成本最小 ncost(i,j)任务1到i能在j时间内完成的最小成本 ncost(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) n上述列递归的方式称为从前向后(backward) n也可按书上提示从后向前列递归 n设n3, T=(2,1,4;3,2,1) C=(1,5,2;2,3,4),t=8 分号前为第一种选择;分号后为第二种选择。 计算优化的完成任务的方案。 n分析算法的复杂性 练习(5),习题20 n假定一机器由n种元件组成。现有三个供应商 :w(i,j)=供应商j提供的元件i的重量;c(i,j)=供 应商j提供的元件i的成本(取整数值);求成本不 超过c,机器重量最轻的采购方案 n同于习题19
链接地址:https://www.31doc.com/p-2551938.html