算法_ch8_培训资料.pptx

第八章 动态规划动态规划(dynamic rogramming)是运筹学的一个分支，20世纪50年代初美国数学家是求解决策过程最优化的数学方法。R.E.Bellman等人在研究多阶段决策过程的优化问题时，提出了著名的最优化原理，把多阶段过程转化为一系列单阶段问题，利用各阶段之间的关系，逐个求解，创立了解决这类过程优化问题的新方法——动态规划。在经济管理、生产调度、工程技术和动态规划问世以来，例如最短路线、库存管理、最优控制等方面得到了广泛的应用，资源分配、设备更新、排序、装载等问题。虽然动态规划用动态规划方法比用其它方法求解更为方便。主要用于求解以时间划分阶段的动态过程的优化问题，但是一些与时间无关的静态规划（如线性规划、非线性规划），只要人为地把它视为多阶段决策过程，也可以用动态规划方法引进时间因素，方便地求解。动态规划不仅是应用数学中用来解决某类最优问题的重要工具，还在计算机领域被当作一种通用的算法设计技术来使用。而且动态规划思想：原始问题（规模为n）子问题1（规模为n/b）子问题a（规模为n/b）子问题2（规模为n/b）......子子问题2子子问题c子子问题i子子问题1...子问题2的解子问题1的解......子问题a的解原始问题的解动态规划思想：在动态规划中，分解得到的各个子问题往往不是相互独立的。在求解过程中，将已解决的子问题的解进行保存，在需要时可以这样就避免了大量的无意义的重复计算，轻松找出。从而降低算法的时间复杂性。如何对已解决的子问题的解进行保存呢？通常采用表的形式，即在实际求解过程中，一旦某个子问题被计算过，不管该问题以后需要的时候就从表中是否用得到，都将其计算结果填入该表，找出该子问题的解。但它们具有具体的动态规划算法多种多样，相同的填表格式。动态规划基本概念：阶段：将所给问题按照时间或空间分解成若干互相联系的阶段，以便按次序去求解每一阶段的解.状态：每个阶段都有许多状态，当前阶段中状态的解必定是由前面阶段状态中的状态“变化”而来的，这种变化叫做状态转移.决策：对于状态转移的过程，我们有很多种可行的选择，这些选择就叫做决策.我们要根据问题选取最优决策.边界条件：有些状态的解无需通过前面阶段上的状态便可得到，称这些状态的解为边界条件.状态转移方程：当前阶段的状态往往是上一阶段状态及其决策的结果.它们之间的关系构成的方程称为状态转移方程.动态规划基本要素：（适用条件）最优化原理（最优子结构性质） 最优化原理是指：对于当前状态的子问题最优，就能保证当前状态的解最优.并且我们做出的决策最优，一个最优化策略的子策略总是最优的。简而言之，一个问题满足最优化原理又称其具有最优子结构性质。无后效性对于某个给定的阶段将各阶段按照一定的次序排列好之后，无法直接影响它未来的决策，它以前各阶段的状态状态，而只能通过当前的这个状态。简单的说，就是“未来与过去无关”。换句话说，每个状态都是过去历史的一个完整总结。又称为无后向性。这就是无后效性，子问题的重叠性 递归算法求解问题时，每次产生的子问题并不总是新问题，有些子问题出现多次，这种性质称为子问题的重叠性质。在应用动态规划时，只需在第一次对于重复出现的子问题，便于并把已解决的各子问题的解储存在表中，遇到时就加以解决，以后遇到时直接引用，而不必重新求解，可大大提高解题的效率。改进成了动态规划将原来具有指数级时间复杂度的有哪些信誉好的足球投注网站算法这是其中的关键在于解决冗余，具有多项式时间复杂度的算法。动态规划实质上是一种以空间换时间动态规划算法的根本目的。的技术。动态规划的解题步骤：（1）分析最优解的性质，刻画最优解的结构特征——考察是否适合采用动态规划法；（2）递归定义最优值（即建立递归式或状态转移方程）；（3）以自底向上的方式计算出最优值，并记录相关信息；（4）根据计算最优值时得到的信息，构造出最优解.§8.1 计算二项式系数§8.2 Warshall算法和Floyd算法一、Warshall算法在离散数学中，我们学习过一个关系的传递闭包的概念.关系可以用有向图表示，因此，关系的传递闭包又称为有向图的传递闭包.?设G为一个有向图，定义：G的顶点集合为有向图G的传递闭包定义为一个n阶布尔矩阵???1,其中否则.0，有向图G的传递闭包实际上就是G的可达矩阵。注：??有向图G:例：???G的邻接矩阵??G的传递闭包?比如进行图的深度优先查找或生成图的传递闭包的方法很多.广度优先查找，都可以求得传递闭包.但这两种遍历方法可能其效率较低.要对某些顶点遍历多次，S. Warshall 找到了一个好的方法生成n个顶点有向图的传递闭包.他的方法是通过构造一系列布尔矩阵：???????中间的每一个矩阵都提供了有向路径的特定信息.具体来说，????当且仅当??S. Warshall 找到了一个好的方法生成n个顶