2010-2011-2《算法分析》ppt-7动态规划--3.ppt

图的任意两点间的最短路径 Warshall算法：求有向图传递闭包 Floyd算法：求图的任意两点间的最短路径 图的任意两点间的最短路径 问题的描述： 已知图G=(V,E),V={v1,v2,…,vn}及距离矩阵 D=（d ij ) n*n 求图G的任意两点间的最短距离。 分析： 常见的图问题有25个，这个问题的算法是Floyd提出的。 设矩阵 ，定义矩阵运算如下： 其中 令 分析： 显然 表示从 出发经过某一中间点到达 点的最短距离。同样 表示从 经过两个中间点到 的最短距离。 定义： 令 则 表示从 vi 点到 vj 点的最短距离。 由于D(k) 有 n2个元素，每个元素要作n-2 次加法与 n-3次比较，依以上办法可知求 的时间复杂性为 。 动态规划算法 设 为从 vi出发中途经过以(v1,v2,…,vk) 为中间点到vj 的最短距离。则有 其中 并且 即为 i,j 之间的最短距离。 void Floyd(int d[][],int n) { int a[n][n],I,j,k; for(i=1;i=n;i++) for(j=1;j=n;j++) a[i][j]=d[i][j]; for(k=1;k=n;k++) for(i=1;i=n;i++) for(j=1;j=n;j++) if(a[i][j]a[i][k]+a[k][j]) a[i][j]=a[i][k]+a[k][j] for(i=1;i=n;i++) { for(j=1;j=n;j++) printf(“%d “,a[i][j]; printf(“\n”); } } 整数规划问题 整数规划是规划论的一个方面，它的求解难度很大，目前还没有一种方法能有效地求解一切整数规划。 整数线性规划模型大致可分为两类： 1o 变量全限制为整数时，称纯（完全）整数规划。 2o 变量部分限制为整数的，称混合整数规划。 3o 变量只能取0或1时，称之为0-1整数规划。 整数规划问题 所谓整数规划，就如求下面问题的最优解。 max z=c1x1+c2x2+…+cnxn 满足约束条件： a1x1+a2x2+…+anxn≤b xi为非负整数,i=1,2,…,n 如果xi可以不是整数，就变成了线性规划问题。 整数规划问题 令fn(b)=max{fn-1 (b-anxn)+cnxn} 0≤xn≤[ b/an] 一般有 fi(x)=max{fi-1 (x-aixi)+cixi}，i=2,3,…,n 0≤xi≤[ b/ai] 计算从f0(x)≡0开始。 整数规划问题 例1 max z=110x1+160x2+260x3+210x4 2x1+3x2+5x3+4x4≤20 xi≥0 是整数 整数规划问题 令 fi（k）= max {110x1} 0≤x1≤[k/2] 故有 55k ，k为偶数 f1（k）= 55（k-1） ，k为奇数 整数规划问题 f2（k）= max {f1（k-3x2）+160x2} 0≤x2≤[k/3] k-3x2为偶数时 f2（k）= max {160x2+55（k-3x2）} 0≤x2≤[k/3] =max{55k-5x2}=55k 0≤x2≤[