从入门到精通最小费用流的“zkw算法”.pdf

《从入门到精通最小费用流的“zkw算法”.pdf》由会员上传分享，免费在线阅读，更多相关内容在行业资料-天天文库。

1、从入门到精通最小费用流的”zkw算法“1.网络流的一些基本概念很多同学建立过网络流模型做题目，也学过了各种算法，但是对于基本的概念反而说不清楚。虽然不同的模型在具体叫法上可能不相同，但是不同叫法对应的思想是一致的。下面的讨论力求规范,个别地方可能需要对通常的叫法加以澄清。求解可行流：给定一个网络流图，初始时每个节点不一定平衡（每个节点可以有盈余或不足），每条边的流量可以有上下界，每条边的当前流量可以不满足上下界约束。可行流求解中没有源和汇的概念，算法的目的是寻找一个可以使所有节点都能平衡，所有边都能满足流量约束的方案，同时可能附加有最小费用的条件（最小费用可行

2、流）。求解最大流：给定一个网络流图，其中有两个特殊的节点称为源和汇。除源和汇之外，给定的每个节点一定平衡。源可以产生无限大的流量，汇可以吸收无限大的流量。标准的最大流模型，初始解一定是可行的（例如，所有边流量均为零），因此边上不能有下界。算法的目的是寻找一个从源到汇流量最大的方案，同时不破坏可行约束，并可能附加有最小费用的条件（最小费用最大流）。扩展的最大流：在有上下界或有节点盈余的网络流图中求解最大流。实际上包括两部分，先是消除下界，消除盈余，可能还需要消除不满足最优条件的流量（最小费用流），找到一个可行流，再进一步得到最大流。因此这里我们的转化似乎是从最大

3、流转化为可行流再变回最大流，但其实质是将一个过程（扩展的最大流）变为了两个过程（可行流+最大流）。以上概念同时适用于最小费用流。2.最小费用流的各种转化不少同学认为消圈算法比增广路算法使用面广，可以有负边，负圈，每个点都能有盈余亏空等等。实际上增广路算法也一样可以有负边，负圈，上下界等等，且一般来说速度快于消圈算法。以下讨论中为盈余量，为费用，为容量。1.最小费用（可行）流最小费用最大流建立超级源和超级汇，对顶点，若，添加边，，，若添加边，，，之后求从到的最小费用最大流，如果流量等于，就存在可行流，残量网络已在原图上求出。2.最小费用最大流最小费用（可行）流连

4、边，，，所有点有，然后直接求。3.最小费用（可行）流中负权边的消除直接将负权边满流。4.最小费用最大流中负权边的消除先连边，，，使用（3.）中的方法消除负权边，使用（1.）中的方法求出最小费用（可行）流，之后距离标号不变，再求最小费用最大流；注意此时增广费用不能机械使用源点的标号——应该是源点汇点标号之差。3.费用流中的负边和负圈3.费用流中的负边和负圈在费用流的求解中难免会遇到负边和负圈的问题。对于消圈算法，负圈就是算法本身的一部分；但对于增广路算法，负圈是我们所不愿意看到的。鉴于竞赛中使用消圈算法将带来严重的效率问题，我们必须探索使用增广路算法处理费用流负

5、边和负圈的方法。对于单纯的负边，如果这些负边没有组成负圈，可以使用重赋权技术来处理，即通过对每个节点合适的顶标，使得ReducedCost非负。这个顶标通常可以使用到汇点的距离，修改之后的边权变为。根据流量平衡条件，容易根据这个新的费用算出原费用，同时可以证明这样的重赋权不改变最优解。这样做的代价是一次SPFA操作，时间耗费是相对较小的。如果存在负圈，SPFA算法将不会终止。很多同学使用人为的限制条件使其终止，这是错误的。举一个例子：源点和汇点均为孤立点，图中另外存在一个负费用，正容量的圈。不管怎样初始标号，仅凭增广无法消除这个负圈，从而得不到最优解（根据最小

6、费用最大流的定义，要在所有最大流（流量都为0）中寻找一个费用最小的方案）。也许你会说这个例子太过极端，但是也很容易构造出其他一些例子，说明不处理负圈，或者简单地对算法打补丁并不能解决本质问题。解决方法就是将所有负费用的边强制满流，称为“退流”操作。这样做之后我们破坏了平衡条件，但满足了最优条件。之后我们可以先求可行流，再求最大流，其间一直维持最优条件，并逐步解决平衡条件，最大流条件等问题。这也就是(2.)中提到的方法。这个方法可以消除所有负权边（在ReducedCost意义下），同时正确处理所有负圈问题。那么，这个方法的速度如何呢?费用流相关的图大致可以分为两

7、类，一类图侧重于费用，即总的流量不大，如TwoShortest（只有2），KaKa'sMatrixTravels等。较为通用的强制满流方法在这类图上表现不佳，原因是原本的流量较小而负费用较多，经过转化的图在可行流求解阶段流量与原流量相比很大，严重影响速度。另一方面，这类图往往有深刻的最短路背景，从而不会出现负圈，可以使用SPFA重赋权。另一类图侧重于流量，即边的费用相差不大，如employee，最优图像的求解。这种图中流量不小而负费用相对有限（也可以稍大，关键是前者），经过转化增加的流量可以很快完成计算，因此强制满流方法就没有问题。另外，不同的建图方式有可能造

8、成不同的模型。在employee这道题