算法设计第六章动态规划稿.pptVIP

算法设计及其应用 第六章:动态规划算法 (国际大学生程序设计竞赛辅导教程） (国际大学生程序设计竞赛例题解（三）) 动态规划概述 运筹学(Operations Research)是系统工程最重要的理论基础之一, 运筹学所研究的问题可简单地归结为: “依照给定条件和目标, 从众多方案中选择最佳方案.” 而动态规划是运筹学的重要分支之一, 它是解决多阶段决策过程最优化的一种方法. 动态规划概述 动态规划简单的来说就是：采用分治的策略把求最优解问题分解为求若干个子问题的最优解，子问题也递归的分解为子问题的组合，通过递归递推等方法，把原问题最优解与局部子问题最优解联系起来，以求最后的解。这些局部子问题之间可能有重叠，就是某个子问题可能需要求解多次，因此需要将子问题及其解记录下来，这样对每个子问题只需求解一次，从而提高了效率。 动态规划概述 一般来说，寻找最优解的算法都具有指数时间的复杂度，因此算法的优化显得十分重要；但是有一类特殊的最优化问题，我们通常可以找到具有多项式时间的复杂度的算法，这种方法就是我们下面要介绍的动态规划。  动态规划的常用名词 (1) 状态(state) 对于一个问题，所有可能到达的情况（包括初始情况和目标情况）都称为这个问题的一个状态。 (2) 状态变量(sk) 对每个状态k关联一个状态变量sk，它的值表示状态k所对应的问题的当前解值。 (3) 决策(decision) 决策是一种选择，对于每一个状态而言，你都可以选择某一种路线或方法，从而到达下一个状态。 动态规划的常用名词 (4) 决策变量(dk) 在状态k下的决策变量dk的值表示对状态k当前所做出的决策。 (5) 策略 策略是一个决策的集合，在我们解决问题的时候，我们将一系列决策记录下来，就是一个策略，其中满足某些最优条件的策略称之为最优策略。 动态规划的常用名词 (6) 状态转移函数(t) 从一个状态到另一个状态，可以依据一定的规则来前进。我们用一个函数t来描述这样的规则，它将状态i和决策变量di映射到另一个状态j，记为t(i,di)=j。 (7) 状态转移方程(f) 状态转移方程f描述了状态变量之间的数学关系。一般来说，与最优化问题相应，状态转移方程表示si的值最优化的条件，或者说是状态i所对应问题的最优解值的计算公式，用代数式表示就是： si=f({(sj,dj)|i=t(j,dj)，对决策变量dj所有可行的取值}) 最优化原理 1951年美国数学家R. Bellman等人，根据一类多阶段问题的特点，把多阶段决策问题变换为一系列互相联系的单阶段问题，然后逐个加以解决。一些静态模型，只要人为地引进“时间”因素，分成时段，就可以转化成多阶段的动态模型，用动态规划方法去处理。 最优化原理 解决这类问题的“最优化原理”（Principle of optimality）： “一个过程的最优决策具有这样的性质：即无论其初始状态和初始决策如何，其今后诸策略对以第一个决策所形成的状态作为初始状态的过程而言，必须构成最优策略”。 简言之，一个最优策略的子策略，对于它的初态和终态而言也必是最优的。 最优化原理 这个“最优化原理”如果用数学化一点的语言来描述的话，就是：假设为了解决某一优化问题，需要依次作出n个决策D1，D2，…，Dn，如若这个决策序列是最优的，对于任何一个整数k，1kn，不论前面k个决策是怎样的，以后的最优决策只取决于由前面决策所确定的当前状态，即以后的决策Dk+1，Dk+2，…，Dn也是最优的。 最优化原理是动态规划的基础。任何一个问题，如果失去了这个最优化原理的支持，就不可能用动态规划方法计算。 何为动态规划 动态规划是运筹学的一个分支。与其说动态规划是一种算法，不如说是一种思维方法来得更贴切。因为动态规划没有固定的框架，即便是应用到同一道题上，也可以建立多种形式的求解算法。许多隐式图上的算法，例如求单源最短路径的Dijkstra算法、广度优先有哪些信誉好的足球投注网站算法，都渗透着动态规划的思想。还有许多数学问题，表面上看起来与动态规划风马牛不相及，但是其求解思想与动态规划是完全一致的。 动态规划适于解决何种问题 只适于解决一定条件的最优策略问题。 所谓“满足一定条件”主要指： (1) 状态必须满足最优化原理； (2) 状态必须满足无后效性。 所谓的无后效性是指：“过去的决策只能通过当前状态影响未来的发展，当前的状态是对以往决策的总结”。 动态规划适于解决何种问题 这个特征说明什么呢？它说明动态规划适于解决当前决策和过去状态无关的问题。状态，出现在策略的任何一个位置，它的地位都是相同的，都可以实施同样的决策。这就是无后效性的内涵。 采用动态规划解题的优点 动态规划的最大优势在于它具有极高的效率; 可获一系列解; 算法