（计算机应用技术专业论文）动态规划算法应用及其在时间效率上的优化.pdf

硕士论文动态规划算法应用及其在时间效率上的优化 摘要 算法设计是软件设计的灵魂内容，动态规划作为相对成熟的算法设计技术，不断 地被运用到工农业生产、经济、军事、工程技术等很多方面，显示出其高效、实用的 性能和宽阔的应用前景。本文对动态规划所涉及的诸多方面进行了深入的研究，通过 大量的程序设计实例阐述了包括动态规划的理论基础、实际应用、优化方法在内的几 大方面的问题。具体包括： 一、从动态规划的本质入手，介绍了多阶段决策问题、阶段与状态、决策与策略、 最优化原理与无后效性、最优指标函数和规划方程等一些专有名词的定义；利用一些 常见的实例阐述了动态规划在设计与实现时的多样性、模式性和技巧性等特点；通过 与一些常见算法的比较，讲解了动态规划与这些算法的区别和联系，突出了使用动态 规划时的最优化、高效率和高消费等特性。 二、从三个具体问题的解决过程中可以看出，动态规划是必不可少的有力工具。 通过问题描述、样例分析、算法设计、问题实现、测试结果等几个步骤详细讨论了动 态规划在应用中的实现过程和思考方法，体现出在应用中相应的实践指导意义。 三、鉴于动态规划在简单设计后还存在很大的时间冗余，从构成其时间复杂度的 三个方面：状态总数、每个状态转移的状态数、每次状态转移的时间进行优化，使得 动态规划在时间效率上得到了进一步的提升，以期面对并解决更大数据规模的问题。 不仅给出了优化的理论依据和具体方法，而且还给出了五个引用实例在优化前后的实 验运行对比结果。 最后，总结全文，分析了动态规划的应用和优化在面对不同问题时需要进一步完 善的地方，并指出了今后工作的研究方向。 关键词：动态规划，状态转移，时间复杂度，优化 a b s 仃a c t 硕士论文 a b s t r a c t t h ed e s i g no ft h ea l g o r i t h mi st h em a i nc o n t e n to fs o f t w a r ed e s i g n a sam a t u r e t e c h n i q u eo fa l g o r i t h md e s i g n ，d y n a m i cp r o g r a m m i n g i s w i d e l yu s e d i n i n d u s t r y , a g r i c u l t u r e ，e c o n o m y , m i l i t a r y , e n g i n e e r i n ga n d s o m eo t h e rf i e l d s ，w h i c hi n d i c a t e st h a ti ti s e f f i c i e n ta n dp r a c t i c a la n di th a sab r i g h tf u t u r e t h ed i s s e r t a t i o nd e a l sw i t l lm a n ya s p e c t s o fd y n a m i cp r o g r a m m i n g b yu s i n gm a n ye x a m p l e so fp r o g r a m m i n g ，i tg i v e sad e t a i l e d e x p l a n a t i o no fd y n a m i cp r o g r a m m i n g sr a t i o n a l e ，a p p l i c a t i o na n do p t i m i z a t i o nm e t h o d t h ed e t a i l s1 i s t e da sf o l l o w s ： f i r s t t h r o u g ht h ei n t r o d u c t i o no fi t se s s e n c e ，i ti n t r o d u c e st h ed e f i n i t i o no fs o m e t e r m ss u c ha sm u l t i s t a g ed e c i s i o n - m a k i n g ，s t a g ea n ds t a t e ，d e c i s i o n - m a k i n ga n ds t r a t e g y , o p t i m a l i t yp r i n c i p l e ，n o n a f t e r e f f e c t ，o p t i m a lt a r g e tf u n c t i o n , p r o g r a m m i n ge q u a t i o na n d s o o n b yu s i n gs o m ec o m m o ne x a m p l e s ，i tg i v e saf u l ld e s c r i p t i o no ft h ed i v e r s i t y , t h e p a t t e ma n dt h e a r t i f i c eo fd y n a m i cp r o g r a m m i n gi nd e s i g n i n ga n da p p l i c a t i o n b y c o m p a r i n gw i t hs o m ec o m m o na l g o r i t h m s ，i te x p l a i n st h e i rd i f f e r e n c e sa n dr e l a t i o n s h i p s a n de m p h a s i z e si t sc h a r a c t e r i s t i c s o p t i m i z e d ，e f f i c i e n t ，a n dc o n s u m p t i v e s e c o n d ，t h r o u g hs o l v i n gt h r e ep r o b l e m s ，w ec a nf i n dd y n a m i cp r o g r a m m i n gi sa n e c e s s i t y w i t ht h eh e l po f t h ef o l l o w i n gs t e p s ，l i k ep r o b l e md e s c r i b i n g ，s a m p l ea n a l y z i n g ， a l g o r i t h md e s i g n i n g ，p r o b l e ms o l v i n ga n dr e s u l tt e s t i n g ，i tg i v e sa f u l le x p l a n a t i o no ft h e i m p l e m e n t a t i o np r o c e s sa n dt h i n k i n gm e t h o d so fd y n a m i cp r o g r a m m i n gi na p p l i c a t i o n i t a l s os h o w st h a td y n a m i cp r o g r a m m i n gi sv e r yu s e f u la n dh e l p f u li na p p l i c a t i o n t h i r d ，t h e r ei sat i m er e d u n d a n c ya f t e rd y n a m i cp r o g r a m m i n gi su s e dt od e s i g n a l g o r i t h ms i m p l y , s oit r yt oo p t i m i z et h ed y n a m i cp r o g r a m m i n gi nt h r e ea s p e c t so ft i m e c o m p l e x i t y - - - t o t a lq u a n t i t i e so fs t a t e ，s t a t eq u a n t i t i e so fe v e r ys t a t et r a n s i t i o na n dt i m eo f e v e r ys t a t et r a n s i t i o n ，w h i c hh e l p si ti m p r o v eal o ti nt i m ee f f i c i e n c ya n dm a k e s i tp o s s i b l e f o rt h en e w l y - d e s i g n e da l g o r i t h mt os o l v et h ep r o b l e mw i t hl a r g e - s i z e dd a t a n o to n l y d o e si tp r o v i d et h et h e o r e t i c a lb a s i sa n dm e t h o d so fo p t i m i z a t i o n ，b u ta l s oi tp r o v i d e st h e c o m p a r i s o nr e s u l t so ff i v ee x p e r i m e n t sb e f o r ei to p t i m i z e da n da f t e ri to p t i m i z e d i nc o n c l u s i o n ，t h ed i s s e r t a t i o nn o to n l ya n a l y z e st h ei m p r o v e m e n t so ft h ea p p l i c a t i o n a n do p t i m i z a t i o no fd y n a m i cp r o g r a m m i n gi ns o l v i n go t h e rp r o b l e m s ，b u ta l s op o i n t so u t t h er e s e a r c hd i r e c t i o no ft h ew o r ki nt h ef u t u r e k e y w o r d s ：d y n a m i cp r o g r a m m i n g ，s t a t et r a n s i t i o n ，t i m ec o m p l e x i t y ，o p t i m i z a t i o n n 声明尸明 本学位论文是我在导师的指导下取得的研究成果，尽我所知，在 本学位论文中；除了加以标注和致谢的部分外，不包含其他人已经发 表或公布过的研究成果，也不包含我为获得任何教育机构的学位或学 历而使用过的材料。与我一同工作的同事对本学位论文做出的贡献均 已在论文中作了明确的说明。 研究生签名：年月目 学位论文使用授权声明 南京理工大学有权保存本学位论文的电孚和纸质文档，可以借阅 或上网公布本学位论文的全部或部分内容，可以向有关部门或机构送 交并授权其保存、借阅或上网公布本学位论文的全部或部分内容。对 于保密论文，按保密的有关规定和程序处理。 研究生签名：年 月日 硕士论文 动态规划算法应用及其在时间效率上的优化 引言 动态规划( d y n a m i cp r o g r a m m i n g ) 是运筹学的一个分支，是求解决策过程( d e c i s i o n p r o c e s s ) 最优化的数学方法。2 0 世纪5 0 年代初美国数学家r e b e l l m a n 等人在研究多 阶段决策过程( m u l t i s t e pd e c i s i o np r o c e s s ) 的优化问题时，提出了著名的最优化原理 ( p d n c i p l eo f o p t i m a l i t y ) ，把多阶段过程转化为一系列单阶段问题，逐个求解，创立了 解决这类过程优化问题的新方法动态规划。1 9 5 7 年出版了他的名著d y n a m i c p r o g r a m m i n g ，这是该领域的第一本著作。 动态规划问世以来，在城市规划【2 】、经济管理【3 】【4 】【5 】、生产调度】【7 】、工程技术和 最优控制等方面得到了广泛的应用。例如神经网络【8 】【9 】【1 0 1 1 1 】【1 2 】【1 3 】、生物有机体d n a 的相似程度分析【1 4 】、最短路线【1 5 】【1 6 1 、库存管理【1 7 1 、资源分配【1 8 】【1 9 】、资产投资 2 0 1 2 、 证券交易阎、经营决策1 2 3 1 、企业生产物流控制【2 4 】、农业灌溉瞄1 1 2 6 、施工计划安排【2 7 】【2 引、 单一品种项目的生产批量问题【2 9 】、设备更新、最优化设计【3 0 1 3 1 】【3 2 1 1 3 3 1 1 3 4 】【3 5 】、学习方法 【3 6 1 、排序、装载等问题，用动态规划方法比用其它方法求解更为方便。动态规划主要 用于求解以时间划分阶段的动态过程的优化问题，而且一些与时间无关的静态规划 【3 刀( 如线性规划、非线性规划) ，只要人为地引进时间因素，把它视为多阶段决策过程， 也可以用动态规划方法方便地求解。 在计算机算法设计方法中，动态规划技术是比较基本，但又比较抽象，难于理解 的一种。它建立在最优原则的基础上，采用动态规划方法，可以优雅而高效地解决许 多用贪心技术或分治技术无法解决的问题。因此，动态规划技术越来越成为解决许多 重要的应用问题的关键技术。例如，用动态规划解决o 1 背包问题、图像数据压缩、 矩阵连乘【3 8 】、不等式证明【3 9 1 、有向图最短路径【1 5 】【1 6 1 、无交叉子集、多目标跟踪【4 0 】、 元件折叠以及最长公共子序列【4 1 】【4 2 】【4 3 】等应用问题。另外，在语音识别领域，应用动 态规划技术的动态时间伸缩算法d t w 取得了很大成功，当词汇表较小以及各个词条 不易于混淆时，d t w 可以有效地解决孤立词识别时说话速度不均匀的难题，从而自 2 0 世纪6 0 年代末期掀起了语音识别研究的热潮。 动态规划技术是基本算法设计技术中较难掌握但也是极其重要的一种方法，它的 应用领域非常广泛，除了本文提到的一些问题之外，动态规划还用于解决字符串搜索 问题、手写字符识别问题、网络的无交叉布线、电路元件折叠和旅行商问题等各种实 际应用问题，因此，掌握动态规划技术对提高计算机算法设计和分析水平及解决实际 计算问题具有至关重要的作用和意义。 近年来，除了基本的动态规划设计方法之外，随机动态规划【删、基于p i p e l i n e 的 一类动态规划并行算法【4 5 1 、离散型动态规划 4 6 1 、动态规划顺序算法【4 7 】f 4 8 1 、多目标动 引言 硕士论文 2 态规划时段轮换并行算法 4 9 1 、灰色动态规划【5 0 1 、多约束动态规划【5 l 】、马尔可夫动态 规划【5 2 1 、线性动态规划【5 3 】、模糊优选动态规划【5 4 1 1 5 5 1 、动态规划逆序算法【5 6 】、大型动 态规划的分解算法【5 7 】、动态规划的单增量搜索算法f 5 8 1 、多目标动态规划分层解法与 p a r e t o 最优解【”j 等很多方面都得到了长足的发展。 本文在撰写过程中参考了大量的文献资料，尽量使得行文能够充分展现动态规划 所涉及的诸多方面并进行深入讨论，通过大量的算法设计实例阐述包括动态规划的理 论基础、实际应用、优化改进在内的几大方面的问题。 硕士论文动态规划算法应用及其在时间效率上的优化 1 绪论 动态规划是算法设计的一种重要手段，在各行各业的程序设计中被应用得越来越 普遍。因此，如何更深入地了解动态规划，从而更为有效地运用算法设计的这个有力 武器，是一个值得深入研究的问题。 要掌握动态规划的应用技巧，就要了解它的各方面的特点。本章内容将从三个方 面进行简单阐述： 1 、动态规划的本质 2 、动态规划的设计与实现 3 、动态规划与一些算法的比较 首要的，是要深入洞悉动态规划的本质。 1 1 动态规划的本质 动态规划是在2 0 世纪5 0 年代初，为了解决一类多阶段决策问题【1 4 】【6 0 】【6 l 】【6 2 】【6 3 1 而 诞生的。那么，什么样的问题被称作多阶段决策问题呢? 1 1 1 多阶段决策问题 通过下面这个例子来说明。 【例一】多段图中的最短路径问题【1 5 】【1 6 】：在图i 1 中找出从a 1 到d l 的最短路径( 图 中的边上的数字表示该边上的权) 。 图1 1 多阶段决策问题 这个图有一个特点，就是可以将图中的点分为四类( 图1 1 中的a 、b 、c 、d ) ， 那么图中所有的边都处于相邻的两类点之间，并且都从前一类点指向后一类点。这样， 图中的边就被分成了三类( a 专b 、b - c 、c 专d ) 。这时需要从每一类中选出一条边 来，组成从a i 到d i 的一条路径，并且这条路径是所有这样的路径中的最短者。这 是多阶段决策问题。 i 绪论硕士论文 更精确的定义如下：多阶段决策过程，是指这样的一类特殊的活动过程，问题可 以按时间顺序分解成若干相互联系的阶段，在每一个阶段都要做出决策，全部过程的 决策是个决策序列。要使整个活动的总体效果达到最优的问题，称为多阶段决策问 题。 多阶段决策问题有两个要素：一个是阶段，一个是决策。 1 1 2 阶段与状态 阶段：将所给问题的过程，按时间或空间特征分解成若干相互联系的阶段，以便 按次序去求每阶段的解。常用字母k 表示阶段变量。 阶段是问题的属性【6 4 1 。多阶段决策问题中通常存在着若干个阶段，如例一中就有 a 、b 、c 、d 这四个阶段。在一般情况下，阶段是和时间有关的；但是在很多问题中， 阶段和时间是无关的。从阶段的定义中，可以看出阶段的两个特点：一是“相互联系”， 二是“次序”。 阶段之间是怎样相互联系的? 就是通过状态和状态转移。 状态：各阶段开始时的客观条件叫做状态。描述各阶段状态的变量称为状态变量， 常用s k 表示第k 阶段的状态变量，状态变量s k 的取值集合称为状态集合，用s k 表示。 状态是阶段的属性。每个阶段通常包含若干个状态，用以描述问题发展到这个阶 段时所处的一种客观情况。在例一中，行人从出发点a 1 走过两个阶段之后，可能出 现的情况有三种，即处于c l 、c 2 或c 3 点。那么第三个阶段就有三个状态s 3 = c 1 ，c 2 ，c 3 。 每个阶段的状态都是由以前阶段的状态以某种方式“变化”而来，这种“变化”称为 状态转移( 后有详细定义) 。例一中c 3 点可以从b l 点过来，也可以从b 2 点过来，从 阶段2 的b 】或b 2 状态走到阶段3 的c 3 状态就是状态转移。状态转移是导出状态的 途径，也是联系各阶段的途径。 应用动态规划的一个重要条件就是将各阶段按照一定的次序排列好之后，对于某 个给定的阶段状态，它以前各阶段的状态无法直接影响它未来的发展，而只能通过当 前的这个状态。换句话说，每个状态都是“过去历史的一个完整总结”。这就是无后效 性。对这个性质，下文还将会有解释。 1 1 3 决策和策略 上面的阶段与状态只是多阶段决策问题的一个方面的要素，下面是另一个方面的 要素决策1 6 引。 决策：当各段的状态取定以后，就可以做出不同的决定，从而确定下一阶段的状 态，这种决定称为决策。表示决策的变量，称为决策变量，常用u k ( s k ) 表示第k 阶段 当状态为s k 时的决策变量。在实际问题中，决策变量的取值往往限制在一定范围内， 此范围称为允许决策集合。常用d k ( s k ) 表示第k 阶段从状态s k 出发的允许决策集合。 4 硕士论文动态规划算法应用及其在时间效率上的优化 显然有u k ( s o e d k ( s k ) 。 ： 决策是问题的解的属性。决策的目的就是“确定下一阶段的状态”，还是回到例一， 从阶段2 的b 1 状态出发有三条路，也就是三个决策，分别导向阶段3 的c l 、c 2 、c 3 三个状态，即d 2 ( b 1 ) = c 1 ，c 2 ，c 3 。 定义状态转移：动态规划中本阶段的状态往往是上一阶段状态和上一阶段决策的 结果，由第k 段的状态s k 和本阶段的决策u k 确定第k + 1 段的状态s k + 1 的过程叫状态 转移。状态转移规律的形式化表示s k + l = t k ( s k ，u k ) ，称为状态转移方程。 状态转移是决策的目的，决策是状态转移的途径。 各段决策确定后，整个问题的决策序列就构成了一个策略，用 p l m = u 1 ( s o ，u 2 ( s 2 ) ，u n ( s 1 1 ) 表示。对每个实际问题，可供选择的策略有一定的范围， 称为允许策略集合，记作p l 使整个问题达到最有效果的策略就是最优策略。 运用动态规划的一个前提，即这个过程的最优策略应具有这样的性质：无论初始 状态及初始决策如何，对于先前决策所形成的状态而言，其以后的所有决策应构成最 优策略。这就是最优化原理【6 6 】【6 7 1 。简言之，就是c 最优策略的子策略也是最优策略”。 1 1 4 最优化原理与无后效性 这里，为什么把最优化原理定位在“运用动态规划的前提”? 这是因为，是否符合 最优化原理是一个问题是否符合动态规划的本质特征。对于不满足最优化原理的一个 多阶段决策问题，整体上的最优策略p l m 同任何一个阶段k 上的决策u k 或任何一组阶 段k 1 k 2 上的子策略p l 【l ，k 2 都不存在任何关系。如果要对这样的问题动态规划的话， 那从一开始所作的划分阶段等努力都将是徒劳的，换句话说，它并不符合动态规划的 本质特征。 而之所以把无后效性定位在“应用动态规划的条件”，是因为动态规划是按次序去 求每个阶段的解，如果一个问题有后效性，那么这样的次序便是不合理的。但是，还 可以通过重新划分阶段，重新选定状态，或者增加状态变量的个数等手段，来使该问 题满足无后效性这个条件。说到底，就是要确定一个“次序”。 在许多多阶段决策问题中，绝大部分都是能够满足最优化原理的，但它们往往会 在后效性这一点上来设置障碍。所以在算法设计的过程中，要特别关心“次序”。对于 有序的问题，就要考虑到动态规划；对于无序的问题，也要想方设法来使其有序。 1 1 5 最优指标函数和规划方程 最优指标函数：用于衡量所选定策略优劣的数量指标称为指标函数，最优指标函 数记为f k ( s o ，它表示从第k 段状态s k 采用最优策略p k n 到过程终止时的最佳效益值。 最优指标函数其实就是问题的解。在例一中，f i ( b 1 ) 就表示从b l 点到终点d l 点 的最短路径长度。求解的最终日标就是f l ( a 1 ) 。 5 l 绪论 硕士论文 最优指标函数的求法一般是一个从目标状态出发的递推公式，称为规划方程： 以( 靠) = o p tg + 1 亿( & ，材t ) ) ，“i ) 段e z 夏( 如) 其中s k 是第k 段的某个状态，u k 是从s k 出发的允许决策集合d k ( s k ) 中的一个决策， t k ( s k ，u k ) 是由s k 和u k 所导出的第k + l 段的某个状态s k + l ，g ( x ，u k ) 是定义在数值x 和决 策i l k 上的一个函数，而函数o p t 表示最优化，根据具体问题分别表为m a x ( 最大) 或 r a i n ( 最小) 。 z ( s 。) = 某个初始值，称为边界条件。 上例中的规划方程就是： 五( & ) = 加。出瘢条池。+ - ( u k 指向的点m ) + 边的长度) 边界条件为( q ) = 0 这里是一种从目标状态往回推的逆序求法，适用于目标状态确定的问题。在众多 相关问题中，也有很多有着确定的初始状态。当然，对于初始状态确定的问题，也可 以采用从初始状态出发往前推的顺序求法。 了解了动态规划的本质之后，下面来讨论一下动态规划在设计与实现时的三种特 性：多样性、模式性、技巧性。 1 2 动态规划的设计与实现 有了动态规划的基本概念后，在实际中对其设计与实现【6 8 1 6 9 时所体现的几种特 性也是值得关注并具有指导意义的。 1 2 1 动态规划的多样性 【例二】花店橱窗布置问题7 0 1 【问题描述】假设你想以最美观的方式布置花店的橱窗。现在你有f 束不同品种 的花束，同时你也有至少同样数量的花瓶被按顺序摆成一行。这些花瓶的位置固定于 架子上，并从1 至v 顺序编号，v 是花瓶的数目，从左至右排列，则最左边的是花 瓶1 ，最右边的是花瓶v 。花束可以移动，并且每束花用】至f 间的整数唯一标识。 标识花束的整数决定了花束在花瓶中的顺序，如果i r o w ) ( 这里的r o w 是地图竖直方向的行数) 可以看到，这个状态转移方程需要根据k 的取值分两种情况讨论，显得非常麻烦。 相应的，把它代入规划方程而付诸实现时，算法也很繁。因而在实现时，一般是不会 这么做的，而代之以下面方法： 将地图中的点规则地编号如图1 5 ，得到的规划方程如下： 9 i 绪论硕士论文 ，。l ，+ d i s t a n c e ( f 一1 ，n ( f ，j ) 【z i + d i s t a n c e “一姗) ( 这里d i s t a n c e 表示相邻两点间的边长) 这样做确实要比上面的方法简单多了，但是它已经破坏了动态规划的本来面目， 而不存在明确的阶段特征了。如果说这种方法是以地图中的行( a 、b 、c 、d ) 来划 分阶段的话，那么它的“状态转移”就不全是在两个阶段之间进行的了。 也许这没什么大不了的：，因为实践比理论更有说服力。但是，如果把问题扩展一 下：在地图中找出从左下角到右上角的两条路径，两条路径中的任何一条边都不能重 叠，并且要求两条路径的总长度最短。这时，再用这种“简单”的方法就很难实现了。 如果一定要套用这种方法的话，则最优指标函数就需要有四维的下标，并且难以 处理两条路径“不能重叠”的问题。 而回到原先“标准”的动态规划法，就会发现这个问题很好解决，只需要加一维状 态变量就可以实现了。即用s l 严，b k ) 分别表示两条路径走到阶段k 时所处的位置，相 应的，决策变量也增加一维；用u f ( x k ，y k ) 分别表示两条路径的行走方向。状态转移 时将两条路径分别考虑： ( 后，p w ) f 【以a k 一_ 。l ：= 6 a 。k 一- 1 1 + + y x 七k ( 七 ，。w ) 【6 a 。k 一_ l l ：= 6 a 。k + + ) ，x 七k 胂沪l 赫m i nm m 范戮禁搿a k = b k 1 0 硕士论文动态规划算法应用及其在时间效率上的优化 1 3 动态规划与一些算法的比较 动态规划作为诸多算法设计方法中的一种，必然和其他一些算法有着诸多联系。 从这些联系中，也可以看出动态规划的一些特点。 1 3 1 动态规划与分治 动态规划是减少重复计算的快速算法 在分治法中，为了解决一个大的问题，总是想方设法把它分成两个或多个更小的 问题；然后分别解决每个小问题；再把各小问题的解答组合起来，即可得到原问题的 解答；小问题通常与原问题本质相似，只是规模小些，一般都可以用递归的方法来解 决，如h a n o i 塔问题和快速排序都是应用这种方法的典型例子。然而常常有些问题难 以用分治法来求解，当把问题分解成若干个子问题，使之能够从这些子闯题的解得到 原问题的解时，子问题的数目太多，这样，如果把每个子问题再分解，必将得到更多 的子问题，以至于最后所设计算法需要耗费指数时间。往往在这类问题中子问题的数 目其实只有多项式多个，于是在上述算法中，一定有些子问题被重复计算了许多次。 如果能够保存已解决的子问题的答案，而在需要时简单查一下，这样就可以避免大量 的重复计算，从而得到多项式时间的算法。 为了实现上述方法，用一个数组来记录所有已解决的子问题的答案。无论子问题 以后是否被用到，只要它被计算过，就将其结果存入数组中，这就是动态规划1 7 s 】。动 态规划算法可以很明显地减少重复计算，以至于在实现的时候完全可以用递推的手段 来实现，但动态规划与递推也有很大的区别。 1 3 2 动态规划与递推 动态规划是最优化算法 由于动态规划的“名气”如此之大，以至于很多人甚至一些资料书上都往往把一种 与动态规划十分相似的算法，当作是动态规划。这种算法就是递推。实际上，这两种 算法还是很容易区分的。下面用一个例子来谈一下递推法和动态规划的关系。 【例四 m o d4 最优路径问题：在图1 6 中找出从第1 点到第4 点的一条路径，要 求路径长度m o d4 的余数最小。 图1 6 模4 最优路径问题 这个图结构是一个多段图，而且是一个特殊的多段图。虽然这个图的形式比一般 的多段图要简单，但是这个最优路径问题却不能用动态规划来做。因为一条从第l 点到第4 点的最优路径，在它走到第2 点、第3 点时，路径长度m o d4 的余数不一定 l l 1 绪论硕士论文 是最小，也就是说最优策略的子策略不一定最优这个问题不满足最优化原理。 但是可以把它转换一下，用递推法来解决。判断从第1 点到第k 点的长度m o d4 为s k 的路径是否存在，用墩( s k ) 来表示，则递推公式如下： 无( & ) = 边界条慨f ，( s 1 ) = 淼藩 ( 这里l e n k , i 表示从第k - 1 点到第k 点之间的第i 条边的长度，方括号表示“或( o r ) ” 运算) 最后的结果就是可以使f 4 ( s 4 ) 值为真的最小的s 4 值。 这个递推法的递推公式和动态规划的规划方程非常相似，在这里借用了动态规划 的符号也就是为了更清楚地显示这一点。其实它们的思想也是非常相像的，可以说是 递推法借用了动态规划的思想解决了动态规划不能解决的问题。 1 3 3 动态规划与搜索 动态规划是高效率、高消费算法 同样是解决最优化问题，有些闯题采用动态规划，而有些问题则需要用搜索。撇 开时间和空间效率的因素不谈，在解决最优化问题的算法中，搜索可以说是“万能” 的。所以如果动态规划可以解决的问题，搜索也一定可以解决。 把一个动态规划算法改写成搜索是非常方便的，状态转移方程、规划方程以及边 界条件都可以直接“移植”，所不同的只是求解顺序。动态规划是自底向上的递推求解， 而搜索则是自顶向下的递归求解( 这里指深度优先搜索，宽度优先搜索类似) 。 反过来，也可以把搜索算法改写成动态规划。状态空间搜索实际上是对图结构中 的点进行枚举，这种枚举是自顶向下的。如果把枚举的顺序反过来，变成自底向上， 那么就成了动态规划。( 当然这里有个条件，即图结构中的点是可排序的) 正因为动态规划和搜索有着求解顺序上的不同，这也造成了它们时间效率上的差 别。在搜索中，往往会出现如图1 7 的情况： 对于图1 7 ( a ) 这样几个状态构成的一个图结构，用搜索算法就会出现重复，如图 1 7 ( b ) 所示，状态c 2 被搜索了两次。在深度优先搜索中，这样的重复会引起以c 2 为 根整个的整个子搜索树的重复搜索；在宽度优先搜索中，虽然这样的重复可以立即被 排除，但是其时间代价也是不小的。而动态规划就没有这个问题，如图1 7 ( c ) 所示。 4 4 4 甜m m 唧 m m j 卫 。 押 珂 聆彪肠沱 一 一 一 r r r o 以 。六五以 硕士论文 动态规划算法应用及其在时间效率上的优化 ( a ) 图结构一( b ) 搜索算法实现( c ) 动态规划实现 图1 7 图结构及其实现实倒一 一般说来，动态规划算法在时间效率上的优势是搜索算法无法比拟的。( 当然对 于某些问题，根本不会出现状态的重复，这样搜索和动态规划的速度就没有差别了。) 而从理论上讲，任何拓扑有序( 现实中这个条件常常可以满足) 的图结构中的搜索算 法都可以改写成动态规划。但事实上，在很多情况下仍然不得不采用搜索算法。那么， 动态规划算法在实现上还有什么障碍吗? ( a ) 图结构二( b ) 搜索算法实现( c ) 动态规划实现 图1 8 图结构及其实现实例二 考虑图1 8 ( a ) 所示的图结构，其中存在两个从初始状态无法达到的状态。在搜索 算法中，这样的两个状态就不被考虑了，图1 8 ( b ) 所示。但是动态规划由于是自底向 上求解，所以就无法估计到这一点，因而遍历了全部的状态，如图1 8 ( c ) 所示。 一般说来，动态规划总要遍历所有的状态，而搜索可以排除一些无效状态。更重 要的是搜索还可以剪枝，可能剪去大量不必要的状态，因此在空间开销上往往比动态 规划要低很多。 如何协调好动态规划的高效率与高消费之间的矛盾呢? 有一种折衷的办法就是 记忆化算法。记忆化算法在求解的时候还是按着自顶向下的顺序，但是每求解一个状 态，就将它的解保存下来，以后再次遇到这个状态的时候，就不必重新求解了。这种 方法综合了搜索和动态规划两方面的优点，因而还是很有实用价值的。 1 4 本章小结 本章内容从动态规划的本质、设计与实现的多种特性以及与多种常见算法的比较 等多个方面谈了一些理论性较强的内容，这为后续应用章节内容打下了很好的基础， 1 3 l绪论 硕士论文 下面一章将详细谈动态规划算法在三个具体问题中的应用，并将给出详细的问题分析 过程、多种设计方法的比较、算法设计框图、多次数据测试记录。 1 4 硕士论文动态规划算法应用及其在时间效率上的优化 2 动态规划算法在三个具体问题中的应用 2 1 “过河”问题 2 1 1 问题描述 在河上有一座独木桥，一只青蛙想沿着独木桥从河的一侧跳到另一侧。在桥上有 一些石子，青蛙很讨厌踩在这些石子上。由于桥的长度和青蛙一次跳过的距离都是正 整数，我们可以把独木桥上青蛙可能到达的点看成数轴上的一串整点：o ，1 ， l ( 其中l 是桥的长度) 。坐标为0 的点表示桥的起点，坐标为l 的点表示桥的终点。 青蛙从桥的起点开始，不停的向终点方向跳跃。一次跳跃的距离是s 到t 之间的任 意正整数( 包括s ，t ) 。当青蛙跳到或跳过坐标为l 的点时，就算青蛙已经跳出了 独木桥。 事先给出独木桥的长度l ，青蛙跳跃的距离范围s ，t ，桥上石子的位置。你的 任务是确定青蛙要想过河，最少需要踩到的石子数。 输入文件： 输入文件r i v e r i n 的第一行有一个正整数l ( i _ l 1 0 9 ) ，表示独木桥的长度。第 二行有三个正整数s ，t ，m ，分别表示青蛙一次跳跃的最小距离，最大距离，及桥 上石子的个数，其中1 s s g 1 0 ，l m 1 0 0 。第三行有m 个不同的正整数分别表示这 m 个石子在数轴上的位置( 数据保证桥的起点和终点处没有石子) 。所有相邻的整 数之间用一个空格隔开。 输出文件： 输出文件r i v e r o u t 只包括一个整数，表示青蛙过河最少需要踩到的石子数。 样例输入： 1 0 235 23567 样例输出： 2 数据规模： 对于3 0 的数据，l s l o o o o ； 对于全部的数据，l _ 1 0 9 。 时限：2 秒。 2 动态规划算法在三个具体问题中的应用硕士论文 2 1 2 样例分析 桥长度l = 1 0 ，最短能跳s = 2 ，最长能跳t = 3 ，石子数m = 5 ，5 个石子所在位置 分别为2 、3 、5 、6 、7 。跳过桥最少要踩到的石子数是2 个，如图2 1 所示： 石石石石石 亏亏亏亏 仁二y 二q - 图2 1 “过河”问题样例分析