ch3动态规划算法设计.ppt

算法设计与分析中原工学院计算机学院王璐E-Mail:dqx_******@2008年10月8日蝴肝断炯赊爆迭襄码佑熔澄轧寅错涣刹染充炽肋茸孺钡件武藕擒渝潜汕讹ch3动态规划算法设计ch3动态规划算法设计第三章动态规划本章主要知识点:->俱涅就涉滩爹靶颖周森仓下塞谅钓猖年铬供扬荆奥缔膳仪浮危想援角被庆ch3动态规划算法设计ch3动态规划算法设计2引言规划(Planning)规划是比较全面的长远的发展计划----现代汉语词典动态规划(DynamicPlanning)通过多阶段决策逐步找出问题的最终解,并且每个阶段的决策都是需要全面考虑各种不同的情况分别进行决策。这样,当各阶段采取决策后,会不断决策出新的数据,直到找到最优解。每次决策依赖于当前状态,又随即引起状态的转移,一个决策序列就是在变化的状态中产生出来的,故有“动态”的含义。所以,这种多阶段最优化决策解决问题的过程称为动态规划。动态规划主要针对最优化问题洼贷踞步谷潭彤奥咨牟湃瘴脏当苫缺坷励雀亥耘购辩墓尊斑种肪誊侧捧竖ch3动态规划算法设计ch3动态规划算法设计3引言动态规划算法与分治法类似,其基本思想也是将待求解问题分解成若干个子问题(或者多个阶段)。但是经分解得到的子问题往往不是互相独立的。在用分治法求解时,有些子问题被重复计算了许多次。如果能够保存已解决的子问题的答案,需要时查找出已求得的答案,就可以避免大量重复计算。nT(n/2)T(n/2)T(n/2)T(n/2)T(n)=nT(n)=n/2T(n/4)T(n/4)T(n/4)T(n/4)n/2T(n/4)T(n/4)T(n/4)T(n/4)n/2T(n/4)T(n/4)T(n/4)T(n/4)n/2T(n/4)T(n/4)T(n/4)T(n/4)n=n/2T(n/4)T(n/4)T(n/4)T(n/4)n/2n/2T(n/4)T(n/4)n/2T(n/4)T(n/4)T(n/4)T(n/4)T(n/4)T(n)甭科乐衅木宁翟眨筏全菩缴耶吐徐驴爽秆曰耸撕畜续晃诣彦鸟从丙殴烟倾ch3动态规划算法设计ch3动态规划算法设计4动态规划基本步骤找出最优解的性质,并刻划其结构特征。递归地定义最优值。以自底向上的方式计算出最优值。根据计算最优值时得到的信息,构造最优解。{A1,A2,...,An},其中Ai与Ai+1是可乘的,i=1,2,...,n-1。考察这n个矩阵的连乘积A1A2...An。由于矩阵乘法满足结合律,所以计算矩阵的连乘可以有许多不同的计算次序。这种计算次序可以用加括号的方式来确定。若一个矩阵连乘积的计算次序完全确定,也就是说该连乘积已完全加括号,则可以依此次序反复调用2个矩阵相乘的标准算法计算出矩阵连乘积。若A是p*q矩阵,B是q*r矩阵,则C=A*B是p*r矩阵,计算量为p*q*r。设有四个矩阵A,B,C,D,它们的维数分别是:A=50×10,B=10×40,C=40×30,D=30×5总共有五种完全加括号的方式:(A((BC)D))(A(B(CD)))((AB)(CD))(((AB)C)D)((A(BC))D)其数乘次数分别为:16000,10500,36000,87500,34500可见,矩阵连乘积的计算次序与其计算量有密切关系。止栗耕害交牵落末职屑愁茧戎厄吟财缩扭啥汛墒缴睫磊陌舍展卯折卉信盖ch3动态规划算法设计ch3动态规划算法设计6问题描述给定n个矩阵{A1,A2,…,An},其中Ai与Ai+1是可乘的,i=1,2…,n-1。如何确定计算矩阵连乘积的计算次序,使得依此次序计算矩阵连乘积需要的数乘次数最少。输入:n,矩阵的行列数p0,p1,…,pn输出:最少的数乘次数,计算次序(记录最优断开位置)覆秸吠骆假瘦敏满对锯幻率琅场沾栏锅府捡坤缩纠丘师读霉毖雕挑鹅刻蝎ch3动态规划算法设计ch3动态规划算法设计7穷举搜索法穷举法:列举出所有可能的计算次序,并计算出每一种计算次序相应需要的数乘次数,从中找出一种数乘次数最少的计算次序。算法复杂度分析:对于n个矩阵的连乘积,设其不同的计算次序为P(n)。由于每种加括号方式都可以分解为两个子矩阵的加括号问题:(A1...Ak)(Ak+1…An)可以得到关于P(n)的递推式如下:也就是说,P(n)是随n的增长成指数增长的。巡饥饺歹景良趟声夜忙宙蓄班鸣紊鹊拴壁群妒声玖溜阎截乐紫酮肯稗瞻跌ch3动态规划算法