C++动态规划
2010-11-16 13:05:18 来源：WEB开发网核心提示：算法总体思想 动态规划算法与分治法类似，其基本思想也是将待求解问题分解成若干个子问题，C++动态规划，但是经分解得到的子问题往往不是互相独立的，不同子问题的数目常常只有多项式量级，而在后面需要时只要简单查一下，从而避免大量的重复计算，在用分治法求解时，有些子问题被重复计算了许多次
算法总体思想
动态规划算法与分治法类似，其基本思想也是将待求解问题分解成若干个子问题。
但是经分解得到的子问题往往不是互相独立的。不同子问题的数目常常只有多项式量级。在用分治法求解时，有些子问题被重复计算了许多次。
如果能够保存已解决的子问题的答案，而在需要时再找出已求得的答案，就可以避免大量重复计算，从而得到多项式时间算法。
动态规划基本步骤:
(1)找出最优解的性质，并刻划其结构特征。
(2)递归地定义最优值。
(3)以自底向上的方式计算出最优值。
(4)根据计算最优值时得到的信息，构造最优解。
实例一、完全加括号的矩阵连乘积
问题可递归定义：
（1）单个矩阵是完全加括号的；
（2）矩阵连乘积A是完全加括号的 ，则A可表示为2个完全加括号的矩阵连乘积B和C的乘积并加括号，即 A = （BC）。
设有四个矩阵A,B,C,D它们的维数分别是: A = 50*10 , B = 10*40 , C = 40*30 , D = 30*5
总共有五中完全加括号的方式：
例如：((A(BC))D): 10 * 40 * 30 + 10 * 30 * 50 + 50 * 30 * 5 = 34500
给定矩阵{A1, A2, A3,..., An}，其中Ai与A(i+1)是可乘的。i = 1,2,3, ..., n - 1。考察这n个矩阵的连乘积A1*A2*A3...An.
由于矩阵乘法满足结合律，所以计算矩阵的连乘可以有许多不同的计算次序。这种计算次序可以用加括号的方式来确定。
若一个矩阵连乘积的计算次序完全确定，也就是说该连乘积已完全加括号，则可以依此次序反复调用2个矩阵相乘的标准算法计算出矩阵连乘积。
矩阵连乘问题
给定矩阵{A1, A2, A3,..., An}，其中Ai与A(i+1)是可乘的。i = 1,2,3, ..., n - 1。考察这n个矩阵的连乘积A1*A2*A3...An. 如何确定计算矩阵连乘积的计算次序，使得依此次序计算矩阵连乘积需要的数乘次数最少.
穷举法：列举出所有可能的计算次序，并计算出每一种计算次序相应需要的数乘次数，从中找出一种数乘次数最少的计算次序。
算法复杂度分析：
对于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)，组合的意思。后面的符号表示 “紧渐近界记号”）
但是，在递归计算时，许多子问题被重复计算多次。这也是该问题可用动态规划算法求解的又一显著特征。
用动态规划算法解此问题，可依据其递归式以自底向上的方式进行计算。在计算过程中，保存已解决的子问题答案。每个子问题只计算一次，而在后面需要时只要简单查一下，从而避免大量的重复计算，最终得到多项式时间的算法。
用动态规划法求最优解
连乘矩阵假如为：
[]
- 好的评价 如果觉得好，就请您
0%(0) 
- 差的评价 如果觉得差，就请您
0%(0) 
中查找“C++动态规划”更多相关内容
中查找“C++动态规划”更多相关内容更多精彩
赞助商链接