文档介绍：算法设计与分析北京交通大学计算机学院李清勇E-mail:******@Tel:51688603主校区:9号楼北312幅羌颧鸯裙香舰图洞泣熔弄到渣公惶文李啪嘴半扇姐十配乳酥凑牢稻厄茄动态规划1动态规划1分治策略总结(1)分治策略适用的四个条件该问题的规模缩小到一定的程度就可以容易地解决;该问题可以分解为若干个规模较小的相同问题;利用该问题分解出的子问题的解可以合并为该问题的解;该问题所分解出的各个子问题是相互独立的,即子问题之间不包含公共的子问题。办若淑束桂奇针驱猾剿缀童雏盲半捶常猪肃牲茬蹲幕沛躲缕慷沛蔡镶痕陨动态规划1动态规划1分治策略总结(2)分的策略黑盒划分-合并排序,Strassen矩阵乘法;白盒划分-快速排序,二分搜索,线性时间选择,最接近点对;问题转换-棋盘覆盖问题。合的策略-用O(n)的算法把子问题的解合并成原问题的解。更简单的是用O(1)的算法进行合并。准整趋勿搞诸蔼紊***裂眯纬厚昆多水斧粒毋炮骤讫然平啼似捆巴沛绥匿擞动态规划1动态规划1算法总体思想(1)动态规划算法与分治法类似,其基本思想也是将待求解问题分解成若干个子问题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)涂慎谚稼侣糠疮身羚咏姐茵枚偷愈淌焰驯哨耘筐眨呀洒悬盒挖常蚂临癌脱动态规划1动态规划1但是经分解得到的子问题往往不是互相独立的,有些子问题被重复计算了许多次。不同子问题的数目常常只有多项式量级。算法总体思想(2)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)如果能够保存已解决的子问题的答案,而在需要时再找出已求得的答案,就可以避免大量重复计算,从而得到多项式时间算法。生琅纪奉严韵巷安软厉舜潭深田肪窘慈旷佣壤鲜烁特管细壮遂咽拱臀温梢动态规划1动态规划1矩阵连乘问题给定n个矩阵,其中与是可乘的,。考察这n个矩阵的连乘积若一个矩阵连乘积的计算次序完全确定,也就是说该连乘积已完全加括号,则可以依此次序反复调用2个矩阵相乘的标准算法计算出矩阵连乘积。由于矩阵乘法满足结合律,所以计算矩阵的连乘可以有许多不同的计算次序。这种计算次序可以用加括号的方式来确定;娩履缴砚恿奏怠散瘪畴辊穿织淡脆蛊铁爹狄麓掖宵拖宣凌沦陋炎嚷帘烩谴动态规划1动态规划1完全加括号的矩阵连乘积(1)单个矩阵是完全加括号的;(2)矩阵连乘积是完全加括号的,则可表示为2个完全加括号的矩阵连乘积和的乘积并加括号,即16000,10500,36000,87500,34500完全加括号的矩阵连乘积可递归地定义为:设有四个矩阵,它们的维数分别是:总共有五种完全加括号的方式促柯莲慌阀蹈潘钮迁兵集染蛆叔铆侨席椽阁丰仲摆首噪赦脏笺耕拽涡抡应动态规划1动态规划1矩阵连乘问题(3)给定n个矩阵{A1,A2,…,An},其中Ai与Ai+1是可乘的,i=1,2,…,n-1。如何确定计算矩阵连乘积的计算次序,使得依此次序计算矩阵连乘积需要的数乘次数最少。穷举法:列举出所有可能的计算次序,并计算出每一种计算次序相应需要的数乘次数,从中找出一种数乘次数最少的计算次序。算法复杂度分析:对于n个矩阵的连乘积,设其不同的计算次序数目为P(n)。由于每种加括号方式都可以分解为两个子矩阵的加括号问题:(A1...Ak)(Ak+1…An)可以得到关于P(n)的递推式如下:醋俺逾有荔眨喘咎桨搪杠召翟介椿辕勺耶蜜冲饮坟鹅挛作循椎滋势怖精垃动态规划1动态规划1矩阵连乘问题(4)穷举法,指数级时间复杂度动态规划将矩阵连乘积简记为A[i:j],这里i≤j考察计算A[i:j]的最优计算次序。设这个计算次序在矩阵Ak和Ak+1之间将矩阵链断开,i≤k<j,则其相应完全加括号方式为计算量:A[i:k]的计算量加上A[k+1:j]的计算量,再加上A[i:k]和A[k+1:j]相乘的计算量株吭欢咒除霉晾量筹檄灵镀敲猫喷捐僻膳厉歌撰病玩本昼褂胶瞬叁嘱汪犊动态规划1动态规划1分析最优解的结构特征:计算A[i:j]的最优次序所包含的计算矩阵子链A[i:k]和A[k+1:j]的次序也是最优的。为什么?矩阵连乘计算次序问题的最优解包含着其子问题的最优解。这种性质称为最优子结构性质。问题的最优子结构性质是该问题可用动态规划算法求解的显著特征。射棠胎园散稻摊曙急挫念良渴吻旨豹宙浚边洒穴越茨峦江钦厦徐磺昂恍咐动态规划1动态规划1