分享

更多

   

动态规划详解 第一章...

2008-12-10  太阳000
动态规划详解 第一章

首先让我们看一个例子:
例1:如下图有一个数字三角阵,请编一个程序计算从顶点至底的某处的一条路径,使该路径所经过的数字的和最大。每一步可沿左斜线向下或右斜线向下走。
                                    7
                                   5  3
                                  4  2  1
                                 2  1  3  7
这个问题的实质实际上是一个有向图中最长路经问题,可以用经典的图论算法或者搜索来解决。
考虑如何用搜索法来解这道题,从第一个点开始扩展,每次扩展2个可行节点,直到达到数字三角形的底部,从所有的可行路径中找出最优值,这样做的复杂度是o(2^n),当n很大的时候,普通的搜索法将不可行。
观察发现,搜索的效率低下很大程度上是因为做了大量的重复运算,因为对于任何一个节点,从他开始向下拓展的最优值是确定的,这启发了我们应当充分利用之前的运算结果。
下面我们来进行深入的分析,假如已经走第I行第J列,此时最大累加和S[I,J]应选S[I-1,J],S[I-1,J+1]中较大者再加上(I,J)处的值A[I,J],即下式
S[I,J]=A[I,J]+MAX(S[I-1,J],S[I-1,J+1])
所以我们可以从第一行开始,向下逐行推出每一处位置的最大累加和S,最后从底行的N个S中选出最大的一个即为所求,这种算法的复杂度为o(n^2),比较搜索法,已经大大的降低了,这种充分利用已经计算出结果的方法,就叫做动态规划。

通过上面的例子,我们对“动态规划”有了一个初步认识,它所处理的问题是一个“多阶段决策问题”。我们现在对一些概念进行具体定义:
状态(State):它表示事物的性质,是描述“动态规划”中的“单元”的量。如例1中的每个节点(指节点处的最大值)都为单个的状态。
阶段(Stage):阶段是一些性质相近,可以同时处理的状态集合。通常,一个问题可以由处理的先后次序划分为几个阶段。如例1中的问题,每一行若干节点组成一个阶段。一个阶段既可以包含多个状态,也可以只包含一个状态。描述各阶段状态的变量称为状态变量,例1中可用S[4 , j]来表示第四阶段(即第四行)走到第j列的最大值,即第四阶段状态变量。
状态转移方程:是前一个阶段的状态转移到后一个的状态的演变规律,是关于两个相邻阶段状态的方程,是“动态规划”的中心。
如例1中: S[I,J]=A[I,J]+MAX(S[I-1,J],S[I-1,J+1])
决策(Decision):每个阶段做出的某种选择性的行动。它是我们程序所需要完成的选择。如例1中MAX(S[I-1,J],S[I-1,J+1])
动态规划所处理的问题是一个“多阶段决策问题”,一般由初始状态开始,通过对中间阶段决策的选择,达到结束状态。这些决策形成了一个决策序列,同时确定了完成整个过程的一条活动路线(通常是求最优的活动路线)

从上面的讲解我们可以发现:动态规划并不像一种算法,而更像一种思考方式

下面,我们来讨论动态规划的应用范围,要确定一个问题是否能用动态规划,需要考虑两个方面:
一:最优子结构
即一个问题的最优解只取决于其子问题的最优解,也就是说,非最优解对问题的求解没有影响。我们再来看一个问题:
例二:有4个点,分别是A、B、C、D,相邻两点用两条连线,表示两条通行的道路,给出每条道路的长度。我们定义从A到D的所有路径中,长度除以4所得余数最小的路径为最优路径。求一条最优路径。

很多初学者往往会认为这道题也可以采用动态规划的方法,但实际并不如此,考虑这种情况
假如A-B的两条道路分别为2,3,B-C的两条道路分别为1,4。如果采用动态规划,节点B的最优值为2,节点C的最优值2,但际上到达C的最优值应该是0,即3-1这条线路。
也就是说,C的最优取值不是由B的最优取值决定的,其不具有最优子结构。
由此可见,并不是所有的“决策问题”都可以用“动态规划”来解决。所以,只有当一个问题呈现出最优子结构时,“动态规划”才可能是一个合适的侯选方法。

二:无后效性
即一个问题被划分阶段后,阶段I中的状态只能由阶段I-1中的状态通过状态转移方程得来,与其他状态没有关系,特别是与未发生的状态没有关系,这就是无后效性。

<<<<<<<<<<<<<<<<<<<END>>>>>>>>>>>>>>>>>>

    本站是提供个人知识管理的网络存储空间,所有内容均由用户发布,不代表本站观点。如发现有害或侵权内容,请点击这里 或 拨打24小时举报电话:4000070609 与我们联系。

    猜你喜欢

    0条评论

    发表

    类似文章 更多
    喜欢该文的人也喜欢 更多