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

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. 如何确定计算矩阵连乘积的计算次序,使得依此次序计算矩阵连乘积需要的数乘次数最少.
穷举法:列举出所有可能的计算次序,并计算出每一种计算次序相应需要的数乘次数,从中找出一种数乘次数最少的计算次序。

1 2 3 4 5 6  下一页

Tags:动态 规划

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