算法分析与设计AlgoDALectureNotesW8章节.pptVIP

Last Section 动态规划应用举例 资源分配问题 生产与存储问题 复合系统工作可靠性问题 排序问题 设备更新问题 可基于动态规划思想求解的问题与算法 计算二项式系数 最长公共子序列 L[i, j] = 0 若i=0或j=0 =L[i-1, j-1] + 1 若i0, j0 和ai= bj =max{ L[i, j-1], L[i-1, j]} 若i0, j0 和ai≠ bj 矩阵链相乘 所有点对的最短路径问题 设G= （V，E）是一个有向图，其中的每条边（i, j）有一个非负的长度l[i, j], 如果从顶点i 到顶点j没有边，则l[i, j]=∞。 问题：找出从每个顶点到其他所有顶点的距离（从顶点x到顶点y的距离是指从x到y 的最短路径的长度）。 我们假设V ={1，2，…,n}，设i和j 是V中两个不同的顶点，定义dki,j是从i到j， 并且不经过{k+1, k+2,…,n}中任何顶点的最短路径的长度。 所有点对的最短路径问题 例如d0i,j=l[i,j], d1i,j是从i到j， 除了可能经过顶点1以外，不经过任何其他顶点的最短路径，d2i,是从i到j， 除了可能经过顶点1、顶点2或同时经过它们以外，不经过任何其他顶点的最短路径，等等。 则dni,j是从i到j的最短路径长度，也就是从i到j的距离。给出这个定义，可以递归地计算dki,j如下 dki,j=l[i, j] 若k = 0 =min{dk-1i,j, dk-1i,k+ dk-1k,j} 若1≤k≤n 所有点对的最短路径问题 Floyd算法，用自底向上地解以上递推式的方法来处理。它用n+1 个n x n维矩阵D0，D1，…,Dn来计算最短约束路径的长度。 开始时，如果i≠j 并且（i ,j）是G中的边，则置D0 [i,i] = 0, D0 [i,j] = l[i,j]; 否则置D0 [i,j] =∞。 然后做n次迭代，使在第k次迭代后，Dk [i,j]含有从顶点i到顶点j，且不经过编号大于k的任何顶点的最短路径的长度。这样在第k次迭代中，可以用公式 计算Dk [i,j]。 *在第K次迭代中，第K行和第K列均不变，且其它元素只用K行列，故D不需做副本 所有点对的最短路径问题 算法FLOYD 输入：n x n维矩阵l[1…n,1…n], 对应于有向图G=（{1,2,…,n},E）中的边（i,j）的长度为l[i,j]。 输出：矩阵D, 使得D[i,j]等于i到j的距离。 1． D←l {将输入矩阵l复制到D} 2. for k←1 to n 3. for i←1 to n 4. for j←1 to n 5. D[i,j]=min{D[i,j],D[i,k] +D[k,j]} 6. end for 7. end for 8. end for 显然，算法的运行时间是 Θ(n3). 图例？ 0/1 背包问题 0/1（同类物品数最大1）背包问题可以定义如下： 设U={u1,u2,…,un}是一个准备放入容量为C的背包中的n项物品的集合。对于1≤j≤n,令sj和vj分别为第j项物品的体积和价值，C,sj,vj和j 都是正整数。 要解决的问题是用U中的一些物品来装背包，这些物品的总体积不超过C，然而要使它们的总价值最大。假设每项物品的体积不大于C，给出有n项物品的U，我们要找出一个子集合 ，使得 在约束条件 下最大。 0/1 背包问题 为导出递归公式， 设V[i,j] 表示从前i项{u1，u2，…,ui}中取出来的装入体积为j的背包的物品的最大价值。这里，i的范围是从0到n, j的范围是从0到C。 则，要寻求的是值V[n,C]。 有V[0,j]对于所有j的值是0，当背包中没有物品。 V[i,0]对于所有i的值为0，当没有物品可放到容积为0的背包里。 0/1 背包问题 当i和j都大于0时，有以下的结论： V[i,j]是下面两个量的最大值： V[i-1,j]:仅用最优的方法取自{u1，u2，…,ui-1}的物品去装入体积为j的背包所得到的价值最大值。 V[i-1,j-si]+vi:用最优的方法取自{u1，u2，…,ui-1}的物品去装入体积为j-si的背包所得到的价值最大值加上物品ui的价值。这仅应用于如果j≥si以及它等于把物品ui加到背包上的情况。 观察结论对于找出最优装背包时的值，有下面的递推式 V[i,j] = 0 若i=0或j=0 =V[i-1,j] 若jsi =Max{V[i-1,j],V[i-1,j-si]+vi} 若j≥si 0/1 背包问题 现在可以很简单地用动态规划来求解这个整数规划问题