ACM课程论文――详解动态规划

DynamicProgramming1暨南大学本科生课程论文论文题目：动态规划算法的应用学院：珠海学院学系：计算机科学系专业：计算机科学与技术课程名称：ACM学生姓名：赵莎学号：2007052391指导教师：陈双平2009年6月10日DynamicProgramming2动态规划算法——试析动态规划算法在ACM中的应用[摘要]通过实例，分析了动态规划算法在ACM中的应用。[关键词]ACM;动态规划算法;DPDynamicprogrammingalgorithm——AnalysisthedynamicprogrammingalgorithmintheapplicationofACM[Abstract]TheapplicationofDynamicprogrammingalgorithmhasbeenstudied[Keywords]ACM;Dynamicprogrammingalgorithm;DPDynamicProgramming31.绪论1.1综述[1]动态规划(dynamicprogramming)是运筹学的一个分支，是求解决策过程(decisionprocess)最优化的数学方法。20世纪50年代初美国数学家R.E.Bellman等人在研究多阶段决策过程(multistepdecisionprocess)的优化问题时，提出了著名的最优化原理(principleofoptimality)，把多阶段过程转化为一系列单阶段问题，利用各阶段之间的关系，逐个求解，创立了解决这类过程优化问题的新方法——动态规划。1957年出版了他的名著DynamicProgramming，这是该领域的第一本著作。动态规划问世以来，在经济管理、生产调度、工程技术和最优控制等方面得到了广泛的应用。例如最短路线、库存管理、资源分配、设备更新、排序、装载等问题，用动态规划方法比用其它方法求解更为方便。虽然动态规划主要用于求解以时间划分阶段的动态过程的优化问题，但是一些与时间无关的静态规划(如线性规划、非线性规划)，只要人为地引进时间因素，把它视为多阶段决策过程，也可以用动态规划方法方便地求解。动态规划程序设计是对解最优化问题的一种途径、一种方法，而不是一种特殊算法。不象前面所述的那些搜索或数值计算那样，具有一个标准的数学表达式和明确清晰的解题方法。动态规划程序设计往往是针对一种最优化问题，由于各种问题的性质不同，确定最优解的条件也互不相同，因而动态规划的设计方法对不同的问题，有各具特色的解题方法，而不存在一种万能的动态规划算法，可以解决各类最优化问题。因此读者在学习时，除了要对基本概念和方法正确理解外，必须具体问题具体分析处理，以丰富的想象力去建立模型，用创造性的技巧去求解。我们也可以通过对若干有代表性的问题的动态规划算法进行分析、讨论，逐渐学会并掌握这一设计方法。1.2研究框架本文将探讨动态规划算法在ACM解题中的应用，在文中首先介绍动态规划算法的相关知识，然后通过实际的例子演示动态规划算法在ACM中的应用。1.3术语说明Dynamicprogrammingalgorithm动态规划算法DynamicProgramming42动态规划算法介绍[1]2.1基本模型多阶段决策过程的最优化问题。在现实生活中，有一类活动的过程，由于它的特殊性，可将过程分成若干个互相联系的阶段，在它的每一阶段都需要作出决策，从而使整个过程达到最好的活动效果。当然，各个阶段决策的选取不是任意确定的，它依赖于当前面临的状态，又影响以后的发展，当各个阶段决策确定后，就组成一个决策序列，因而也就确定了整个过程的一条活动路线，如图所示：（看词条图）这种把一个问题看作是一个前后关联具有链状结构的多阶段过程就称为多阶段决策过程，这种问题就称为多阶段决策问题。2.2状态决策[1]2.2.1状态我们一般在动规的时候所用到的一些数组，也就是用来存储每个状态的最优值的。我们就从动态规划的要诀，也就是核心部分“状态”开始，来逐步了解动态规划。有时候当前状态确定后,以前状态就已经确定,则无需枚举.2.2.2决策当前状态通过决策,回到了以前状态.可见决策其实就是状态之间的桥梁。而以前状态也就决定了当前状态的情况。数字三角形的决策就是选择相邻的两个以前状态的最优值。2.3动态规划算法的应用[1]一、动态规划的概念近年来，涉及动态规划的各种竞赛题越来越多，每一年的NOI几乎都至少有一道题目需要用动态规划的方法来解决；而竞赛对选手运用动态规划知识的要求也越来越高，已经不再停留于简单的递推和建模上了。要了解动态规划的概念，首先要知道什么是多阶段决策问题。1.多阶段决策问题如果一类活动过程可以分为若干个互相联系的阶段，在每一个阶段都需作出决策(采取措施)，一个阶段的决策确定以后，常常影响到下一个阶段的决策，从而就完全确定了一个过程的活动路线，则称它为多阶段决策问题。DynamicProgramming5各个阶段的决策构成一个决策序列，称为一个策略。每一个阶段都有若干个决策可供选择，因而就有许多策略供我们选取，对应于一个策略可以确定活动的效果，这个效果可以用数量来确定。策略不同，效果也不同，多阶段决策问题，就是要在可以选择的那些策略中间，选取一个最优策略，使在预定的标准下达到最好的效果.2．动态规划问题中的术语阶段：把所给求解问题的过程恰当地分成若干个相互联系的阶段，以便于求解，过程不同，阶段数就可能不同．描述阶段的变量称为阶段变量。在多数情况下，阶段变量是离散的，用k表示。此外，也有阶段变量是连续的情形。如果过程可以在任何时刻作出决策，且在任意两个不同的时刻之间允许有无穷多个决策时，阶段变量就是连续的。状态：状态表示每个阶段开始面临的自然状况或客观条件，它不以人们的主观意志为转移，也称为不可控因素。在上面的例子中状态就是某阶段的出发位置，它既是该阶段某路的起点，同时又是前一阶段某支路的终点。过程的状态通常可以用一个或一组数来描述，称为状态变量。一般，状态是离散的，但有时为了方便也将状态取成连续的。当然，在现实生活中，由于变量形式的限制，所有的状态都是离散的，但从分析的观点，有时将状态作为连续的处理将会有很大的好处。此外，状态可以有多个分量(多维情形)，因而用向量来代表；而且在每个阶段的状态维数可以不同。当过程按所有可能不同的方式发展时，过程各段的状态变量将在某一确定的范围内取值。状态变量取值的集合称为状态集合。无后效性：我们要求状态具有下面的性质：如果给定某一阶段的状态，则在这一阶段以后过程的发展不受这阶段以前各段状态的影响，所有各阶段都确定时，整个过程也就确定了。换句话说，过程的每一次实现可以用一个状态序列表示，在前面的例子中每阶段的状态是该线路的始点，确定了这些点的序列，整个线路也就完全确定。从某一阶段以后的线路开始，当这段的始点给定时，不受以前线路（所通过的点）的影响。状态的这个性质意味着过程的历史只能通过当前的状态去影响它的未来的发展，这个性质称为无后效性。决策：一个阶段的状态给定以后，从该状态演变到下一阶段某个状态的一种选择（行动）称为决策。在最优控制中，也称为控制。在许多间题中，决策可以自然而然地表示为一个数或一组数。不同的决策对应着不同的数值。描述决策的变量称决策变量，因状态满足无后效性，故在每个阶段选择决策时只需考虑当前的状态而无须考虑过程的历史。决策变量的范围称为允许决策集合。DynamicProgramming6策略：由每个阶段的决策组成的序列称为策略。对于每一个实际的多阶段决策过程，可供选取的策略有一定的范围限制，这个范围称为允许策略集合。允许策略集合中达到最优效果的策略称为最优策略。给定k阶段状态变量x(k)的值后，如果这一阶段的决策变量一经确定，第k+1阶段的状态变量x(k+1)也就完全确定，即x(k+1)的值随x(k)和第k阶段的决策u(k)的值变化而变化，那么可以把这一关系看成(x(k)，u(k))与x(k+1)确定的对应关系，用x(k+1)=Tk(x(k),u(k))表示。这是从k阶段到k+1阶段的状态转移规律，称为状态转移方程。最优性原理:作为整个过程的最优策略，它满足：相对前面决策所形成的状态而言，余下的子策略必然构成“最优子策略”。2.4动态规划算法的问题求解模式动态规划算法所处理的问题是一个多阶段决策问题,一般由初始状态开始,通过对中间阶段决策的选择,达到结束状态.这些决策形成了一个决策序列,同时确定了完成整个过程的一条活动路线(通常是求最优的活动路线)。动态规划的设计一般都有着固定的模式，一般要经历以下几个步骤：又可以系统的解释为以下具体的步骤：（1）找出最优解的性质，并刻画其结构特征。（2）递归地定义最优值。（3）以自底向上的方式计算出最优值。（4）根据计算最优值时得到的信息，构造一个最优解。其中（1）－（3）步是动态规划算法的基本步骤。在只需要求出最优值的情形，步骤（4）可以省去。若需要求出问题的一个最优解，则必须执行步骤（4）。此时，在步骤（3）中计算最优值时，通常需记录更多的信息，以便在步骤（4）中，根据所记录的信息，快速构造出一个最优解。2.4动态规划问题的基本特征动态规划算法的有效性依赖于问题本身所具有的两个重要性质：1、最优子结构：当问题的最优解包含了其子问题的最优解时，称该问题具有最优子结构性质。2、重叠子问题：在用递归算法自顶向下解问题时，每次产生的子问题并不总是新问题，有些子问题被反复计算多次。动态规划算法正是利用了这种子问题的重叠性质，对每一个子问题只解一次，而后将其解保存在一个表格中，在以后尽可能多地利用这些子问题的解。当再次需要计算已经计算过的子问题时，只是在表格中简单的查看一下结果，从而获得较高的解题效率。2.4动态规划的基本思想如果各个子问题不是独立的，不同的子问题的个数只是多项式量级，如果我DynamicProgramming7们能够保存已经解决的子问题的答案，而在需要的时候再找出已求得的答案，这样就可以避免大量的重复计算。由此而来的基本思路是，用一个表记录所有已解决的子问题的答案，不管该问题以后是否被用到，只要它被计算过，就将其结果填入表中。2.5应用动态规划的算法[2]1)许多字符串操作算法如最长公共子列、最长递增子列、最长公共字串；2)将动态规划用于图的树分解，可以有效解决有界树宽图的生成树等许多与图相关的算法问题；3)决定是否及如何可以通过某一特定上下文无关文法产生给定字符串的Cocke-Younger-Kasami(CYK)算法；4)计算机国际象棋中转换表和驳斥表的使用；5)Viterbi算法（用于隐式马尔可夫模型）；6)Earley算法（一类图表分析器）；7)Needleman-Wunsch及其他生物信息学中使用的算法，包括序列比对、结构比对、RNA结构预测；8)Levenshtein距离（编辑距离）；9)弗洛伊德最短路径算法；10)连锁矩阵乘法次序优化；11)子集求和、背包问题和分治问题的伪多项式时间算法；12)计算两个时间序列全局距离的动态时间规整算法；13)关系型数据库的查询优化的Selinger（又名SystemR）算法；14)评价B样条曲线的DeBoor算法；15)用于解决板球运动中断问题的Duckworth-Lewis方法；16)价值迭代法求解马尔可夫决策过程；17)一些图形图像边缘以下的选择方法，如“磁铁”选择工具在Photoshop；18)间隔调度；19)自动换行；20)巡回旅行商问题（又称邮差问题或货担郎问题）；21)分段最小二乘法；22)音乐信息检索跟踪。DynamicProgramming83解题实例3.1解题一原题可参见以下网址：=2663DescriptionInhowmanywayscanyoutilea3xnrectanglewith2x1dominoes?Hereisasampletilingofa3x12rectangle.InputInputconsistsofseveraltestcase