《算法分析与设计 第5章》由会员分享，可在线阅读，更多相关《算法分析与设计 第5章（38页珍藏版）》请在金锄头文库上搜索。
1、算法设计方法吴哲辉 崔焕庆 马炳先 吴振寰 编 著机械工业出版社1第5章 动态规划算法多段图问题矩阵连 乘问题0-1背包问题旅行售货商问题最长公共子序列问题流水作业调 度问题资源分配问题动态规 划小结2第5章 动态规划算法n动态规 划（Dynamic Programming）是运筹学 的一个分支，是求解决策过程最优化的数学方法 。20世纪50年代初美国数学家R. E. Bellman等 人在研究多阶段决策过程（Multistep Decision Process）的优化问题时 ，提出了著名的最优化 原理（Principle of Optimality），将多阶段决策 过程转化为一系列的单阶段决
2、策问题，创立了 解决这类过 程优化问题的新方法动态规 划 。 3第5章 动态规划算法n最优化原理是指一个最优化策略具有这样的性 质：不论过去的状态和决策如何，余下的决策 必须相对于前一决策所产生的状态构成最优决 策序列，也就是说，一个最优化策略的子策略总 是最优的，问题的最优解可以通过其子问题的 最优解构成。一个问题若满足最优化原理又称 其具有最优子结构性质。 4第5章 动态规划算法n根据动态规 划的思想方法设计的算法称为动态 规划算法。动态规 划算法常用于求解这样一类 问题：问题的解可以表示成一个解向量（ x1,x2,x3,xn），算法分为n步进行，每一步确 定解向量中一个分量的取值。5第5
3、章 动态规划算法n动态规 划算法的基本思想是：每一步都列出各种 可能的局部解，然后通过计算，舍去那些不满足 约束条件的局部解和那些已经肯定不可能发展成 为全局最优解的局部解。在此基础上，对存留 的局部解考察下一步（下一个分量）的取值。65.1 多段图问题n给定加权有向图G=(V,E,W),|V|=n，若G的顶点划分为k（ k1）个不相交集合Vi（00; i-) md(i)=;for (顶点i的所有邻接顶点j)if( md(i)c(i,j)+md(j)md(i)=c(i,j)+md(j); 105.1 多段图问题n4. 构造最优解。容易发现，在算法5.1计算最短距离的过程中已 经蕴含了最短路径的
4、结构信息，设顶点j是使取 最小值的顶点i的邻接顶点，则顶点j是顶点i到t 的最短路径上的前方顶点，此时只需要将顶点j 的编号记录下来，最后就可以逐步构造得到s到t 的最短路径。 算法5.2。115.2 矩阵连乘问题n矩阵连乘积问题 是指：给定n个矩阵A1An，其 中Ai与Ai+1是可乘的，矩阵的维数Ai为pi-1*pi，要 求确定一种矩阵连乘的顺序，使得计算矩阵连 乘积需要的计算量为最小。n完全加括号的矩阵连乘积可递归地定义为： (1) 单个矩阵是完全加括号的； (2) 若矩阵连乘积A是完全加括号的，则A可表示为 两个完全加括号的矩阵连乘积B、C的乘积并加 括号，即A=(BC)。 125.2
5、矩阵连乘问题n每一种完全加括号方式对应一种矩阵连乘积的 计算次序，矩阵连乘积问题 即对于给定的n个矩 阵，确定一种完全加括号方式，使得依此次序计 算矩阵连乘积所需要的数乘次数最少，称这个 计算次序为最优计算次序。 135.2 矩阵连乘问题n1. 最优子结构性质。将矩阵连乘积简记为 Ai:j。假设已经得到计算 的一个最优次序（最优解），该计算次序在Ak 和Ak+1之间将矩阵链断开。照此，我们要先计算 Ai:k和Ak+1:j，然后，将所得的结果矩阵相乘 得到Ai:j 。显然，计算A1:n的一个最优次序中，计算 A1:k和Ak+1:n的次序和计算的次序也是最优 的。因此，矩阵连乘积问题满 足最优子结
6、构性 质。145.2 矩阵连乘问题n2. 建立递归关系。设计算的最少数乘次数为mij，则问题 的最优 值为m1n。递归定义为：155.2 矩阵连乘问题n3. 计算最优值。 算法5.4 矩阵连 乘问题 的直接递归 算法 输入：矩阵连 乘的第一个和最后一个矩阵的编号i和j，P和m是全局变 量； 输出：最优计 算次序的计算次数。 int MatrixChain(int i, int j) if (i = j) return (0);= MatrixChain(i,i) + MatrixChain(i+1,j) + Pi-1*Pi*Pj;for(k=i+1; k t) = t;return (); 1
7、65.2 矩阵连乘问题n4. 构造最优解。 算法5.6 构造矩阵连乘问题的最优解 输入: i、j和sij； 输出:的最优计算次序。 void DPMatrixChain(int i, int j, int s)if (i != j) DPMatrixChain(i,sij, s);DPMatrixChain(sij+1, j, s);输出在处断开为Ai:sij和A1+sij:j; 175.3 0-1背包问题n0-1背包问题：给定n种物品和一个背包，物品i 的重量是，价值为，背包容量为c，问如何选择 装入背包的物品，使得装入背包的物品的总价值 最大。在装入背包时，每种物品i只有两种选择 ，全部装
8、入或者不装入。 185.3 0-1背包问题n1. 最优子结构性质。0-1背包问题的解是一个n维0-1向量，不妨设 (y1,y2,yn)是0-1背包问题的一个最优解，则部 分解(y2,yn)对应为 下面子问题的一个最优解 ：求维向量(x2,xn) ，使得并且满足195.3 0-1背包问题n2. 建立递归关系。0-1背包问题的求解需要逐步确定解向量(x1,x2, xn)中的取值。假设按照的次序来确定的值： (1) 如果x1=0，问题转变为 相对于其余n-1个物品， 背包容量仍为c的0-1背包问题； (2) 如果x1yn，zkyn，zkyn，则Z是X和Yn-1的最长公共子 序列。295.5 最长公共
9、子序列问题n2. 建立递归关系。 设Lij为序列和的最长公共子序列的长度， 305.5 最长公共子序列问题n3. 计算最优值。算法5.11n4. 构造最长公共子序列。算法5.12315.6 流水作业调度问题n流水作业调度问题一般指如下问题：n个作业要 在由m台机器组成的流水线上进行加工。每个作 业i可分解为m个任务，其中作业i的第j个任务要 求必须在机器j上进行加工，作业i的m个任务必 须顺序加工完成，即必须在完成之后才可以开始 加工，并且一台机器在任何时刻只能加工一个任 务。设任务在机器j上加工完成需要的时间为 Tij ，要求为n个作业安排一种加工顺序，使得从第 一个作业开始加工，直到最后一
10、个作业加工完成 ，所需要的时间最少，该加工顺序称为最优作 业调度，这里我们假设各个作业加工的优先级 都是相同的。 325.6 流水作业调度问题n已经证明，当m=3的时候，最优作业调度问题 是一个NP难的问题，而当m=2时，可以找到求 解该问题 的多项式时间算法。n显然，最优调度问题满 足最优子结构性质，即 若在一个最优作业调度中去掉前面的作业，剩 下的作业调度仍然是相应子问题的一个最优调 度。335.6 流水作业调度问题nJohnson法则： (1) 当 时，应将作业k安排在最前 面，作为最优调度的第一个执行的作业； (2) 当 时，应将作业k安排在最后 面，作为最优调度的最后一个执行的作业。
11、n算法5.13 345.7 资源分配问题n设有m份资源和n个工程，对每个工程投入不同数量的 资源获得的利润对应为 每个工程的利润函数Pi(xi)，表 示将xi份资源分配给第i个工程可获得的利润，那么， 将m份资源分配给n个工程可获得的利润总和为其中 355.7 资源分配问题n1. 最优子结构性质。设已经得到一个问题的最 优解X=(x1,x2,xn)，则部分解(x1,x2,xn-1)是 将(m-xn)份资源分配给前n-1个工程的子问题的 一个最优解。n2. 建立递归关系。n计算最优值。 n构造最优解。365.8 动态规划小结n利用动态规 划算法求解问题的过程是一个多阶段最优 决策的过程，一般可分
12、为如下四个求解步骤。 (1) 分析问题最优解的结构，并刻画其结构特征，证明其 满足最优子结构性质。通过对问题 的分析，将问题最 优解的求解分为若干个阶段，各个阶段之间应具有明 确的先后顺序关系； (2) 建立最优值的递归关系，问题的最优值对应 的递归 关系是各阶段决策的依据； (3) 计算最优值。根据最优值对应 的递归关系，按照自 底向上的顺序或自顶向下的方法递归计 算问题的最优 值； (4) 依据最优值求解过程中记录下来的最优解的信息，构 造问题的一个最优解。375.8 动态规划小结n动态规 划算法通常为自底向上的迭代形式，对每个不 同的子问题仅计 算一次，从而避免不必要的重复计算 。但有时也可以采用自上而下的计算顺序，这就是备 忘录方法。备忘录方法用表格将已经求解的子问题的 答案作为一个记录项 保存下来，当下次需要使用该子 问题的结果时，只需要通过查表就可以直接应用，而 不需要重新计算，同样避免了同一子问题的重复求解 。n算法5.1538
