算法分析与设计第5章

《算法分析与设计第5章》由会员上传分享，免费在线阅读，更多相关内容在教育资源-天天文库。

1、算法设计方法吴哲辉崔焕庆马炳先吴振寰编著机械工业出版社第5章动态规划算法多段图问题矩阵连乘问题0-1背包问题旅行售货商问题最长公共子序列问题流水作业调度问题资源分配问题动态规划小结2第5章动态规划算法动态规划（DynamicProgramming）是运筹学的一个分支，是求解决策过程最优化的数学方法。20世纪50年代初美国数学家R.E.Bellman等人在研究多阶段决策过程（MultistepDecisionProcess）的优化问题时，提出了著名的最优化原理（PrincipleofOptimality），将多阶段决策过程转化为一系列的单阶段决策问题，创立了解

2、决这类过程优化问题的新方法——动态规划。3第5章动态规划算法最优化原理是指一个最优化策略具有这样的性质：不论过去的状态和决策如何，余下的决策必须相对于前一决策所产生的状态构成最优决策序列，也就是说，一个最优化策略的子策略总是最优的，问题的最优解可以通过其子问题的最优解构成。一个问题若满足最优化原理又称其具有最优子结构性质。4第5章动态规划算法根据动态规划的思想方法设计的算法称为动态规划算法。动态规划算法常用于求解这样一类问题：问题的解可以表示成一个解向量（x1,x2,x3,…,xn），算法分为n步进行，每一步确定解向量中一个分量的取值。5第5章动态规划算法动

3、态规划算法的基本思想是：每一步都列出各种可能的局部解，然后通过计算，舍去那些不满足约束条件的局部解和那些已经肯定不可能发展成为全局最优解的局部解。在此基础上，对存留的局部解考察下一步（下一个分量）的取值。65.1多段图问题给定加权有向图G=(V,E,W),

4、V

5、=n，若G的顶点划分为k（k>1）个不相交集合Vi（0

6、到t的最小成本路径（最短路径）。为了求解方便，事先对顶点集V中的顶点按下述方式进行编号：首先将顶点s编为1，然后对V2中的顶点编号，V3的顶点接着V2中的最后一个编号继续往下编号，最后将t编为n。75.1多段图问题85.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)的权值。95.1多段图问题3.计算最优值。算法5.1求解

7、顶点到顶点的最短路径成本输入：多段图的邻接矩阵c，顶点个数n；输出：顶点i到汇点t的最短路径成本。intMinCost(intc[][],intn){md(n)=0;for(i=n-1;i>0;i--){md(i)=∞;for(顶点i的所有邻接顶点j)if(md(i)>c(i,j)+md(j))md(i)=c(i,j)+md(j);}}105.1多段图问题4.构造最优解。容易发现，在算法5.1计算最短距离的过程中已经蕴含了最短路径的结构信息，设顶点j是使取最小值的顶点i的邻接顶点，则顶点j是顶点i到t的最短路径上的前方顶点，此时只需要将顶点j的编号记录下来，

8、最后就可以逐步构造得到s到t的最短路径。算法5.2。115.2矩阵连乘问题矩阵连乘积问题是指：给定n个矩阵A1~An，其中Ai与Ai+1是可乘的，矩阵的维数Ai为pi-1*pi，要求确定一种矩阵连乘的顺序，使得计算矩阵连乘积需要的计算量为最小。完全加括号的矩阵连乘积可递归地定义为：(1)单个矩阵是完全加括号的；(2)若矩阵连乘积A是完全加括号的，则A可表示为两个完全加括号的矩阵连乘积B、C的乘积并加括号，即A=(BC)。125.2矩阵连乘问题每一种完全加括号方式对应一种矩阵连乘积的计算次序，矩阵连乘积问题即对于给定的n个矩阵，确定一种完全加括号方式，使得依此

9、次序计算矩阵连乘积所需要的数乘次数最少，称这个计算次序为最优计算次序。135.2矩阵连乘问题1.最优子结构性质。将矩阵连乘积简记为A[i:j]。假设已经得到计算的一个最优次序（最优解），该计算次序在Ak和Ak+1之间将矩阵链断开。照此，我们要先计算A[i:k]和A[k+1:j]，然后，将所得的结果矩阵相乘得到A[i:j]。显然，计算A[1:n]的一个最优次序中，计算A[1:k]和A[k+1:n]的次序和计算的次序也是最优的。因此，矩阵连乘积问题满足最优子结构性质。145.2矩阵连乘问题2.建立递归关系。设计算的最少数乘次数为m[i][j]，则问题的最优值为m

10、[1][n]。递归定义为：155.2矩阵连乘问题3.