算法设计与分析4-5

《算法设计与分析4-5》由会员上传分享，免费在线阅读，更多相关内容在教育资源-天天文库。

1、动态规划(DynamicProgramming)基本思想和使用条件动态规划算法的设计步骤应用实例小结1基本思想和使用条件例1求从始点到终点的最短路径d,15d,11S16dd9,93B19u2u,22T1u,13A14u,53C154S2u8u,83B26d3d,34T27d,105A22u,74C23S3d6d,63B32u7u,77T34d,119A31d,51C37S44u,72B44u,1T41u,10A45u,43C436S5B5T52基本思想解：判断序列F(Cl)=min{ClTm)mF(Bk)=min{BkCl+F(Cl)}lF(

2、Aj)=min{AjBk+F(Bk)}kF(Si)=min{SiAj+F(Aj)}j任何最短路径的子路径都是相对于子路径的始点和终点的最短路径为找到一条最短路径只需从T开始进行多j步判断3使用条件－－优化原则一个最优决策序列的任何子序列本身一定是相对于子序列的初始和结束状态的最优的决策序列例2求总长模10的最小路径2222d,1u,6u,4u,2ST5555最优解：下、下、下、下动态规划求解：下、上、上、上不满足优化原则，不能使用动态规划设计技术4算法设计步骤例3矩阵乘法：设A,A,…,A为矩阵序列，A为P×P阶12nii-1i矩阵，i=121

3、,2,…,n.确定乘法顺序使得元素相乘的总次数最少.输入：向量P=01n实例：P=<10,100,5,50>A:10×100,A:100×5,A:5×50,123乘法次序(AA)A:10×100×5+10×5×50=7500123A(AA):10×100×50+100×5×50=7500012351⎛2n⎞一般算法：加括号的方法有⎜⎜⎟⎟种，n+1⎝n⎠Catalan数2n2n2π2n()1(2n)!1eW(n)=Ω()=Ω()n+1n!n!n+1nnnn2πn()2πn()ee122n2nnn31n2nee2n2=Ω()=Ω

4、(2/n)11n+1e2nn2nnn2nn6递推方程输入P=,A表示乘积AA…A的结果，01ni..jii+1j其最后一次相乘是A=AA,i..ji..kk+1..jm[i,j]表示得到A的最少的相乘次数i..j递推方程⎧0i=j⎪m[i,j]=⎨⎪⎩min{m[i,k]+m[k+1,j]+Pi−1PkPj}i

5、toj−1do4.q←RecurMatrixChain(P,i,k)+RecurMatrixChain(P,k+1,j)+pppi−1kj5.ifq1⎪⎩k=1n−1n−1n−1T(n)≥O(n)+∑T(k)+∑T(n−k)=O(n)+2∑T(k)k=1k=1k=1数学归纳法证明T(n)≥2n-1n=2,显然为真假设对于任何小于n的

6、k命题为真,则n−1n−1k−1T(n)≥O(n)+2∑T(k)≥O(n)+2∑2k=1k=1n−1n−1=O(n)+2(2−1)≥29复杂性高的原因原因：子问题重复程度高10算法2：非递归算法算法2MatrixChain(P,n)1．令有的令所有的m[i,j]初值为02．forr←2tondo//r为计算的矩阵链长度//3．fori←1to1ton−r+1do+1do//n-r+1为最后r链的始位置//4．j←i+r−1//计算链i—j//5．m[i,j]←m[i+1,j]+p*p*p//A(A..A)//i-1ijii+1j6.s[i,j]

7、←i//记录分割位置//7.fork←i+1toj−1do8.t←m[i,k]+m[k+1,j]+p*p*p//(A..A)(A..A)//i-1kjikk+1j9.ift,解得r=1m[2,2]=0m[3,3]=0

8、m[4,4]=0m[5,5]=0r=2m[2,3][2,3]2625=2625m[3,4][3,4]750=750m[4,5][4,5]1000=10