运筹学课程作业-动态规划算法的应用

1、中 国 地 质 大 学研究生课程论文封面课程名称 运筹学 教师姓名 王广民 研究生姓名 谢盼盼 研究生学号 120100887 研究生专业 工商管理 所在院系 经济管理学院 类别: A.博士 B.硕士 C.进修生 日期: 2010 年 12 月 25 日 评 语对课程论文的评语:平时成绩：课程论文成绩：总 成 绩：评阅人签名：注：1、无评阅人签名成绩无效；2、必须用钢笔或圆珠笔批阅，用铅笔阅卷无效；3、如有平时成绩，必须在上面评分表中标出，并计算入总成绩。动态规划算法的应用摘要：从动态规划的基本概念入手，介绍了多阶段决策问题、阶段与状态、决策与策略等一些专有名词的定义；利用一些常见的实例阐述了

2、动态规划在设计与实现时的多样性、模式性和技巧性等特点；最后通过一个具体问题的解决过程，可以看出动态规划是一个必不可少的有利工具。通过问题描述、样例分析、算法设计、问题实现、测试结果等几个步骤详细讨论了动态规划在应用中的实现过程和思考方法，体现出在应用中相应的实践指导意义。关键词：动态规划 ；算法 引言动态规划（Dynamic Programming）是运筹学的一个分支，是求解决策过程（Decision Process）最优化的数学方法。20世纪50年代初美国数学家R.EBellman等人在研究多阶段决策过程（Multistep Decision Process)的优化问题时，提出了著名的最优化

3、原理(Principle of Optimality)，把多阶段过程转化为一系列单阶段问题，逐个求解，创立了解决这类过程优化问题的新方法动态规划。动态规划问世以来，在城市规划、经济管理、生产调度、工程技术和最优控制等方面得到了广泛的应用。例如神经网络、生物有机体DNA的相似程度分析、最短路线、库存管理、资源分配、资产投资、证券交易、经营决策、企业生产物流控制、农业灌溉阅、施工计划安排、单一品种项目的生产批量问题、设备更新、最优化设计、学习方法、排序、装载等问题，用动态规划方法比用其它方法求解更为方便。动态规划主要用于求解以时间划分阶段的动态过程的优化问题，而且一些与时间无关的静态规划（如线性规

4、划、非线性规划），只要人为地引进时间因素，把它视为多阶段决策过程，也可以用动态规划方法方便地求解。动态规划的基本概念动态规划是算法设计的一种重要手段，在各行各业的程序设计中被应用得越来越普遍。因此，如何更深入地了解动态规划，从而更为有效地运用算法设计的这个有力武器，是一个值得深入研究的问题。首先来了解一些动态规划的基本概念：（1）阶段与阶段变量 将所有问题的过程，按照时间或空间特征，划分成若干个相互联系的子问题，则每个子问题称为一个阶段。用来表示阶段的变量称为阶段变量。（2）状态与状态变量过程中各个阶段开始时所处的客观条件或位置称为状态。动态规划的状态具有如下性质：当某阶段状态给定后，在这阶段

5、以后过程的发展不受这阶段以前各段状态的影响。描述各阶段所处状态的变量成为状态变量。状态变量取值的集合称为状态集合。（3）决策与决策变量当各段状态取定后，就可以做出不同的决定和选择，从而确定下一阶段的状态，这种决定称为决策。表示决策的变量称为决策变量。决策变量可选择的范围称为允许决策集合。（4）状态转移前阶段的状态和决策决定了下一阶段的状态，它们之间的关系称为状态转移。（5）策略由阶段K1到阶段K=n的全部过程中，每个阶段所选择的决策构成一个决策序列，称之为一个策略。（6）后部子过程与后部子策略从K阶段某状态Sk出发到终点的过程称为后部过程。后部子过程对应的后部子决策序列称为后部子策略。（7）阶

6、段指标K阶段中，评价由状态S出发作出决策所产生的效果的数量指标称为阶段指标。（8）指标函数与最优指标函数评价由K阶段S状态出发到终点的后部子策略产生效果的数量指标，由于该指标由状态S和后部子策略所决定，所以称为指标函数，可以用它来评价和衡量所实现过程的优劣。由K阶段S状态出发，所有可能的后部子策略所产生的指标函数值中最优者称为最优指标函数。动态规划的设计与实现有了动态规划的基本概念后，在实际中对其设计与实现时所体现的几种特性也是值得关注并具有指导意义的。动态规划的多样性假设你想以最美观的方式布置花店的橱窗。现在你有F束不同品种的花束，同时你也有至少同样数量的花瓶被按顺序摆成一行。这些花瓶的位置

7、固定于架子上，并从1至V顺序编号，V是花瓶的数目，从左至右排列，则最左边的是花瓶1，最右边的是花瓶V。花束可以移动，并且每束花用1至F间的整数唯一标识。标识花束的整数决定了花束在花瓶中的顺序，如果IJ，则令花束I必须放在花束J左边的花瓶中。例如，假设一束杜鹃花的标识数为1，一束秋海棠的标识数为2，一束康乃馨的标识数为3，所有的花束在放入花瓶时必须保持其标识数的顺序，即：杜鹃花必须放在秋海棠左边的花瓶中，秋海棠必须放在康乃馨左边的花瓶中。如果花瓶的数目大于花束的数目。则多余的花瓶必须空置，且每个花瓶中只能放一束花。每一个花瓶都具有各自的特点。因此，当各个花瓶中放入不同的花束时，会产生不同的美学效

8、果，并以美学值（一个整数）来表示，空置花瓶的美学值为零。在上述例子中，花瓶与花束的不同搭配所具有的美学值，如表 1.1所示。 花瓶花束123451（杜鹃）723-5-24162（秋海棠）521-410233（康乃馨）-215-4-2020根据上表，杜鹃花放在花瓶2中，会显得非常好看；但若放在花瓶4中则显得十分难看。为取得最佳美学效果，你必须在保持花束顺序的前提下，使花束的摆放取得最大的美学值。如果有不止一种的摆放方式具有最大的美学值，则其中任何一直摆放方式都可以接受，但你只要输出任意一种摆放方式。这虽然是较为简单的一个问题，但其中大有文章可作。说它简单，是因为它有序，因此一眼便可看出这个问题应

9、该用动态规划来解决。但是，如何动态规划呢？如何划分阶段，又如何选择状态呢？方法1以花束的数目来划分阶段。在这里，阶段变量k表示的就是要布置的花束数目（前k束花），状态变量Sk表示第k束花所在的花瓶。而对于每一个状态Sk，决策就是第k-1束花应该放在哪个花瓶，用uk表示。最优指标函数丘（Sk）表示前k束花，其中第k束插在第Sk个花瓶中，所能取得的最大美学值。状态转移方程为 Sk-1 = uk规划方程为 fk（Sk）= max（fk-1（uk）+A（k, Sk） kuk Sk （其中A（I,j）是花束i插在花瓶j中的美学值）边界条件f0（s0）= 0 （0s0V）（V是花瓶总数，事实上这是一个虚拟

10、的边界）方法2 以花瓶的数目来划分阶段。在这里阶段变量k表示的是要占用的花瓶数目（前k个花瓶），状态变量Sk表示前k个花瓶中放了多少花。而对于任意一个状态Sk，决策就是第Sk束花是否放在第k个花瓶中，用变量uk=1或0来表示。最优指标函数fk（Sk）表示前k个花瓶中插了Sk束花，所能取得的最大美学值。状态转移方程为 Sk-1 = Sk - uk规划方程为 fk（Sk）= max（fk-1（Sk - uk）+ ukA（Sk , k） kuk Sk边界条件f0（s0）= 0 （0s0V）两种划分阶段的方法，引出了两种状态表示法，两种规划方式，但是却都成功地解决了问题。只不过因为决策的选择有多有少，

11、所以算法的时间复杂度也就不同。这个例子具有很大的普遍性。有很多的多阶段决策问题都有着不止一种的阶段划分方法，因而往往就有不止一种的规划方法。有时各种方法所产生的效果是差不多的，但更多的时候，就像上述例子一样，两种方法会在某个方面有些区别。动态规划的模式性动态规划的设计有着一定的模式，一般都要经历以下几个步骤。划分阶段：按照问题的时间或空间特征，把问题分为若干个阶段。注意这若干个阶段一定要是有序的或者是可排序的，否则问题就无法求解。选择状态：将问题发展到各个阶段时所处于的各种客观情况用不同的状态表示出来。当然，状态的选择要满足无后效性。确定决策并写出状态转移方程：之所以把这两步放在一起，是因为决

12、策和状态转移有着天然的联系，状态转移就是根据上一阶段的状态和决策来导出本阶段的状态。所以，如果确定了决策，状态转移方程也就写出来了。但事实上，常常是反过来做，根据相邻两段的各状态之间的关系来确定决策。写出规划方程（包括边界条件）：一般说来，只要阶段、状态、决策和状态转移确定了，要写出规划方程还是比较简单的。图2.1动态规划实现的模式框架N-S图掌握了动态规划的模式性，在用动态规划考虑问题时就可以把主要的精力放在理论的设计上面。一旦设计成熟，问题也就基本上解决了，而且在设计算法时也可以按部就班地进行。动态规划的技巧性上面所说的动态规划的模式性，主要指的是实现方面。而在设计方面，虽然它有较为严格的

13、步骤性，但是它的设计思想却是没有一定的规律可循的。这就需要在实践当中不断地去掌握动态规划的技巧，下面仅就一个例子谈一谈技巧性。图2.2街道问题 图2.3 街道问题虚线划分阶段 图2.4街道问题重新划分阶段街道问题：在图2.2中找出从左下角到右上角的最短路径，每步只能向右方或上方走。这是一个简单而又典型的动态规划问题，许多介绍动态规划的书与文章中都拿它来做例子。通常，书上的解答是这样的：按照图2.3中的虚线来划分阶段，即阶段变量k表示走过的步数，而状态变量Sk表示当前处于这一阶段上的哪一点（各点所对应的阶段和状态已经用ks在地图上标明）。这时的模型实际上己经转化成了一个特殊的多段图。用决策变量u

14、k=0表示向右走，uk=1表示向上走，则状态转移方程如下：Sk 1 + uk （Krow）Sk-1 = Sk + uk （Krow）（这里的row是地图竖直方向的行数）可以看到，这个状态转移方程需要根据k的取值分两种情况讨论，显得非常麻烦。相应的，把它代入规划方程而付诸实现时，算法也很繁。因而在实现时，一般是不会这么做的，而代之以下面方法：将地图中的点规则地编号如图2.4，得到的规划方程如下： fi-1,j + Distance（i-1,j）（i,j）fi,j =Min fi-1,j + Distance（i-1,j）（i,j）（这里Distance表示相邻两点间的边长）这样做确实要比上面的方

15、法简单多了，但是它已经破坏了动态规划的本来面目，而不存在明确的阶段特征了。如果说这种方法是以地图中的行（A、B、C、D）来划分阶段的话，那么它“状态转移”就不全是在两个阶段之间进行的了。也许这没什么大不了的，因为实践比理论更有说服力。但是，如果把问题扩展一下：在地图中找出从左下角到右上角的两条路径，两条路径中的任何一条边都不能重叠，并且要求两条路径的总长度最短。这时，再用这种“简单”的方法就很难实现了。如果一定要套用这种方法的话，则最优指标函数就需要有四维的下标，并且难以处理两条路径“不能重叠”的问题。而回到原先“标准”的动态规划法，就会发现这个问题很好解决，只需要加一维状态变量就可以实现了。

16、即用sk=（ak，bk）分别表示两条路径走到阶段k时所处的位置，相应的，决策变量也增加一维，用uk=（xk，yt）分别表示两条路径的行走方向。状态转移时将两条路径分别考虑： ak-1 = a-1+xk（Krow）bk-1 = b-1+ykak-1 = a + xk（Krow）bk-1 = b + yk在写规划方程时，只要对两条路径走到同一个点的情况稍微处理一下，减少可选的决策个数： min （fk-1（TK（Sk，Uk）+两条边长）ak =bk Uk=（0,1）,（1,0）fk（sk）=min （fk-1（TK （Sk，Uk）+两条边长）akbkUk=（0,1）,（1,0）从这个例子中可以总结

17、出设计动态规划算法的一个技巧:状态转移一般是在相邻的两个阶段之间（有时也可以在不相邻的两个阶段间），但是尽量不要在同一个阶段内进行。动态规划是一种很灵活的算法设计方法，在动态规划算法的设计中，类似的技巧还有很多。要掌握动态规划的技巧，有两条途径:一是要深刻理解动态规划的本质，这也是为什么一开始就探讨它的本质的原因；二是要多实践，不但要多应用，还要学会从应用中探寻规律，总结技巧。动态规划算法在具体问题中的应用所选的例子产生的数据量不是太大，简单动态规划能够解决。问题描述在河上有一座独木桥，一只青蛙想沿着独木桥从河的一侧跳到另一侧。在桥上有一些石子，青蛙很讨厌踩在这些石子上。由于桥的长度和青蛙一次

18、跳过的距离都是正整数，我们可以把独木桥上青蛙可能到达的点看成数轴上的一串整点：0，1，L（其中L是桥的长度）。坐标为0的点表示桥的起点，坐标为L的点表示桥的终点。青蛙从桥的起点开始，不停的向终点方向跳跃。一次跳跃的距离是S到T之间的任意正整数（包括S，T）。当青蛙跳到或跳过坐标为L的点时，就算青蛙已经跳出了独木桥。事先给出独木桥的长度L，青蛙跳跃的距离范围S，T，桥上石子的位置。你的任务是确定青蛙要想过河，最少需要踩到的石子数。输入文件：输入文件river.in的第一行有一个正整数L(1L109)，表示独木桥的长度。第二行有三个正整数S，T，M，分别表示青蛙一次跳跃的最小距离，最大距离，及桥上

19、石子的个数，其中1ST10，1M100。第三行有M个不同的正整数分别表示这M个石子在数轴上的位置（数据保证桥的起点和终点处没有石子）。所有相邻的整数之间用一个空格隔开。输出文件：输出文件river.out只包括一个整数，表示青蛙过河最少需要踩到的石子数。样例输入：1023523567样例输出：2数据规模：对于30%的数据，L10000；对于全部的数据，L109 。时限：2秒。样例分析桥长度L=10，最短能跳S=2，最长能跳T=3，石子数M=5，5个石子所在位置分别为2、3、5、6、7。跳过桥最少要踩到的石子数是2个，如图2.1所示：图3.1“过河”问题样例分析算法分析1、这个问题初看是一个典型

20、的搜索问题，从河的一侧到河的另一侧，要找最少踩到的石头数。只要时间和空间足够，利用递归穷举每一种跳过桥的方法，那是完全可以实现的，也是最容易想到的，有人就是这么做的，还通过了一个数据量比较小的测试数据。但从最大数据范围来看，1.109长度的桥，就算是O（n）的算法也不能在一秒内出解。2、当然，最特殊的情况应该是S和T相等，即每次只能以相同长度进行跳跃，则只要统计相应倍数上的石子数即可。3、如果使用以石子分阶段的一维动态规划，时间复杂度O（L）。最多也只有100、100的时间。但是这样分状态就十分复杂。因为石头的分布是没有任何规律的，而且会有后效性。4、只有以桥上的每个相等距离间隔的整数点作为动

21、态规划的对象，时间复杂度为O（L），从最优子结构和无后效性的两个方面来看整个问题：到达每一个点的最少石子数可由距离当前点之前长度为S和T间的一些点确定（刚开始的几个点可以通过临时改变S和T的值来处理），而且一旦该值确定，则不会受后续点取值的影响；另外，距离当前点之前长度为S和T间的一些点的最终值的确定又可以沿用以上方法，这就从理论上满足了最优子结构和无后效性的要求，可以使用这种动态规划实现。可以总结出以下动态转移方程（记：Ai表示i点上的石子数目，Pi表示到达i点的最少石子数）： ； （iS） minPi+Ai； （iT）Pi = 0js minPi+Ai； （iT） i-Tji-s样例中的数

22、据按照动态规划方法实现，得到的P数组序列如图2.2所示，初始点的值为0，因为1号点位置不能达到，所以到达该点所要踩到的最少石子数为二，依次计算，最后的结果应该从含终点在内的之后几个点的数值取最小值，最小值为2。图3.2“过河”问题样例的动态规划实现过程5、由于L可能达到109，从时间复杂度和空间复杂度来说还是不能满足要求，能不能减少不必要的操作呢。再看，从桥的一侧到另一侧，中间最多只有100个石子。假设桥长为最大值（109），石头数也为最大值（100）。这样中间一定会有很多“空长条”（两个石子中的空地），处理时把这些跳过，就会减少很多次运算。关键是找出每一个可以跳过的“空长条”。其实可以断言：

23、两个相隔较远（距离大于100）的点可以移近一点，通过移动，则相应数据在时间和空间上都能接受了。因为有石子的点，如果后续有很长的空长条，则到达这些空长条点的最少石子数逐渐趋于一个稳定的值。青蛙跳1次，2次，3次的距离范围分别是s，T，2S，2T，3S，3T当NS，NT与(N+1)S，(N+1)T相接的时候，说明NS，+的距离青蛙都是可以跳到的。假设两个相邻石子的坐标是x和Y（XY），青蛙到达X或者越过X时到达的位置是A（XAX+Y）。当X和Y之间的距离很大时，无论A的值是多少，Y-1，Y-2，Y-T的位置青蛙都可以跳到。因此可以缩短X和Y之间的距离，只要保证Y-1，Y-2，Y-T这T个位置，青蛙仍然都可以跳到就可以了（这是因为青蛙到达T及其以后的位置跳法只跟这T个位置有关，现在虽然距离减小了，但是青蛙的选择并没有减少，所以是等价的）。又由于1ST10，将间距大于100的点移近至间距100是完全合理的，从而桥的总长度就缩小至I00 x100=10000以内，最长运算次数也只有I0000 x100，利用动态规划完全可以在规定的时间和空间内实现。6、作为一个完整的程序，因为给出条件中石子位置并未排好序，由于最多100个位置