关于动态规划算法的研究

《关于动态规划算法的研究》由会员上传分享，免费在线阅读，更多相关内容在工程资料-天天文库。

1、关于动态规划算法的研究一、动态规划的基本思想在比较基本的算法设计思想里，动态规划是比较难于理解，难于抽象的一种，但是却乂十分重要。动态规划的实质是分治思想和解决兀余，因此它与分治法和贪心法类似，它们都是将问题的实例分解为更小的、相似的子问题，但是动态规划又有口己的特点。贪心法的当前选择可能要依赖于已经作出的选择，但不依赖于还未做出的选择和了问题，因此它的特征是由顶向下，一步一步地做出贪心选择，但不足的是，如果当前选择可能耍依赖了问题的解时，则难以通过局部的贪心策略达到全局最优解。相比而言，动态规划则可以处理不具有贪心实质的问题。在用分治法解决问

2、题时，由于了问题的数hl往往是问题规模的指数函数，因此对时间的消耗太大。动态规划的思想在于，如果各个子问题不是独立的，不同的子问题的个数只是多项式量级，如果我们能够保存已经解决的子问题的答案，而在需要的时候再找出己求得的答案,这样就可以避免大量的垂复计算。由此而來的棊本思路是，川一个表记录所冇己解决的了问题的答案，不管该问题以后是否被用到，只要它被计算过，就将其结果填入表中。比鮫感性的说，其实动态规划的思想是对贪心算法和分治法的一种折衷，它所解决的问题往往不具冇可爱的贪心实质，但是各个了问题又不是完全零散的，这时候我们用一定的空间來换取时间，就

3、可以提高解题的效率。二、动态规划的棊本步骤动态规划算法通常用于求解具有某种最优性质的问题。在这类问题中，对能会有许多对行解。每一个解都对应于一个值，我们希望找到具冇最优值（最大值或最小值）的那个解。设计一个动态规划算法，通常可以按以下儿个步骤进行：（1）找出最优解的性质，并刻画其结构特征。（2）递归地定义最优值。（3）以口底向上的方式计算出最优值。（4）根据计算最优值时得到的信息，构造一个最优解。其中（1）——（3）步是动态规划算法的基木步骤。在只盂要求出最优值的情形，步骤（4）可以省去。若需要求出问题的一个最优解，则必须执行步骤（4）。此时，

4、在步骤（3）中计算最优值时，通常需记录更多的信息，以便在步骤（4）中，根据所记录的信息，快速构造出一个最优解。三、典型的动态规划举例——矩阵连乘问题作为经典的动态规划算法举例，矩阵连乘问题很好地展现了动态规划的特点和实用价值。给定n个矩阵{Al,A2,,An},其中Ai与Ai+1是可乘的,i=l,2,...n—l。现在要计算这n个矩阵的连乘积。由于矩阵的乘法满足结合律，所以通过加括号nJ以使得计算矩阵的连乘积有许多不同的计算次序。然而采用不同的加扩号方式，所需要的总计算量是不一样的。若A是一个p*q矩阵，B是一个q*r矩阵，则其乘积C二AB是一

5、个p*r矩阵。如果用标准算法计算C,总共需要pqr次数乘。现在来看一个例子。Al,A2,A3分别是10*100,100*5和5*50的矩阵。如果按照((A1A2)A3)來计算，则计算所需的总数乘次数是10*100*5+10*5*50二7500。如果按照(Al(A2A3))來计算,则需要的数乘次数是100*5*50+10*100*50=75000,整整是前者的10倍。由此可见，在计算矩阵连乘积时，不同的加括号方式所导致的不同的计算对计算量冇很大的影响。如何确定计算矩阵连乘积A1A2,的一个计算次序，使得依此次序计算矩阵连乘积需耍的数乘次数最少便成

6、为一个问题。对于这个问题，穷举法虽然易于入手，但是经过计算，它所需要的计算次数是n的指数函数,因此在效率上显得过于低下。现在我们按照动态规划的基本步骤来分析解决这个问题，并比较它与穷举法在时间消耗上的差异。(1)分析最优解的结构。现在,将矩阵连乘积AiAi+l...Aj简记为A[i:j]o对于A[l:n]的一个最优次序，设这个计算次序在矩阵Ak和Ak+1之间将矩阵链断开(l<=k

7、],总计算量为A[l:k]的计算量加上A[k+l:n]的计算量，再加上A[l:k]和A[k+l:n]相乘的计算量。通过反证法可以证明，问题的关键特征在于，计算A[l:n]的一个最优次序所包含的计算矩阵子链A[l:k]和A[k+l:n]的次序也是最优的。因此，矩阵连乘积计算次序问题的最优解包含着其子问题的最优解。这种最优子结构性质是该问题可以用动态规划解决的重要特征。(2)建立递归关系定义最优值。设计算A[i:j](l<=i<=j<=n)所需的最少数乘次数为m[i][j],则原问题的最优值为m[l][n]o而且易见,当i二j时,m[i][j]=0

8、o根据上述最优了结构性质，当Kj时，若计算A[i:j]的最优次序在Ak和Ak+lZ间断开，可以定义m[i][j]=m[i][k]+m[k+l][j]+