【人人都要學算法】網絡流算法遠比你想的要好玩
這個問題的由來是想起來明天將會有國足世預賽的比賽，于是今天去看了看國足目前在小組中的積分。在積分榜中，我們可以看到與中國同組的馬爾代夫和不 丹都已經沒有了出線的機會，即使他們剩余的比賽全勝也不可能出線了。我在想，有沒有一個通用的方法，可以算出各支隊還有沒有出現的可能。
</blockquote>
====
現在我們來回歸正題：
網絡流(network-flows)是一種類比水流的解決問題方法，與線性規劃密切相關。網絡流的理論和應用在不斷發展，出現了具有增益的流、多 終端流、多商品流以及網絡流的分解與合成等新課題。網絡流的應用已遍及通訊、運輸、電力、工程規劃、任務分派、設備更新以及計算機輔助設計等眾多領域。
</blockquote>其實網絡流沒有那么復雜，我們來用交通網示意圖來舉個例子：
我們來看這個交通網示意圖，假設 S 為入口，T 為出口，圖中的單向箭頭表示從一個地方到另一個地方的可允許通過的方向，箭頭上的數字表示該路線所能承載的最大的車流量（例如：a,b 兩點，只能從 a 地到 b 地，并且該路線同時只能有4輛車同時通過）
我們需要解決的一個問題是如何安排好車的流量，例如現在有6輛車進入入口，我們可以如下圖這樣安排車的流量：
從圖中我們可以看出來各個路線的最大承載量與當前的車流量，如上圖的情況，我們說它是安全的。只要每一個地點它的駛入量與駛出量是相等的，我們就可以說它是安全的。另外，對于這個問題，我們會發現有的路線會是一個環（a->b->c->a）,我們暫且不考慮這個問題，我們只關注當前的交通系統是安全的，至于有的車可能一直在繞圈圈我們不會去考慮。
現在又出現了一個新的問題：現在的交通實際車流量并沒有達到最大，似乎還能增大 S 點的駛入量，這時我們可以再尋找一條從 S 到 T 的路經：S->a->b->c->T。把每條路徑的實際流量加1，我們會發現情況依舊是安全的，此時的駛入量為7：
現在實際交通流量達到最大了嗎？這次好像沒有那么容易看出來了。我們來看一下這條路經：S->b->a->c->T,我們 看到這條路經并不是完全順著我們的路線的，只有 S->b 和 c->T 是順著路線的，b->a 和 a->c 是逆著路線的。我們把順著的路線流量都+1，把逆著的路線流量都-1，我們得到了下面的圖：
此時，我們看這個圖，它依舊是安全的，并且流量增加了1，現在駛入量是8。
現在我們得到了兩種方式可以增大網絡流流量的方法：
- 從 S -> T 尋找一條路徑，每一條的子路徑的承載量都未滿，我們可以通過該路徑增加流量。
- 從 S -> T 尋找一條路徑，順著方向的路徑流量能+1（未滿），逆著方向的路徑流量能-1（非空），我們也可以通過該路徑來增大流量。
</ul>我們把這兩種路徑叫做增廣路徑 ，如果我們不能在圖中找到任何增廣路徑，那么我們就說它以及達到了最大流量。
====
現在，我們想想如何用網絡流的模型來解決一支隊是否有奪得第一名的可能。
現在我們來假設一種比賽，共有若干支隊伍，互相之間要進行多場比賽，其中的5只隊伍勝負情況如下表（其中 A 為聯賽第一名，E 為聯賽最后一名）：
TEAM 勝 負 剩余 </tr> </tbody>A 75 59 28 </tr>B 72 62 28 </tr>C 69 66 27 </tr>D 60 75 27 </tr>E 49 86 27 </tr> </tbody> </table>剩余比賽的狀況如下表：
TEAM A B C D E </tr> </tbody>A 0 3 8 7 3 </tr>B 3 0 2 7 4 </tr>C 8 2 0 0 0 </tr>D 7 7 0 0 0 </tr>E 3 4 0 0 0 </tr> </tbody> </table>我們現在考慮 E 隊還有沒有機會奪冠，也就是說在最好的情況下 E 能不能奪得第一名，即在剩下的比賽中 E 獲得全勝。
現在我們考慮 E 如何才能奪得冠軍，我們可以看到 E 還剩下27場比賽，如果它全勝的話，最后的勝局數量將會是49+27=76，那么也就是說，若使 E 保留奪冠可能，A 最多還能贏1場，B 最多還能贏4場，C 最多能贏7場，D 最多能贏16場。
現在我們來看看賽程，A、B 直接還有3場比賽，A、C 之間還有8場比賽，A、D 之間還有7場比賽，B、C 之間還有2場比賽，B、D之間還有7場比賽
我們把上述情況總結成一個網絡流圖：
我們來解釋下這一個圖：
從 S 點出發的路線表示某兩只隊之間的剩余比賽數，到 T 點的路線表示某隊最多能贏的場數。例如，我們設置了一個 A-B 結點，然后從 S 引出一條道路指向這個結點，并將其最大流量設定為 3 ；再從這個結點出發，引出兩條道路，分別指向 A 和 B ，其最大流量可以均設為 3 ，或者任意比 3 大的值（一般設為無窮大，以表示無需限制）。因而，在一個網絡流中，結點 A-B 將會從源點 S 處獲得最多 3 個單位的流量，并將所得的流量再分給結點 A 和結點 B 。如果把每個單位的流量理解成一個一個的勝局，那么網絡流也就可以理解為這些勝局的來源和去向。類似的我們有 A-B,A-C,A-D,B-C,B-D 五個結點。因此這個圖中的任意一個合法的網絡流都表示一種比賽結果
因此，現在如果我們能使該圖的最大流量到達27，那么我們就可以合理的安排比賽，使得每支隊伍都不超過所能允許的最多生理場次。
現在圖中的最大流量是26，我們看看還能不能增加一個流量，即找到一個增廣路徑（圖中 n 表示無窮大）：
很顯然，我們在圖中找不到另外的增廣路徑了，因此該圖的最大流量為26，因此，E 隊不論多么努力，他們都將會與冠軍無緣~。
</div>
來自：http:/www. nhang.com/2015/11/17/【人人都要學算法】網絡流算法遠比你想的要好玩/本文由用戶 jopen 自行上傳分享，僅供網友學習交流。所有權歸原作者，若您的權利被侵害，請聯系管理員。轉載本站原創文章，請注明出處，并保留原始鏈接、圖片水印。本站是一個以用戶分享為主的開源技術平臺，歡迎各類分享！相關經驗
sesese色