网络优化课件.ppt

* 权函数法 记当前森林中最大活跃点的集合为H,并令?=?i?H ?(i),其中?(i)=max{0,K+1-|D(i)|}, K为一个待定参数. 显然, 0??(i)?K. - 6.5.2 复杂度分析 (1) 对最大活跃点 i 沿当前(允许)弧(i,j)执行一次非饱和推进; (2) 对最大活跃点 i 沿当前(允许)弧(i,j)执行一次饱和推进; (3) 对最大活跃点i，重新进行距离标号; (4) 在当前森林中增加一条新的当前(允许)弧. (1) 对最大活跃点i沿当前(允许)弧(i,j)执行一次非饱和推进: 推进后当前弧(i,j)仍然为允许弧，当前森林不会发生改变; i变为非活跃点; j成为活跃点，也可能成为新的最大活跃点; 由于|D(i)||D(j)|, 所以当|D(i)|?K时, ?(i)+?(j)至少减少1个单位;否则, ?(i)+?(j)保持不变. 6.5 最高标号预流推进算法 下面讨论算法的各种操作对?的值的影响, 有四种可能: * (2) 对最大活跃点i，沿当前(允许)弧（i，j）执行一次饱和推进: 推进后，当前弧（i，j）不再是允许弧(因为残留容量为0)，所以从当前森林中退出. 但节点i仍为最大活跃点，同时节点j成为活跃点，因此也可能成为新的最大活跃点. 所以此时?可能增加最多K个单位. - 6.5.2 复杂度分析 (3) 对最大活跃点i，重新进行距离标号: 此时, 说明从i出发没有允许弧, 即它是当前森林中的一个根节点. 由于i是最大活跃点, D(i)中的所有其它节点不可能是活跃点. 重新标号后, 当前树林中所有进入i的弧成为非允许弧, 所以从当前森林中退出, 即|D(i)|=1. 但这并不会增加任何新的活跃点或最大活跃点, 因此此时?可能增加最多K个单位. 6.5 最高标号预流推进算法 * (4) 在当前森林中增加一条新的当前(允许)弧: 此时, 不会产生任何新的最大活跃节点,而只可能使一些节点的后代集合扩大, 因此可能使某些最大活跃点变成非最大活跃点. 无论如何, ?的值不可能增加. - 6.5.2 复杂度分析 把算法的执行过程分成若干个阶段来考虑, 每一个阶段是指算法中两次相邻的重标号操作之间的预流推进. 预流推进算法中最多含有O(n2)个阶段. 我们把阶段分成两类: 最多执行2n/K次非饱和推进的阶段; 最少执行2n/K次非饱和推进的阶段. 6.5 最高标号预流推进算法 算法中饱和推进的总次数为O(mn); 所有节点重标号次数最多为O(n2). 算法中?最多增加O(mnK+n2K)= O(mnK)个单位. * 最多执行2n/K次非饱和推进的阶段: 所有这类阶段中的非饱和推进的次数之和最多为O(n3/K)次 - 6.5.2 复杂度分析 因此，这两类非饱和推进的次数之和为O(n3/K +mnK). 6.5 最高标号预流推进算法 最少执行2n/K次非饱和推进的阶段: 由于网络中后代个数不少于K个的节点最多有n/K个, 所以此阶段至少有n/K次非饱和推进来自于后代个数少于K个的节点. 根据上面对四种可能情形的讨论，这n/K次非饱和推进每次使得?减少至少1个单位. 开始时?最多为nK，算法结束时?为0，所以所有这类阶段中的非饱和推进的次数之和最多为O(mnK)次. 取K= ，则得到两类非饱和推进的次数之和为O( ) 定理6.7 最高标号预流推进算法复杂度为O( ). * 6.6单位容量网络上的最大流算法(简介) 定义6.10 每条弧上的容量(上界)都是1个单位的网络称为单位容量网络（unit capacity network）. 如果在这种单位容量网络中, 除了源点和汇点以外, 所有其它节点上要么最多只有一条入弧, 要么最多只有一条出弧, 则称这种网络为单位容量简单网络（unit capacity simple network）. * 6.6.1 单位容量网络上的最大流算法 6.6单位容量网络上的最大流算法 6.6.2 单位容量简单网络上的最大流算法 略（自学） 略（自学） O({mn2/3 ,m3/2}) O(mn1/2) * 最小费用流问题 (Minimum Cost Flow Problem) 第1讲 * 最小费用流问题的例子 许多实际问题都可以转化为最小费用流问题 S