《算法分析与设计AlgoDALectureNotesW8章节》由会员分享，可在线阅读，更多相关《算法分析与设计AlgoDALectureNotesW8章节（69页珍藏版）》请在金锄头文库上搜索。
1、Last Section,动态规划应用举例,资源分配问题 生产与存储问题 复合系统工作可靠性问题 排序问题 设备更新问题,可基于动态规划思想求解的 问题与算法,计算二项式系数 最长公共子序列 Li, j = 0 若i=0或j=0 =Li-1, j-1 + 1 若i0, j0 和ai= bj =max Li, j-1, Li-1, j 若i0, j0 和ai bj 矩阵链相乘,所有点对的最短路径问题,设G= （V，E）是一个有向图，其中的每条边（i, j）有一个非负的长度li, j, 如果从顶点i 到顶点j没有边，则li, j=。 问题：找出从每个顶点到其他所有顶点的距离（从顶点x到顶点y的距离
2、是指从x到y 的最短路径的长度）。 我们假设V =1，2，,n，设i和j 是V中两个不同的顶点，定义dki,j是从i到j， 并且不经过k+1, k+2,n中任何顶点的最短路径的长度。,所有点对的最短路径问题,例如d0i,j=li,j, d1i,j是从i到j， 除了可能经过顶点1以外，不经过任何其他顶点的最短路径，d2i,是从i到j， 除了可能经过顶点1、顶点2或同时经过它们以外，不经过任何其他顶点的最短路径，等等。 则dni,j是从i到j的最短路径长度，也就是从i到j的距离。给出这个定义，可以递归地计算dki,j如下 dki,j=li, j 若k = 0 =mindk-1i,j, dk-1i,
3、k+ dk-1k,j 若1kn,所有点对的最短路径问题,Floyd算法，用自底向上地解以上递推式的方法来处理。它用n+1 个n x n维矩阵D0，D1，,Dn来计算最短约束路径的长度。 开始时，如果ij 并且（i ,j）是G中的边，则置D0 i,i = 0, D0 i,j = li,j; 否则置D0 i,j =。 然后做n次迭代，使在第k次迭代后，Dk i,j含有从顶点i到顶点j，且不经过编号大于k的任何顶点的最短路径的长度。这样在第k次迭代中，可以用公式 计算Dk i,j。 *在第K次迭代中，第K行和第K列均不变，且其它元素只用K行列，故D不需做副本,所有点对的最短路径问题,算法FLOYD
4、输入：n x n维矩阵l1n,1n, 对应于有向图G=（1,2,n,E）中的边（i,j）的长度为li,j。 输出：矩阵D, 使得Di,j等于i到j的距离。 1 Dl 将输入矩阵l复制到D 2. for k1 to n 3. for i1 to n 4. for j1 to n 5. Di,j=minDi,j,Di,k +Dk,j 6. end for 7. end for 8. end for 显然，算法的运行时间是 (n3). 图例？,0/1 背包问题,0/1（同类物品数最大1）背包问题可以定义如下： 设U=u1,u2,un是一个准备放入容量为C的背包中的n项物品的集合。对于1jn,令sj和
5、vj分别为第j项物品的体积和价值，C,sj,vj和j 都是正整数。 要解决的问题是用U中的一些物品来装背包，这些物品的总体积不超过C，然而要使它们的总价值最大。假设每项物品的体积不大于C，给出有n项物品的U，我们要找出一个子集合 ，使得 在约束条件 下最大。,0/1 背包问题,为导出递归公式， 设Vi,j 表示从前i项u1，u2，,ui中取出来的装入体积为j的背包的物品的最大价值。这里，i的范围是从0到n, j的范围是从0到C。 则，要寻求的是值Vn,C。 有V0,j对于所有j的值是0，当背包中没有物品。 Vi,0对于所有i的值为0，当没有物品可放到容积为0的背包里。,0/1 背包问题,当i和
6、j都大于0时，有以下的结论： Vi,j是下面两个量的最大值： Vi-1,j:仅用最优的方法取自u1，u2，,ui-1的物品去装入体积为j的背包所得到的价值最大值。 Vi-1,j-si+vi:用最优的方法取自u1，u2，,ui-1的物品去装入体积为j-si的背包所得到的价值最大值加上物品ui的价值。这仅应用于如果jsi以及它等于把物品ui加到背包上的情况。 观察结论对于找出最优装背包时的值，有下面的递推式 Vi,j = 0 若i=0或j=0 =Vi-1,j 若jsi =MaxVi-1,j,Vi-1,j-si+vi 若jsi,0/1 背包问题,现在可以很简单地用动态规划来求解这个整数规划问题。 用
7、一个(n+1) x (C+1)的表来计算Vi, j的值，只需利用上面的公式逐行地填表V0n,0C即可。,0/1 背包问题,算法KNAPSACK 输入：物品集合U= u1，u2，,un，体积分别为v1,v2,vn，容量为C的背包。 输出： 的最大总价值，且满足 ，其中 。 for i0 to n Vi, 0 0 end for for j0 to C V0, j 0 end for for i1 to n for j1 to C Vi, j Vi-1, j if sij then Vi, j MaxVi, j,Vi-1, j-si+vi end for end for return Vn, C
8、(nc),计算有向图的传递闭包,定义 一个n顶点有向图的传递闭包可以定义为一个n阶布尔矩阵T=tij； 如果从第i个顶点到第j个顶点之间存在一条有效的有向路径，矩阵第i行（1in）第j列（1jn）的元素为1； 否则，tij为0。 可以通过深度优先查找和广度优先查找生成有向图的传递闭包； 但对同一个有向图遍历了多次（需以每个顶点为起点做一次遍历）。,Warshall 算法,Warshall算法通过一系列n阶布尔矩阵来构造一个给定的n个顶点有向图的传递闭包： R(0),R(k-1),R(k),R(n) （1） 当且仅当，从第i个顶点到第j个顶点之间存在一条有向路径（长度大于0）并且路径的每一个中间
9、顶点的编号不大于k时，矩阵R(k)的第i行第j列的元素rij(k)的值等于1。 这一系列矩阵从R（0）开始，这个矩阵不允许它的路径中包含任何中间顶点；所以R（0）就是有向图的邻接矩阵。 R（1）包含允许使用第一个顶点作为中间顶点的路径信息；每一个后继矩阵相对它的前趋来说，都允许增加一个顶点作为其路径上的顶点。 序列中的最后一个矩阵，反映了能够以有向图的所有n个顶点作为中间顶点的路径，因此它就是有向图的传递闭包。,Warshall 算法的主要思想,任何R（k）中的所有元素都可以通过它在序列（1）中的直接前趋R（k-1）计算得到。把矩阵R（k）中第i行第j列的元素rij(k)置为1意味着存在一条从
10、第i个顶点到第j个顶点的路径，路径中每一个中间顶点的编号都不大于k： vi，每个顶点编号都不大于k的中间顶点列表，vj (2) 对于路径（2），有两种可能： 1、路径的中间顶点列表中不包含第k个顶点，那么这条从vi到vj的路径中顶点的编号不会大于k-1, 所以 rij(k-1)也等于1。 2、路径的中间顶点rij(k-1) 的确包含第k个顶点vk。,Warshall 算法,假设vk在列表中只出现一次，路径（2）可以改写成以下形式： （若不只一次，只要简单地把路径中第一个vk和最后一个vk之间的顶点全部消去，就可以创建一条从vi到vj的新路径） vi, 编号k-1的顶点， vk，编号k-1的顶点
11、，vj 这表明： 存在一条从vi到vk的路径，路径中每个中间顶点的编号都不大于k-1（因此rik(k-1)=1）； 存在一条从vk到vj的路径，路径中每个中间顶点的编号也都不大于k-1（因此rkj(k-1)=1）。,Warshall 算法,上述说明： 如果rij(k)=1， 则： rij(k-1)=1，或 rik(k-1)=1且rkj(k-1)=1。 其逆命题也成立。因此，对于如何从矩阵R(k-1)的元素中生成矩阵R(k)的元素，我们有下面的公式： rij(k)= rij(k-1) or rik(k-1) and rkj(k-1) 该公式意味着以下规则： 如果一个元素rij在R(k-1)中是1
12、，它在R(k)中仍然是1。 如果一个元素rij在R(k-1)中是0，当且仅当矩阵中第i行第k列的元素和第k行第j列的元素都是1，该元素在R(k)中才能变成1。（如图） * 例,Warshall 算法,算法Warshall(A1n,1n) /实现计算传递闭包的Warshall算法 /输入：包括n个顶点有向图的邻接矩阵A /输出：该有向图的传递闭包 R(0)A for k1 to n do for i1 to n do for j1 to n do R(k)i,j Rk-1i,jor Rk-1i,kand Rk-1k,j return R(n) (n3) ; sparse graph? DFS?
13、BFS? 比特串，位操作语句,最优二叉查找树,最优二叉查找树：在查找中的平均键值比较次数是最低的。 （集合中元素的查找概率是已知的） 例：分别以概率0.1，0.2，0.4，0.3来查找4个键A，B，C，D。 在成功查找时，第一棵树的平均键值比较次数为2.9， 而第二棵树是2.1。,最优二叉查找树,0.11+0.22+0.43+0.34=2.9,0.12+0.21+0.42+0.33=2.1,0.1，0.2，0.4，0.3 A，B，C，D,最优二叉查找树,最优二叉查找树：在查找中的平均键值比较次数是最低的。（集合中元素的查找概率是已知的） 例：分别以概率0.1，0.2，0.4，0.3来查找4个键
14、A，B，C，D。 在成功查找时，第一棵树的平均键值比较次数为2.9， 而第二棵树是2.1。 构造*的穷举方法是不现实的：包含n个键的二叉查找树的总数量等于第n个Catalan数，它以4n/n1.5的速度逼近无穷大。 (1,1,2,5,14,42,132,429,1430,4862,16796),最优二叉查找树,设a1,an 是从小到大排列的互不相等的键，p1,pn是它们的查找概率。Tij是由键ai,aj构成的二叉树，Ci,j是在这棵树中成功查找的最小的平均查找次数，其中，i,j 是一些整数下标， 1ijn. 为了推导出动态规划算法中隐含的递推关系，需要考虑从键ai,aj中选择一个根ak的所有可
15、能的方法。 以ak 为根的左子树Tik-1和右子树Tjk+1中的键ai,ak-1 和ak+1,aj也应分别是最优排列的。,最优二叉查找树,若从1开始对树的层数进行计数，有下列递推关系式(顶点层数为0) ： （设s为as在Tik-1中的层数，s为as在Tjk+1中的层数）,最优二叉查找树,因此有下列递推关系式： 当1ijn 时 当1in+1 时, ci,i-1=0; empty tree 当1in 时, ci,i =pi ; single node,最优二叉查找树,算法OptimalBST(P1n) /用动态规划求最优二叉查找树 /输入：一个n个键的有序列表的查找概率数组P1n /输出：在最优BST中成功查找的平均比较次数，以及最优BST中子树的根表R for i 1 to n do Ci,i-1 0 Ci,i Pi Ri,i i Cn+1,n 0 for d1 to n-1 do /对角线计数 for i1to n-d do ji+d minval for ki to j do if Ci,k-1+Ck+1,jminval then minval
