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

图的任意两点间的最短路径Warshall算法：求有向图传递闭包Floyd算法：求图的任意两点间的最短路径图的任意两点间的最短路径问题的描述：已知图G=(V,E),V={v1,v2,…,vn}及距离矩阵D=（dij)n*n求图G的任意两点间的最短距离。，其它v，vEvv，若vvdjijijiji0),(),(,的长度分析：常见的图问题有25个，这个问题的算法是Floyd提出的。设矩阵，定义矩阵运算如下：其中令nnijnnijbBaA)(,)(nnijcBAC)(njibackjikij....2,1,},min{jiknkDDDDDkk,,~1,,)1()()1()1(分析：显然表示从出发经过某一中间点到达点的最短距离。同样表示从经过两个中间点到的最短距离。}min{),()2()2()2(kjikijijddddD定义：令则表示从vi点到vj点的最短距离。由于D(k)有n2个元素，每个元素要作n-2次加法与n-3次比较，依以上办法可知求的时间复杂性为。nnijijbaBA)),(min(nnijndDDDD)(...*)()2()1(*ijd)(4n动态规划算法设为从vi出发中途经过以(v1,v2,…,vk)为中间点到vj的最短距离。则有其中并且即为i,j之间的最短距离。)()()(kijkdD)(kijdnjiddddkijkikkijkij,...,2,1,},,min{)1()1()1()(ijijdd)0()(nijdvoidFloyd(intd[][],intn){inta[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整数规划。整数规划问题所谓整数规划，就如求下面问题的最优解。maxz=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开始。整数规划问题例1maxz=110x1+160x2+260x3+210x42x1+3x2+5x3+4x4≤20xi≥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≤[k/3]∴x2=0整数规划问题k-3x2为奇数时f2（k）=max{160x2+55（k-3x--1）}0≤x2≤[k/3]=max{55k-55-5x2}0≤x2≤[k/3]=55k-55∴x2=0整数规划问题所以55k,k为偶数f2(k)=55k-55,k为奇数整数规划问题f3（k）=max{260x3+f2（k-5x3）}0≤x3≤[k/5]整数规划问题k-5x3为偶数时f3（k）=max{260x3+55(k-5x3)}0≤x3≤[k/5]=max{260x2+55k-275x3}0≤x3≤[k/5]=max{55k-15x3}0≤x3≤[k/5]=55kx3=0整数规划问题k-5x3为奇数时f3（k）=max{260x3+55(k-5x3)-55}0≤x3≤[k/5]=max{55k-15x3-55}=55k-550≤x3≤[k/5]x3=0整数规划问题所以55k,k为偶数f3(k)=55k-55,k为奇数整数规划问题f4(20)=max{210x4+f3(20-4x4)}0≤x4≤5=max{210x4+55(20-4x4)}0≤x4≤5整数规划问题由于20-4x4为偶数故有f4(20)=max{1100-10x4}0≤x4≤5=1100x4=0故最优解为：x1=10，x2=x3=x4=0，z=11000-1整数规划问题0-1整数规划问题。即变量只取0或1两个值的整数规划问题。maxz=c1x1+c2x2+…+cnxna1x1+a2x2+…+anxn≤bxi=0，1，i=1,2,…,n0-1整数规划问题令zn（b）=max{zn-1（b），zn-1（b-an）+cn}一般地有：zi（x）=max{zi-1（x），zi-1（x-ai）+ci}0-1整数规划问题计算从z0（a）=0开始，并且当x0时令zi（x）=-∞z1（x）=max{z0（x），z0（x-a1）+c1}，z2（x）=max{z1（x），z1（x-a2）+c2}，…………zn（x）=max{zn-1（x），zn-1（x-an）+cn}0-1整数规划问题例子maxz=2x1+3x2+4x3，x1+2x2+5x3≤6x1，x2，x3=0或10-1整数规划问题0，x≥0z0（x）=-∞，x0z1（x）=max{z0（x），z0（x-1）+2}max{0，-∞}=0，0≤x1，=max{0，2}=2，x≥10-1整数规划问题z2（x）=max{z1（x），z1（x-2）+3}max{0，-∞}=0，0≤x1max{2，-∞}=2，1≤x2=max{2，3}=3，2≤x3max{2，5}=5，x≥30-1整数规划问题z3（x）=max{z2（x），z2（x-5）+4}max{0，-∞}=0，x1，max{2，-∞}=2，1≤x2，max{3，-∞}=3，2≤x3，=max{5，4}=5，3≤x6，max{5，6}=6，6≤x7，max{5，7}=7，7≤x8，max{5，9}=9，x≥8。0-1整数规划问题由于x1+2x2+5x3≤6，故x3=1，z2（x-5）+4=6，z2（x-5）=2，x2=0，x1=1。故得最优解：maxz=6x1=1，x2=0，x3=1