动态规划算法分析与探究

动态规划算法分析与探究

摘 要：动态规划是运筹学的一个分支。它是解决多阶段决策过程最优化问题的一种方法。动态规划就是为了使产生决策序列在符合某种条件下达到最优。动态规划思想在各类信息学中频繁的使用，其作用越来越受到人们的重视。本文就动态规划算法进行分析与探究，从而解决实际生活中的诸多问题。

引言

  算法是解决一系列问题的清晰指令，能够在有限的时间内获得所要求的输出。一个好的算法对于解决一个或者一类实际问题将给予很大帮助。评价一个算法优劣，主要体现在两个方面（排除错误算法的情况）。一、时间优劣性；二、空间优劣性。时间的优劣即在处理相同问题时，不同算法解决此问题所需的时间。时间的优劣换种方式表达就是算法的效率。另一方面，是空间优劣即在处理相同问题时，不同算法解决此问题所需占用的资源（计算机资源），主要体现在所占用内存资源上。总的来说，算法优劣由时间复杂度和空间复杂度来衡量。

   对于一种算法，判断是否是最优算法并不能单单通过解决一个或一类问题来说明。因为，对于一类的问题或许该算法的复杂度要低于其它算法，而解决另一类问题的复杂度可能要高于其它算法。因此，没有最好的算法，只有针对某一实际问题有最优的算法，该算法的时间复杂度和空间复杂度要低于其它算法。

1、动态规划简介

   1.1 动态规划基本思想

   动态规划的实质是分治思想和解决冗余，因此，动态规划是一种将问题实例分解为更小的、相似的自问题，并存储子问题的解而避免计算重复的自问题，已解决最优化问题的算法策略。

   动态规划法所针对的问题有一个显著的特征，即它所对应的子问题树中的子问题呈现大量的重复。动态规划法的关键就在于，对于重复出现的子问题，只在第一次遇到时加以求解，并把答案保存起来，让以后再遇到时直接引用，不必重新求解。

   1.2动态规划分类

   动态规划按其模型的不同可以分为：背包模型、最长非降子序列模型、最大字段和模型、LCS模型、线段覆盖问题模型、股票模型、连续段划分模型、游戏模型等。其中最为常见的就是背包问题，对于背包问题可以再细分为：0-1背包问题、无限背包问题、有限背包问题、有价值背包、小数背包等问题。

2、动态规划主要术语

  2.1 阶段

   用动态规划求解一个问题时，需要将问题的全过程恰当地划分成若干个相互联系的阶段，以便按一定的次序去求解。阶段的划分一般是根据时间和空间的自然特征来定的，一般要便于把问题转化成多阶段决策的过程。

   2.2 状态

   状态表示的是事物某一阶段的性质，状态通过一个变量来描述，这个变量称为状态变量。各个状态之间是可以相互转换的。

   2.3 决策

   对问题的处理中做出某种选择性的行动就是决策。一个实际问题可能要有多次决策，在每一个阶段中都需要有一次决策。一次决策就会从一个阶段进入另一个阶段，状态也就发生了转移。

    2.4策略和最优策略

   所有阶段按照约定的决策方法，依次排列构成问题的求解全过程。这些决策的总体称为策略。在实际问题中，从决策允许集合中找出最优效果的策略称为最优策略。

   2.5 状态转移方程

前一阶段的终点就是后一阶段的起点，这种关系描述了由K阶段到K+1阶段状态的演变规律，是关于两个相邻阶段状态的方程，称为状态转移方程，是动态规划的核心。

3、运用动态规划条件

   任何思想方法都有一定的局限性，超出了特定条件，它就失去了作用。同理，动态规划也需满足其使用条件。对于解决动态规划问题必须满足最优化原理和无后效性。

  最优化原理：无论过去状态和决策如何，对前面的决策所形成的状态而言，余下的决策必须构成最优策略。简而言之，一个最优化策略的自策略总是最优的。

K

        (图 1)

       如图1所示，路线I和J是A到C的最优路径，则根据最优化原理，路线J必须从B到C的最优路线。

   最优化原理是动态规划的基础，任何问题，如果失去了最优化原理的支持，就不可能用动态规划方法计算。

       无后效性：“过去的步骤只能通过当前状态影响未来的发展，当前的状态是历史的总结”。这条特征说明动态规划只适用于解决当前决策与过去状态无关的问题。状态，出现在策略任何一个位置，它的地位相同，都可实施同样策略，这就是无后效性。

4、动态规划计算步骤

  4.1 划分阶段

   按照问题的时间或空间特征，将问题分为若干个阶段。前提是这个若干个阶段一定要有序，即无后向性。

   4.2 选择状态

   将问题发展到各个阶段时所出现的各种客观情况用不同的状态表示。

   4.3 确定决策并写出状态转移方程

   状态转移就是根据上一阶段的状态和决策来导出本阶段的状态。

对于动态规划问题来说，阶段的划分是关键，必须依据题意分析，寻求合理的划分阶段的方法。依据计算最优值时得到的信息，构造问题的最优解。

接下来我用一个实例来说明解决动态规划问题的步骤。

[问题描述]：

设有一个正整数序列b₁，b₂，b₃，…，b_n，若下标为i₁<i₂<i₃<…<i_k且有b_i1≤b_i2≤… ≤b_ik则称存在一个长度为k的不下降序列。可能有多个不下降序列，输出最长序列的长度。

[样例输入]：

13　7　9　16　38　24　37　18

[样例输出]：

5               (7 9  16  24  37)

[问题分析]：

1、    分阶段：以数的个数为阶段。

2、    确定状态及状态变量：n个数的最长不下降序列长度。

3、    决策：跟前面的哪个数拼接成最长不降序列。

4、    策略和最优策略：最终解在那。

5、    状态转移方程：

[求解过程]：

1、以个数为阶段，从第二项开始计算，由于前面仅有1项，所以做一次比较，因7<13，不符合问题要求，不作任何改变，长度仍为1。

2、第三项的前面有2项，因此需要做两次比较，得到目前最长的不下降序列为2，情况如下表：

(图 2)

3、处理过程：在1，2，……，i-1项中，找出比a[i]小于等于的最长长度L；若L>0，则b[i]=L+1。

5、动态规划小结

动态规划所处理的问题是一个“多阶段决策问题”，目的是得到一个最优解（方案）。动态规划的实质是分治思想和解决冗余，因此，动态规划是一种将问题分解为更小的、相似的子问题，并存储子问题的解而避免计算重复的子问题，以解决最优化问题的算法策略。这类问题会有多种可能的解，每个解都有一个值，而动态规划找出其中最优（最大或最小）解。若存在多个最优解的话，它只取其中的一个。

(图 3)

动态规划与贪心算法类似，是通过多阶段决策过程来解决问题的，同时动态规划又与递归法类似，当问题不能分解为独立的阶段，却又符合最优原理（最优子结构性质）时，就比较适合用动态规划。

但动态规划与一般的递推不同点也比较明显，主要表现如下方面：

1、递推的边界条件一般很明显，而动态规划的边界条件比较隐蔽，容易被忽视；

2、递推的数学性一般较强，而动态规划的数学性相对较弱；

3、递推一般不划分阶段，而动态规划一般有较为明显的阶段；

4、动态规划往往是用来求一个最优值，而一般的递推往往是用来计数或是求一个值。

因此，总的来说，动态规划更加适合解决绝大多数最优化问题。但是，动态规划来解决问题并不一定是最优（复杂度较低），因此，具体问题需要具体分析，从而确定最优算法。