最小費用最大流問題

在圖論中，網(wǎng)絡(luò)流（英語：Network flow）是指在一個每條邊都有容量（capacity）的有向圖分配流，使一條邊的流量不會超過它的容量。通常在運籌學(xué)中，有向圖稱為網(wǎng)絡(luò)。頂點稱為節(jié)點（node）而邊稱為弧（arc）。一道流必須匹配一個結(jié)點的進出的流量相同的限制，除非這是一個源點（source）──有較多向外的流，或是一個匯點（sink）──有較多向內(nèi)的流。一個網(wǎng)絡(luò)可以用來模擬道路系統(tǒng)的交通量、管中的液體、電路中的電流或類似一些東西在一個結(jié)點的網(wǎng)絡(luò)中游動的任何事物。

• 網(wǎng)絡(luò)流

最小費用最大流問題是經(jīng)濟學(xué)和管理學(xué)中的一類典型問題。在一個網(wǎng)絡(luò)中每段路徑都有“容量”和“費用”兩個限制的條件下，此類問題的研究試圖尋找出：流量從A到B，如何選擇路徑、分配經(jīng)過路徑的流量，可以達到所用的費用最小的要求。

在實際中：n輛卡車要運送物品，從A地到B地。由于每條路段都有不同的路費要繳納，每條路能容納的車的數(shù)量有限制，如何分配卡車的出發(fā)路徑可以達到費用最低，物品又能全部送到。

解決最小費用最大流問題，一般有兩條途徑。一條途徑是先用最大流算法算出最大流，然后根據(jù)邊費用，檢查是否有可能在流量平衡的前提下通過調(diào)整邊流量，使總費用得以減少？只要有這個可能，就進行這樣的調(diào)整。調(diào)整后，得到一個新的最大流。

然后，在這個新流的基礎(chǔ)上繼續(xù)檢查，調(diào)整。這樣迭代下去，直至無調(diào)整可能，便得到最小費用最大流。這一思路的特點是保持問題的可行性（始終保持最大流），向最優(yōu)推進。另一條解決途徑和前面介紹的最大流算法思路相類似，一般首先給出零流作為初始流。這個流的費用為零，當然是最小費用的。然后尋找一條源點至匯點的增流鏈，但要求這條增流鏈必須是所有增流鏈中費用最小的一條。如果能找出增流鏈，則在增流鏈上增流，得出新流。將這個流做為初始流看待，繼續(xù)尋找增流鏈增流。這樣迭代下去，直至找不出增流鏈，這時的流即為最小費用最大流。這一算法思路的特點是保持解的最優(yōu)性（每次得到的新流都是費用最小的流），而逐漸向可行解靠近（直至最大流時才是一個可行解）。

由于第二種算法和已介紹的最大流算法接近，且算法中尋找最小費用增流鏈，可以轉(zhuǎn)化為一個尋求源點至匯點的最短路徑問題，所以這里介紹這一算法。

在這一算法中，為了尋求最小費用的增流鏈，對每一當前流，需建立伴隨這一網(wǎng)絡(luò)流的增流網(wǎng)絡(luò)。例如圖 1 網(wǎng)絡(luò)G 是具有最小 費用的流，邊旁參數(shù)為c(e),f(e),w(e），而圖 2 即為該網(wǎng)絡(luò)流 的增流網(wǎng)絡(luò)G′。增流網(wǎng)絡(luò)的頂點和原網(wǎng)絡(luò)相同。按以下原則建 立增流網(wǎng)絡(luò)的邊：若G中邊（u，v）流量未飽，即f(u,v) < e(u,v），則G ' 中建邊（u,v），賦權(quán)w ' (u,v)=w(u,v）；若G中邊（u,v）已有流量，即f(u,v）〉0，則G′中建邊（v,u），賦權(quán)w′（v,u) =-w(u,v）。建立增流網(wǎng)絡(luò)后，即可在此網(wǎng)絡(luò)上求源點至匯點的最短路徑，以此決定增流路徑，然后在原網(wǎng)絡(luò)上循此路徑增流。這里，運用的仍然是最大流算法的增流原理，唯必須選定最小費用的增流鏈增流。

計算中有一個問題需要解決。這就是增流網(wǎng)絡(luò)G ′中有負權(quán)邊，因而不能直接應(yīng)用標號法來尋找x至y的最短路徑，采用其它計算有負權(quán)邊的網(wǎng)絡(luò)最短路徑的方法來尋找x至y的最短路徑，將 大大降低計算效率。為了仍然采用標號法計算最短路徑，在每次建立增流網(wǎng)絡(luò)求得最短路徑后，可將網(wǎng)絡(luò)G的權(quán)w(e）做一次修正，使再建的增流網(wǎng)絡(luò)不會出現(xiàn)負權(quán)邊，并保證最短路徑不至于因此而改變。下面介紹這種修改方法。當流值為零，第一次建增流網(wǎng)絡(luò)求最短路徑時，因無負權(quán)邊，當然可以采用標號法進行計算。為了使以后建立增流網(wǎng)絡(luò)時不出現(xiàn)負權(quán)邊，采取的辦法是將 G中有流邊（f(e)>0）的權(quán)w(e）修正為0。為此， 每次在增流網(wǎng)絡(luò)上求得最短路徑后，以下式計算G中新的邊權(quán)w " (u,v）：

w " (u,v)=L(u)-L(v) w(u,v) (*)

式中 L(u),L(v) -- 計算G′的x至y最短路徑時u和v的標號值。第一次求最短徑時如果（u,v）是增流路徑上的邊， 則據(jù)最短 路徑算法一定有 L(v)=L(u) w ' (u,v)=L(u) w(u,v）， 代入（*）式必有

w″（u,v)=0。

如果（u,v）不是增流路徑上的邊，則一定有：

L(v）≤L(u) w(u,v）， 代入（*）式則有 w(u,v）≥0。

可見第一次修正w(e）后，對任一邊，皆有w(e）≥0， 且有流 的邊（增流鏈上的邊），一定有w(e)=0。以后每次迭代計算，若 f(u,v)>0，增流網(wǎng)絡(luò)需建立（v,u）邊，邊權(quán)數(shù)w ' (v,u)=-w(u,v) =0，即不會再出現(xiàn)負權(quán)邊。 此外，每次迭代計算用（*）式修正一切w(e）， 不難證明對每一條x至y的路徑而言，其路徑長度都同樣增加L(x)-L(y）。因此，x至y的最短路徑不會因?qū)(e）的修正而發(fā)生變化。

【計算步驟】

⒈ 對網(wǎng)絡(luò)G=[V,E,C,W]，給出流值為零的初始流。

⒉ 作伴隨這個流的增流網(wǎng)絡(luò)G′=[V′，E′，W′]。G′的頂點同G：V′=V。若G中f(u,v)0，則G′中建邊（v,u），w′（v,u)=-w(u,v）。

⒊ 若G′不存在x至y的路徑，則G的流即為最小費用最大流， 停止計算；否則用標號法找出x至y的最短路徑P。

⒋ 根據(jù)P，在G上增流：對P的每條邊（u,v），若G存在（u,v），則（u,v）增流；若G存在（v,u），則（v,u）減流。增（減）流后，應(yīng)保證對任一邊有c(e）≥ f(e）≥0。

⒌ 根據(jù)計算最短路徑時的各頂點的標號值L(v），按下式修 改G一切邊的權(quán)數(shù)w(e):

L(u)-L(v) w(e）→w(e）。

⒍ 將新流視為初始流，轉(zhuǎn)2。

由割集的定義不難看出，無論拿掉那個割集，發(fā)點v_s到收點v_t便不再相通，所以任何一個可行流都會經(jīng)過割集，且不會超過任一割集的容量。最小割如同瓶頸一般，即使是最大流也無法超過最小割，網(wǎng)絡(luò)的最大流與最小割容量滿足下面的定理（證明略）。

最大流問題定理一

設(shè)f為網(wǎng)絡(luò)G=(V,E,C)的任一可行流，流量為v(f)，

最大流問題定理二

由定理一可知，最大流的流量v(f)和某一割集K的容量相等，而且最大流的流量本身也不帶任一割集的容量，因此割集一定是最小的割集。

任一網(wǎng)絡(luò)G中，從v_s到v_t的最大流的流量等于分離v_s、v_t的最小割的容量（最小的割集的容量）。

最大流問題前后向弧

一條從起點v_s到終點vt的鏈μ，規(guī)定從v_s到v_t的方向為鏈μ的方向，鏈上與μ方向一致的邊叫前向弧（邊），記作μ^-；與μ方向相反的邊稱為后向?。ㄟ叄涀鳓?sup class="normal"> 。

最大流問題可增廣鏈

f是一個可行流，f_ij表示由i點指向j點的流量，如果滿足前向弧的流量非負且小于容量，或后向弧的流量大于0且不超過容量：

則稱μ為從v_s到v_t的關(guān)于f的可增廣鏈。

可增廣鏈的實際意義是：沿著這條從v_s到v_t輸送的流，仍有潛力可挖，只要前向弧的流量增加或后向弧的流量減少，就可以將截集的流量提高。調(diào)整后的流，在各點仍滿足平衡條件及容量限制條件，仍為可行流。

從另一個角度來說，可以提高流量的可行流也不是最大流，因此可行流f是最大流的充要條件是不存在從v_s到v_t的可增廣鏈。

augmentpath

譯為“增廣路”算法，其思想大致如下：

原有網(wǎng)絡(luò)為G，設(shè)有一輔助圖G'，其定義為V(G') = V(G），E(G'）初始值（也就是容量）與E(G）相同。每次操作時從Source點搜索出一條到Sink點的路徑，然后將該路徑上所有的容量減去該路徑上容量的最小值，然后對路徑上每一條邊；添加或擴大反方向的容量，大小就是剛才減去的容量。一直到?jīng)]有路為止。此時輔助圖上的正向流就是最大流。

我們很容易覺得這個算法會陷入死循環(huán)，但事實上不是這樣的。我們只需要注意到每次網(wǎng)絡(luò)中由Source到Sink的流都增加了，若容量都是整數(shù)，則這個算法必然會結(jié)束。

尋找通路的時候可以用DFS，BFS最短路等算法。就這兩者來說，BFS要比DFS快得多，但是編碼量也會相應(yīng)上增加。

增廣路方法可以解決最大流問題，然而它有一個不可避免的缺陷，就是在極端情況下每次只能將流擴大1（假設(shè)容量、流為整數(shù)），這樣會造成性能上的很大問題，解決這個問題有一個復(fù)雜得多的算法，就是預(yù)推進算法。

pushlabel

譯為“預(yù)流推進”算法。

可以想象在一個自來水管網(wǎng)的源頭盡可能多的注入水流之后，最多有多少水可以流到匯點去，由網(wǎng)絡(luò)的各個節(jié)點和管道來約束流量。將每個節(jié)點都看成一個水站，他的通過能力是有限的不能通過的水只能退回去。

Push-Relabel

譯為壓入與重標記算法

除了用各種方法在剩余網(wǎng)絡(luò)中不斷找增廣路（augmenting）的Ford-Fulkerson系的算法外，還有一種求最大流的算法被稱為壓入與重標記（Push-Relabel）算法。它的基本操作有：壓入，作用于一條邊，將邊的始點的預(yù)流盡可能多的壓向終點；重標記，作用于一個點，將它的高度（也就是label）設(shè)為所有鄰接點的高度的最小值加一。Push-Relabel系的算法普遍要比Ford-Fulkerson系的算法快，但是缺點是相對難以理解。

Relabel-to-Front使用一個鏈表保存溢出頂點，用Discharge操作不斷使溢出頂點不再溢出。

Discharge的操作過程是：若找不到可被壓入的臨邊，則重標記，否則對臨邊壓入，直至點不再溢出。

算法的主過程是：首先將源點出發(fā)的所有邊充滿，然后將除源和匯外的所有頂點保存在一個鏈表里，從鏈表頭開始進行Discharge，如果完成后頂點的高度有所增加，則將這個頂點置于鏈表的頭部，對下一個頂點開始Discharge。

Relabel-to-Front算法的時間復(fù)雜度是O(V^3），還有一個叫Highest Label Preflow Push的算法復(fù)雜度據(jù)說是O(V^2*E^0.5）。我研究了一下HLPP，感覺它和Relabel-to-Front本質(zhì)上沒有區(qū)別，因為Relabel-to-Front每次前移的都是高度最高的頂點，所以也相當于每次選擇最高的標號進行更新。還有一個感覺也會很好實現(xiàn)的算法是使用隊列維護溢出頂點，每次對pop出來的頂點discharge，出現(xiàn)了新的溢出頂點時入隊。

Push-Relabel類的算法有一個名為gap heuristic的優(yōu)化，就是當存在一個整數(shù)0k的頂點v做更新，若它小于V 1就置為V 1。

c 程序舉例

typedef pair P;

struct edge { int to,cap,cost,rev; };

int V;

vector G[MAX_V];

int h[MAX_V];

int dist[MAX_V];

int prevv[MAX_V],preve[MAX_V];

void add_edge(int from,int to,int cap,int cost) {

G[from].push_back((edge){to,cap,cost,G[to].size()});

G[to].push_back((edge){from,0,-cost,G[from].size()-1});

}

int min_cost_flow(int s,int t,int f) {

int res;

fill(h,h V,0);

while(f>0) {

priority_queue ,greater

> que;

fill(dist,dist V,INF);

dist[s]=0;

que.push(P(0,s));

while(!que.empty()) {

P p=que.top();que.pop();

int v=p.second;

if(dist[v]

if(e.cap>0&&dist[e.to]>dist[v] e.cost h[v]-h[e.to]) {

dist[e.to]=dist[v] e.cost h[v]-h[e.to];

prevv[e.to]=v;

preve[e.to]=i;

que.push(P(dist[e.to],e.to));

}

}

}

if(dist[t]==INF) return -1;

for(int v=0;v

for(int v=t;v!=s;v=prevv[v])

d=min(d,G[prevv[v]][preve[v]].cap);

f-=d;

res =d*h[t];

for(int v=t;v!=s;v=prevv[v]) {

edge &e=G[prevv[v]][preve[v]];

e.cap-=d;

G[v][e.rev].cap =d;

}

}

return res;

}2100433B