[工学]第八章线性规划和网络流.pptVIP

预流推进算法 1 算法基本思想 增广路算法的特点是找到增广路后，立即沿增广路对网络流进行增广。 每一次增广可能需要对最多n-1条边进行操作。 最坏情况下，每一次增广需要O(n)计算时间。 有些情况下，这个代价是很高的。下面是一个极端的例子。 无论用哪种增广路算法，都会找到10条增广路，每条路长为10，容量为1。 共需要10次增广，每次增广需要对10条边进行操作，每条边增广1个单位流量。 10条增广路中的前9个顶点（前8条边）是完全一样的。 如果直接将前8条边的流量增广10个单位，而只对后面长为2的不同的有向路单独操作，就可以节省许多计算时间。 这就是预流推进（preflow push )算法的基本思想。 预流推进算法注重对每一条边的增流，而不必每次一定对一条增广路增流。 通常将沿一条边增流的运算称为一次推进（push）。 在算法的推进过程中，网络流满足容量约束，但一般不满足流量平衡约束。 从每个顶点（除s和t外）流出的流量之和总是小于等于流入该顶点的流量之和。 这种流称为预流（preflow）。这也是这类算法被称为预流推进算法的原因。 下面先给出预流的严格定义。 给定网络G=(V,E)一个预流是定义在G的边集E上的一个正边流函数。 该函数满足容量约束，即对G的每一条边(v,w)∈E，满足0≤flow(v,w)≤cap(v,w)。 G的每一中间顶点满足流出量小于或等于流入量。 即对每个v∈V(v≠s,t)有 满足条件 的中间顶点v称为活顶点。 量 称为顶点v的存流。 按此定义，源s和汇t不可能成为活顶点。 对网络G上的一个预流，如果存在活顶点，则说明该预流不是可行流。 预流推进算法就是要选择活顶点，并通过把一定的流量推进到它的邻点，尽可能地将当前活顶点处正的存流减少为0，直至网络中不再有活顶点，从而使预流成为可行流。 如果当前活顶点有多个邻点，那么首先推进到哪个邻点呢? 由于算法最后的目的是尽可能将流推进到汇点t，因此算法应寻求把流量推进到它的邻点中距顶点t最近的顶点。 预流推进算法中用到一个高度函数h来确定推流边。 对于给定网络G=(V,E)的一个流，其高度函数h是定义在G的顶点集V上的一个非负函数。该函数满足： （1）对于G的残流网络中的每一条边(u,v)有，h(u) ? h(v)+1； （2）h(t)=0。 G的残流网络中满足h(u) = h(v)+1的边(u,v)称为G的可推流边。 一般的预流推进算法 一般的预流推进算法的每次迭代是一次推进运算或者一次高度重新标号运算。 如果推进的流量等于推流边上的残留容量，则称为饱和推进，否则称为非饱和推进。 算法终止时，网络中不含有活顶点。此时只有顶点s和t的存流非零。此时的预流实际上已经是一个可行流。 算法预处理阶段已经令h(s)=n，而高度函数在计算过程中不会减少，因此算法在计算过程中可以保证网络中不存在增广路。 根据增广路定理，算法终止时的可行流是一个最大流。 步骤0：构造初始预流flow： 对源顶点s的每条出边(s,v)令flow(s,v)=cap(s,v)； 对其余边(u,v)令flow(u,v)=0。构造一有效的高度函数h。 步骤1：如果残量网络中不存在活顶点，则计算结束，已经得到最大流； 否则转步骤2。 步骤2：在网络中选取活顶点v。 如果存在顶点v的出边为可推流边，则选取一条这样的可推流边，并沿此边推流。 否则令h(v) = min{h(w)+1 | (v,w)是当前残流网络中的边}，并转步骤1。 一般的预流推进算法并未给出如何选择活顶点和可推流边。 不同的选择策略导致不同的预流推进算法。 在基于顶点的预流推进算法中，选定一个活顶点后，算法沿该活顶点的所有推流边进行推流运算，直至无可推流边或该顶点的存变成0时为止。 3 算法的计算复杂性 基于顶点的预流推进算法用一个广义队列gQ存储当前活顶点集合。 广义队列可以是通常的FIFO队列，LIFO栈，随机化队列，随机化栈，或按各种优先级定义的优先队列。 算法的效率与广义优先队列的选择密切相关。 如果选用通常的FIFO队列，则在最坏情况下，预流推进算法求最大流所需的计算时间为O(mn2)，其中m和n分别为图G的边数和顶点数。 如果以顶点高度值为优先级，选用优先队列实现预流推进算法，则在最坏情况下，求最大流所需的计算时间为 这个算法也称为最高顶点标号预流推进算法。 近来已提出许多其它预流推进算法的实现策略，在最坏情况下算法所需的计算时间已接近O(mn)。 8.3 最小费用流问题 1 网络流的费用 在实际应用中，与网络流有关的问题，不仅涉及流量，而且还有费用的因素。 网络的每一条边(v,w