WEB开发网
开发学院软件开发C++ C++动态规划 阅读

C++动态规划

 2010-11-16 13:05:18 来源:WEB开发网   
核心提示:算法复杂度分析:对于n个矩阵的连乘积,设其不同的计算次序为P(n)由于每种加括号方式都可以分解为两个子矩阵的加括号问题(A1...Ak)(A(k+1)…An)可以得到关于P(n)的递推式如下:动态规划:将矩阵连乘积A(i)A(i+1)…A(j)简记为A[i:j],C++动态规划(2),这里
算法复杂度分析:
对于n个矩阵的连乘积,设其不同的计算次序为P(n)
由于每种加括号方式都可以分解为两个子矩阵的加括号问题
(A1...Ak)(A(k+1)…An)可以得到关于P(n)的递推式如下:
动态规划:将矩阵连乘积A(i)A(i+1)…A(j)简记为A[i:j],这里 i <= j。
考察计算A[i:j]的最优计算次序。设这个计算次序在矩阵A(k)和A(k+1)之间将矩阵链断开,i <= k < j, 则其相应完全加括号方式为(A(i)A(i+1)...A(k)) * (A(k+1)A(k+2)...A(j))。
计算量:A[i:k]的计算量加上A[k+1,j],再加上A[i:k] * A[k+1][j]的计算量。
分析最优解的结构 
特征:计算A[i:j]的最优次序所包含的计算矩阵子链 A[i:k]和A[k+1:j]的次序也是最优的。
矩阵连乘计算次序问题的最优解包含着其子问题的最优解。这种性质称为最优子结构性质问题的最优子结构性质是该问题可用动态规划算法求解的显著特征
建立递归关系 
设计算A[i:j],1 <= i <= j <= n,所需要的最少数乘次数m[i,j],则原问题的最优值为m[1,n]
当i = j时,A[i:j]=Ai,因此,m[i,i] = 0,i = 1,2,…,n
当i < j时,m[i,j] = m[i,k] + m[k+1,j] + p(i-1)p(k)p(j)
这里A(i)的维数为p(i-1)*(i)(注:p(i-1)为矩阵A(i)的行数,p(i)为矩阵A[i]的列数)
可以递归地定义m[i,j]为:
k的位置只有j - i种。
计算最优值 
对于1 <= i <= j <= n不同的有序对(i,j)对应于不同的子问题。因此,不同子问题的个数最多只有:
(大括号表示C(n,2),组合的意思。后面的符号表示 “紧渐近界记号”)
但是,在递归计算时,许多子问题被重复计算多次。这也是该问题可用动态规划算法求解的又一显著特征。
用动态规划算法解此问题,可依据其递归式以自底向上的方式进行计算。在计算过程中,保存已解决的子问题答案。每个子问题只计算一次,而在后面需要时只要简单查一下,从而避免大量的重复计算,最终得到多项式时间的算法。
用动态规划法求最优解 
连乘矩阵假如为:
计算过程为:

上一页  1 2 3 4 5 6 7  下一页

Tags:动态 规划

编辑录入:爽爽 [复制链接] [打 印]
赞助商链接