动态规划法选编.ppt

第6章 动态规划法;学习要点: 理解动态规划的思想 掌握动态规划算法的基本要素 掌握设计动态规划算法的步骤 通过应用范例学习动态规划算法设计策略;动态规划是运筹学的一个分支，它是解决多阶段决策过程最优化问题的一种方法。1951年，美国数学家贝尔曼（R.Bellman）提出了解决这类问题的“最优化原则”，1957年发表了他的名著《动态规划》，该书是动态规划方面的第一本著作。 多阶段决策问题： 可以分为若干个相互联系的阶段，每个阶段都要做出一个决策，这个决策即决定了本阶段的效益，也决定了下一阶段的初始状态。 当每一个阶段的决策确定后，就得到一个决策序列，称为策略。;动态规划主要用于求解以时间划分阶段的动态过程的优化问题，但是一些与时间无关的静态规划（如线性规划、非线性规划），可以人为地引进时间因素，把它视为多阶段决策过程，也可以用动态规划方法方便地求解。 动态规划是考察问题的一种途径，或是求解某类问题的一种方法。 动态规划问世以来，在经济管理、生产调度、工程技术和最优控制等方面得到了广泛的应用。例如最短路线、库存管理、资源分配、设备更新、排序、装载等问题，用动态规划方法比其它方法求解更为方便。;6.1.1 多阶段决策过程;例如：在0/1背包问题中，物品i或者被装入背包，或者不被装入背包，设xi表示物品i装入背包的情况，则 xi=0时，表示物品i没有被装入背包， xi=1时，表示物品i被装入背包。 根据问题的要求，有如下约束条件和目标函数： ;6.1.2 最优化问题;如果用向量X=( x1, x2, …, xn)表示S中所选取的货币，则 (式6.2) 则，POS机支付的现金必须满足 (式6.3) 并且 (式6.4);6.1.3 最优性原理;具有n个输入的最优化问题，其求解过程划分为若干个阶段，每一阶段的决策仅依赖于前一阶段的状态，由决策所采取的动作使状态发生转移，成为下一阶段决策的依据。 一个决策序列在不断变化的状态中产生，这个决策序列产生的过程称为多阶段决策过程。;最优性原理：无论决策过程的初始状态和初始决策如何，其余的决策都必须相对于初始决策所产生的当前状态，构成一个最优决策序列。;6.1.4 算法总体思想 与分治法类似，动态规划算法的基本思想也是将待求解问题分解成若干个子问题，但是经分解得到的子问题往往不是互相独立的。 保存已解决的子问题的答案，需要时再找出已求得的答案，就可以避免大量重复计算，从而得到多项式时间算法。;动态规划算法适用于解最优化问题。步骤： 找出最优解的性质，并刻划其结构特征。(划分子问题) 最优子结构性质：问题的最优解包含其子问题的最优解。 递归地定义最优值。(确定动态规划函数) 以自底向上的方式计算出最优值。 根据计算最优值时得到的信息，构造最优解。;例6-1：数塔问题。 【问题描述】从数塔的顶层出发，在每一个结点可以选择向左走或向右走，一直走到最底层，要求找出一条路径，使得路径上的数值和最大。;分析：;求解初始子问题：底层的每个数字可以看作1层数塔，则最大数值和就是其自身； 再求解下一阶段的子问题：第4层的决策是在底层决策的基础上进行求解，可以看作4个2层数塔，对每个数塔进行求解； 再求解下一阶段的子问题：第3层的决策是在第4层决策的基础上进行求解，可以看作3个2层的数塔，对每个数塔进行求解； 以此类推，直到最后一个阶段：第1层的决策结果就是数塔问题的整体最优解。;算法描述： 输入：二维数组d[n][n] 输出：数塔的最大数值和及其路径 1. 初始化数组maxAdd的最后一行为数塔的底层数据： for (j = 0; j n; j++) maxAdd[n-1][j] = d[n-1][j]; 2. 从第n-1层开始直到第 1 层对下三角元素maxAdd[i][j]执行下述操作： 2.1 maxAdd[i][j] = d[i][j] + max{maxAdd[i+1][j], maxAdd[i+1][j+1]}； 2.2 如果选择下标j的元素，则path[i][j] = j；否则path[i][j] = j+1； 3. 输出最大数值和maxAdd[0][0]； 4. 根据path数组确定每一层决策的列下标, 输出路径信息;;6.1.5 矩阵连乘问题 问题描述： 给定n个矩阵 ，其中 与 是可乘的，