算法分析与设计第5章.ppt

算法设计方法,吴哲辉 崔焕庆 马炳先 吴振寰 编著 机械工业出版社,2,第5章 动态规划算法,3,第5章 动态规划算法,动态规划（Dynamic Programming）是运筹学的一个分支，是求解决策过程最优化的数学方法。20世纪50年代初美国数学家R. E. Bellman等人在研究多阶段决策过程（Multistep Decision Process）的优化问题时，提出了著名的最优化原理（Principle of Optimality），将多阶段决策过程转化为一系列的单阶段决策问题，创立了解决这类过程优化问题的新方法动态规划。,4,第5章 动态规划算法,最优化原理是指一个最优化策略具有这样的性质：不论过去的状态和决策如何，余下的决策必须相对于前一决策所产生的状态构成最优决策序列，也就是说，一个最优化策略的子策略总是最优的，问题的最优解可以通过其子问题的最优解构成。一个问题若满足最优化原理又称其具有最优子结构性质。,5,第5章 动态规划算法,根据动态规划的思想方法设计的算法称为动态规划算法。动态规划算法常用于求解这样一类问题：问题的解可以表示成一个解向量（x1,x2,x3,xn），算法分为n步进行，每一步确定解向量中一个分量的取值。,6,第5章 动态规划算法,动态规划算法的基本思想是：每一步都列出各种可能的局部解，然后通过计算，舍去那些不满足约束条件的局部解和那些已经肯定不可能发展成为全局最优解的局部解。在此基础上，对存留的局部解考察下一步（下一个分量）的取值。,7,5.1 多段图问题,给定加权有向图G=(V,E,W),|V|=n，若G的顶点划分为k（k1）个不相交集合Vi（0ik+1），其中V1和Vk中分别只有一个顶点s（源点）和t（汇点），而且G中所有的边(u,v)均满足：若uVi，则v Vi+1，0ik，则称G是一个多段图。 从顶点s到顶点t的一条路径的成本是这条路径上所有边的权值之和，多段图问题就是求由s到t的最小成本路径（最短路径）。 为了求解方便，事先对顶点集V中的顶点按下述方式进行编号：首先将顶点s编为1，然后对V2中的顶点编号，V3的顶点接着V2中的最后一个编号继续往下编号，最后将t编为n。,8,5.1 多段图问题,9,5.1 多段图问题,1. 最优子结构性质。 设是一条由s到t的最短路径，则（ui,ui+1,uk-1,t）就是一条由顶点ui到t的最短路径。 2. 建立递归关系。 记md(i)为顶点i到顶点t的最短路径的成本，显然，md(n)=0。对于其它顶点，容易得到具有如下递归关系： 其中c(i,j)为边(i,j)的权值。,10,5.1 多段图问题,3. 计算最优值。 算法5.1 求解顶点到顶点的最短路径成本 输入：多段图的邻接矩阵c，顶点个数n； 输出：顶点i到汇点t的最短路径成本。 int MinCost(int c, int n) md(n)= 0; for (i=n-1; i0; i-) md(i)=; for (顶点i的所有邻接顶点j) if( md(i)c(i,j)+md(j) md(i)=c(i,j)+md(j); ,11,5.1 多段图问题,4. 构造最优解。 容易发现，在算法5.1计算最短距离的过程中已经蕴含了最短路径的结构信息，设顶点j是使取最小值的顶点i的邻接顶点，则顶点j是顶点i到t的最短路径上的前方顶点，此时只需要将顶点j的编号记录下来，最后就可以逐步构造得到s到t的最短路径。 算法5.2。,5.2 矩阵连乘问题,矩阵连乘积问题是指：给定n个矩阵A1An，其中Ai与Ai+1是可乘的，矩阵的维数Ai为pi-1*pi，要求确定一种矩阵连乘的顺序，使得计算矩阵连乘积需要的计算量为最小。 完全加括号的矩阵连乘积可递归地定义为： (1) 单个矩阵是完全加括号的； (2) 若矩阵连乘积A是完全加括号的，则A可表示为两个完全加括号的矩阵连乘积B、C的乘积并加括号，即A=(BC)。,13,5.2 矩阵连乘问题,每一种完全加括号方式对应一种矩阵连乘积的计算次序，矩阵连乘积问题即对于给定的n个矩阵，确定一种完全加括号方式，使得依此次序计算矩阵连乘积所需要的数乘次数最少，称这个计算次序为最优计算次序。,14,5.2 矩阵连乘问题,1. 最优子结构性质。 将矩阵连乘积简记为Ai:j。假设已经得到计算的一个最优次序（最优解），该计算次序在Ak和Ak+1之间将矩阵链断开。照此，我们要先计算Ai:k和Ak+1:j，然后，将所得的结果矩阵相乘得到Ai:j 。 显然，计算A1:n的一个最优次序中，计算A1:k和Ak+1:n的次序和计算的次序也是最优的。因此，矩阵连乘积问题满足最优子结构性质。,15,5.2 矩阵连乘问题,2. 建立递归关系。 设计算的最少数乘次数为mij，则问题的最优值为m1n。递归定义为：,16,5.2 矩阵连乘问题,3. 计算最优值。 算法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 (); ,17,5.2 矩阵连乘问题,4. 构造最优解。 算法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; ,18,5.3 0-1背包问题,0-1背包问题：给定n种物品和一个背包，物品i的重量是，价值为，背包容量为c，问如何选择装入背包的物品，使得装入背包的物品的总价值最大。在装入背包时，每种物品i只有两种选择，全部装入或者不装入。,19,5.3 0-1背包问题,1. 最优子结构性质。 0-1背包问题的解是一个n维0-1向量，不妨设(y1,y2,yn)是0-1背包问题的一个最优解，则部分解(y2,yn)对应为下面子问题的一个最优解：求维向量(x2,xn) ，使得 并且满足,20,5.3 0-1背包问题,2. 建立递归关系。 0-1背包问题的求解需要逐步确定解向量(x1,x2, xn)中的取值。假设按照的次序来确定的值： (1) 如果x1=0，问题转变为相对于其余n-1个物品，背包容量仍为c的0-1背包问题； (2) 如果x10 ，问题转变为相对于其余个物品，背包容量为c-w1的0-1背包问题。 则：,21,5.3 0-1背包问题,3. 递归计算最优值。 假设各物品的重量为正整数，用二维数组mij存储，那么求解0-1背包问题就是为二维数组m中填入相应的元素取值，且m1c中的值就是0-1背包问题的最优值。 算法5.7,22,5.3 0-1背包问题,4. 构造最优解。 考察递归关系中mij的取值，如果mij=mi+1j说明若要得到最优值，物品i不放入背包中，对应；如果mij=mi+1j-wi+vi ，则说明若要得到最优值，物品i应该放入背包中，对应，如此可按照算法5.8构造0-1背包问题的最优解。,23,5.3 0-1背包问题,5. 算法改进。 函数m(i,j)实际上是关于j的阶梯函数，容易证明，在i确定的情况下，m(i,j)是关于j的阶梯单调递增函数，并且可以发现m(i,j)实际上由若干跳跃点决定，因此，如果设用数组Pi记录的所有跳跃点，则Pi可以由Pi+1计算得到。,24,5.4 旅行售货员问题,旅行售货员问题（Traveling Salesman Problem，TSP）又称为货郎担问题，是指某售货员要到n个城市去推销商品，已知各城市之间的路程（或旅费）。售货员要选定一条从驻地出发，经过每个城市一次，最后回到驻地的路线，使总的路程（总旅费）最短（最小）。 容易想到，任取一出发点k，则剩下的n-1个顶点的任何一个排列对应路径均有可能与出发点k构成一条回路（若图G是有向完全图），对每条回路计算一次长度，在这些长度中选取最小者，其对应的路径即为所求，此时计算的时间复杂度为o(n-1)!)。,25,5.4 旅行售货员问题,1. 最优子结构性质。 从顶点i出发，经过G中各顶点最终返回顶点i的回路的解的结构为(i,x2,x3,xn)。 x2,x3,xn为n-1个顶点的一个排列。不妨设(i,y2,y3,yn)是问题的一个最优解，则(y2,y3,yn)是从顶点y2出发，经过G中其他顶点各一次，并最终返回顶点i的最短路径。容易利用反证法证明该结论是成立的，说明TSP问题满足最优子结构性质。,26,5.4 旅行售货员问题,2. 建立递归关系。 定义函数的d(k,v1)为从顶点k出发，经过V1中各顶点各一次，并最终返回顶点i的最短路径长度，TSP问题的最优值为d(i,V-i)。,27,5.4 旅行售货员问题,3. 递归计算最优值。算法5.9 4. 构造最优解。算法5.10,28,5.5 最长公共子序列问题,对于给定的2个序列X和Y，当另一序列Z既是X的子序列又是Y的子序列时，称Z是序列X和Y的公共子序列。若Z是X和Y的公共子序列中长度最大的，则Z是序列X和Y的最长公共子序列。 最长公共子序列问题即是：对于给定的两个序列X和Y，找出X和Y的最长公共子序列。,29,5.5 最长公共子序列问题,1. 最优子结构性质。 最长公共子序列问题具有最优子结构性质。设序列X=x1,x2,xm和Y=y1,y2,yn的最长公共子序列为Z=z1,z2,zk，则 (1) 若xm=yn，则zk=xm，且Zk-1是Xm-1和Ym-1的最长公共子序列； (2) 若xmyn，zkxm，则Z是Xm-1和Y的最长公共子序列； (3) 若xmyn，zkyn，则Z是X和Yn-1的最长公共子序列。,30,5.5 最长公共子序列问题,2. 建立递归关系。 设Lij为序列和的最长公共子序列的长度，,31,5.5 最长公共子序列问题,3. 计算最优值。算法5.11 4. 构造最长公共子序列。算法5.12,32,5.6 流水作业调度问题,流水作业调度问题一般指如下问题：n个作业要在由m台机器组成的流水线上进行加工。每个作业i可分解为m个任务，其中作业i的第j个任务要求必须在机器j上进行加工，作业i的m个任务必须顺序加工完成，即必须在完成之后才可以开始加工，并且一台机器在任何时刻只能加工一个任务。设任务在机器j上加工完成需要的时间为Tij，要求为n个作业安排一种加工顺序，使得从第一个作业开始加工，直到最后一个作业加工完成，所需要的时间最少，该加工顺序称为最优作业调度，这里我们假设各个作业加工的优先级都是相同的。,33,5.6 流水作业调度问题,已经证明，当m=3的时候，最优作业调度问题是一个NP难的问题，而当m=2时，可以找到求解该问题的多项式时间算法。 显然，最优调度问题满足最优子结构性质，即若在一个最优作业调度中去掉前面的作业，剩下的作业调度仍然是相应子问题的一个最优调度。,34,5.6 流水作业调度问题,Johnson法则： (1) 当 时，应将作业k安排在最前面，作为最优调度的第一个执行的作业； (2) 当 时，应将作业k安排在最后面，作为最优调度的最后一个执行的作业。 算法5.13,35,5.7 资源分配问题,设有m份资源和n个工程，对每个工程投入不同数量的资源获得的利润对应为每个工程的利润函数Pi(xi)，表示将xi份资源分配给第i个工程可获得的利润，那么，将m份资源分配给n个工程可获得的利润总和为 其中,36,5.7 资源分配问题,1. 最优子结构性质。设已经得到一个问题的最优解X=(x1,x2,xn)，则部分解(x1,x2,xn-1)是将(m-xn)份资源分配给前n-1个工程的子问题的一个最优解。 2. 建立递归关系。 计算最优值。 构造最优解。,37,5.8 动态规划小结,利用动态规划算法求解问题的过程是一个多阶段最优决策的过程，一般可分为如下四个求解步骤。 (1) 分析问题最优解的结构，并刻画其结构特征，证明其满足最优子结构性质。通过对问题的分析，将问题最优解的求解分为若干个阶段，各个阶段之间应具有明确的先后顺序关系； (2) 建立最优值的递归关系，问题的最优值对应的递归关系是各阶段决策的依据； (