算法设计与分析.pptVIP

最优解 求问题最优解即最短路径时，如果在计算每一个cost(i,j)的同时，记录下每个状态（结点j）所作的决策，设为d(i,j)来记录从第i阶段结点j到t的最短路径上该结点的下一个结点编号则可以容易地求出这条最小成本的路径。对于图5-8可以得到：d(4,7)=d(4,8)=9d(3,4)=8，d(3,5)=8，d(3,6)=8d(2,1)=5，d(2,2)=5,d(2,3)=6d(1,0)=2从d的值确定最短路径上的结点为：（0，d(1,0)=2,d(2,2)=5,d(3,5)=8,d(4,8)=9） 多段图显然也存在重叠子问题现象。如cost(3,5)、cost(3,6)、cost(3,7)的计算都用到了cost(4,9)的值。如果保存了cost(4,9)的值，就可以避免重复计算它的值。5、算法分析 在上述求解过程中，初始化的时间复杂度为O(n),遍历总的边数的时间复杂度为O(e),如此可得总的时间复杂度为O(n+e)。 多段图问题虽然简单，但用处很大，很多实际问题都可用多段图来描述，例如资源分配问题，假设把m个资源分配给n个项目，那么可用n+1段图来表示。5.3.2每对结点间最短距离1、问题描述 多设G=(V,E)是一个有n个结点的带权有向图，w(i,j)是权函数每对结点间的最短路径问题是指求图中任意一对结点i和j之间的最短路径。2、动态规划算法的求解设G=(V,E)是一带权有向图，d(i,j）是从结点i到结点j的最短路径长度，k是这条路径上的一个结点，d(i,k）和d(k,j）分别是从i到k和从k到j的最短路径长度，则必有d(i,j）=d(i,k）+d(k,j）。若不然，则d(i,j）代表的路径就不是最短路径。这表明每对结点之间的最短路径问题的最优解具有最优子结构特性。最优解的递推关系重叠子问题：为了计算dk[i][j]时，必须先计算dk-1[i][j]、dk-1[i][k]和dk-1[i][k]，dk-1的元素被多个dk的元素的计算共享。弗洛伊德算法弗洛伊德算法的基本思想是：令k=0,1,…,n-1，每次考察一个结点k。二维数组d用于保存各条最短路径的长度，其中，d[i][j]存放从结点i到结点j的最短路径的长度。在算法的第k步上应作出决策：从i到j的最短路径上是否包含结点k。显然两结点i和j之间的最短路径的长度就是问题的最优解值。为了得到最优解，弗洛伊德算法还使用了一个二维数组path[i][j]保存相应的最短路径，与当前迭代的次数有关。3、算法描述 寻找每对结点之间的最短路径长度算法SHORTPATH的伪代码描述如下：【输入】有向图的成本邻接矩阵COST(n，n)【输出】所有结点对之间的最短路径的成本（1）使用二维数组COST[n][n]表示n结点图的成本邻接矩阵；D[i][j]表示结点Vi到Vj的最短路径的成本；PATH[i][j]表示获得最短路径经过的顶点编号；（2）初始化，对i，j从1到n求算D[i][j]，即将COST[i][j]复制到D[i][j]；（3）在求算i，j之间最短路径的成本时，随着中间结点的加入，需重新计算D[i][j]，同时记录PATH[i][j]；（4）从1到n计算得到有向图的最短路径成本和获得最短路径的结点编号；4、算法举例

例5-4求解如图5-12所示的有向图的所有节点之间的最短路径长度。5、算法分析 Floyd算法在对顶点i到顶点j的最短路径d[i][j]进行计算时，每次都需要对其第i行及第j列所对应的元素进行相加运算，一共有n次加法运算，且对于迭代的距离矩阵，其中共有n×n个元素，因此，算法的时间复杂度为O(n3),空间复杂度为O(n2)。5.4组合问题中的动态规划算法1、问题描述 给定n件重量为w0、w1、…wn-1的物品和一个最大载重量为M的背包。这n件物品的价值分别为p0、p1、…、pn-1，其中第i件物品的重量是wi，如果将第i件物品装入背包其收益为pi，这里wi0，pi0(0≤in)。背包问题是问应如何选择装入背包的物品，使得装入背包中物品的总价值最大?如果在选择装入背包的物品时，对每种物品i只有两种选择,要么装入要么不装入，物品不能分割装入，则称为0/1背包问题。注意这里所有物品的重量和背包的总重量都是正整数，即0-1背包问题是一个特殊的整数规划问题。5.4.10/1背包问题2、动态规划算法的求解最优解的递归算法递归式3、算法描述0-1背包问题算法KNAPSACK伪代码描述：【输入】n件物品的重量W=(w0、w1、…wn-1)和价值p=（p0、p1、…、pn-1），以及背包的载重W【输出】0-1背包问题的