动态规划算法研究.pdf

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

1、I一学窭⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯一动态规划算法研究天津师范大学计算机与信息工程学院宁静雁【摘要】动态规划算法通常用于求解具有某种最优性质的问题，在这类问题中，可能会有许多可行解，每一个解都对应于一个值，我们希望找到具有最优值的解。本文主要研究动态规划算法的特点、基本思想以及其解决问题的具体步骤，详细分析其用于解决矩阵连乘问题的上的算法设计，并给出算法实现。【关键词】动态规划；矩阵连乘问题；最优子结构；递归算法；重叠子问题1．动态规划动态规划算法适用于解最优化问题，通常重要特征。动态规划是运筹学的一个分支，是求解可按一下4

2、个步骤设计：2．3建立递归关系决策过程最优化的数学方法。20世纪5O年代初找出最优解的性质，并刻画其结构特征。设计算矩阵连乘积A[i：J]，1≤i≤j≤n，美国数学家R．E．Bel1man等人在研究多阶段决递归地定义最优值。所需要的最少数乘次数为m[i，j]，则原问题策过程的优化问题时，提出了著名的最优化原以自底向上的方式计算出最优值。的最优值为nl[1，n]，当i=j时，A[i：J]=A．，理，把多阶段过程转化为一系列单阶段问题，根据计算最优值时得到的信息，构造最优因此，13[i，i]=O，i=i，2，⋯，n；当i

3、

4、的问题分解为更小给定n个矩阵{A，，A，⋯，A}，其中A，其中，P>l是A，的行数，P是Ak的列数，P．的、相似的子问题，并存储子问题的解而避免与A，．是可乘的，i=l，2，⋯，n—l。考察这n个是AI的列数计算重复的子问题，以解决最优化问题的算法矩阵的连乘积A．，⋯，A。由于矩阵乘法满足结m[iJ【j]给出了最优值，即计算A[i：J]所策略。合律，所以计算矩阵的连乘可以有许多不同的需的最少数乘次数，同时还确定了计算A[i：j]1．1基本思想计算次序。这种计算次序可以用加括号的方式的最优次序中的断开位置k，在计算出最

5、优值动态规划算法的基本思想是将待求解问题来确定。若一个矩阵连乘积的计算次序完全确后，可递归地由这个断开位置构造出相应的最分解成若干个子问题，先求解子问题，然后从定，也就是说该连乘积已完全加括号，则可以优解。这些子问题的解得到原问题的解。适合于用动依此次序反复调用2个矩阵相乘的标准算法计2．4计算最优值态规划法求解的问题，经分解得到的子问题往算出矩阵连乘积。在递归计算时，许多_了问题被重复计算往不是相互独立的，可以用一个表来记录所有完全加括号的矩阵连乘积可递归地定义多次。这也是该问题可用动态规划算法求解的已解决的子问题

6、的答案，不管该子问题以后是为又一显著特征。用动态规划算法解此问题，可否被用到，只要它被计算过，就将其结果填入(1)单个矩阵是完全加括号的：根据其递归式以自底向上的方式进行计算。在表中，而在需要时再找出已求得的答案，这样(2)矩阵连乘积A是完全加括号的，则A可计算过程中，先找到求得的予问题的答案并保就可以避免大量的重复计算，从而得到多项式表示为2个完全加括号的矩阵连乘积B和C的乘存，这样使得每个子问题只需计算一次，而在时间算法。积并加括号，即A=(BC)。后面需要时只要简单查一下，从而避免大量的1．2求解问题特征矩阵连

7、乘积的计算顺序不同，总的数乘次重复计算，最终得到多项式时间的算法。动态规划算法的有效性依赖于问题本身所数也不同。举例如下：下面给出动态规划算法MatrixChain，此具有的两个重要性质：最优子结构性质和子问D1D2D分别是5*50，50*100和l00．10的矩算法除了输出最优值数组m外还输出记录最优题重叠性质。阵，如果按照((D．D)D：)来计算，则计算所需断开位置的数组S：1．2．1最优子结构的总数乘次数是5*50*i00+5．100．10=30000；voidMatrixChain(intp，intn，int

8、原问题的最优解包含着其子问题的最优如果按照(D(DD。))来计算则需要的数乘次数蛔n，int$s)解，这种性质称为最优子结构性质。在分析问是50．100．IO+5$5O1O=5250oO，整整是前者的{for(inti=1：i<=n：i+_)m[i儿ij题的最优子结构性质时，所用的方法具有普遍1．75倍。因而在计算矩阵连乘积时不同的加括：O：／