在大規(guī)模戰(zhàn)爭(zhēng)中，后勤補(bǔ)給是重中之重，為了盡最大可能滿(mǎn)足前線的物資消耗，后勤部隊(duì)必然要充分利用每條運(yùn)輸網(wǎng)。與此同時(shí)，交戰(zhàn)雙方也想要以最小的代價(jià)切斷敵軍的補(bǔ)給，從而使敵軍處于孤立無(wú)援的境地。在古今中外的各種重大戰(zhàn)役中，上演了一幕幕補(bǔ)給線上的攻防戰(zhàn)。

甲軍的運(yùn)輸路線

　　假設(shè)甲、乙兩軍正在交戰(zhàn)，圖8.17是甲軍的補(bǔ)給運(yùn)輸網(wǎng)，其中t是甲軍的前沿陣地，s是后勤大營(yíng)，每條邊是一條公路，邊上的數(shù)字代表公路的寬度。

　　如果甲軍想要盡最大努力供應(yīng)前線的消耗，應(yīng)該怎樣設(shè)計(jì)運(yùn)輸路線？

　　這個(gè)問(wèn)題很容易規(guī)約成網(wǎng)絡(luò)流模型，使用下面的代碼可以直接計(jì)算出結(jié)果。

1 import network_flow as nf 2 3 V = [0, 1, 2, 3, 4, 5, 6, 7, 8] 4 E = [nf.Edge(0, 1, 15), nf.Edge(0, 2, 15), nf.Edge(0, 3, 15), nf.Edge(1, 4, 2), nf.Edge(2, 4, 3), 5 nf.Edge(2, 5, 2), nf.Edge(3, 5, 4), nf.Edge(4, 5, 2), nf.Edge(4, 6, 2), nf.Edge(5, 6, 4), 6 nf.Edge(5, 7, 3), nf.Edge(6, 8, 15), nf.Edge(7, 8, 15)] 7 s, t = 0, 8 8 G = nf.Network(V, E, s, t) 9 ford_fullkerson = nf.FordFulkerson(G) 10 ford_fullkerson.start() 11 ford_fullkerson.display() 12 X, Y, st_cut = ford_fullkerson.min_st_cut() 13 ford_fullkerson.display_st_cut(X, Y, st_cut)

　　（network_flow參考上一章的相關(guān)代碼）運(yùn)行結(jié)果對(duì)應(yīng)的網(wǎng)絡(luò)流：

乙軍的轟炸目標(biāo)

　　甲軍想要充分利用每條公路，乙軍的目的正好相反，是破壞公路網(wǎng)，使乙軍的戰(zhàn)斗部隊(duì)處于孤立無(wú)援的境地。乙軍打算組織一次針對(duì)甲軍補(bǔ)給線的戰(zhàn)略轟炸，由于甲軍在每個(gè)節(jié)點(diǎn)都部署了大量防空武器，因此需要繞過(guò)節(jié)點(diǎn)，直接轟炸防御薄弱的公路。假設(shè)炸掉容量為1的公路需要n顆炸彈，破壞的公路容量和投擲的炸彈數(shù)成正比，怎樣設(shè)計(jì)轟炸目標(biāo)才能以最小的代價(jià)完全破壞敵軍的補(bǔ)給線？

　　一個(gè)方案是炸毀直接通向匯點(diǎn)的公路，但由于連接匯點(diǎn)的兩條公路太寬，完全破壞需要30n的炸彈，這顯然不是最小代價(jià)。如果換個(gè)地點(diǎn)，假設(shè)轟炸的是v₅→v₇，那么只需要3n的炸彈就可以使寬敞的v₇→t淪為擺設(shè)。為了設(shè)計(jì)這種轟炸方案，需要理解最小st-剪切的概念。

8.3.3 最小st-剪切

　　設(shè)計(jì)成本最低的轟炸方案是我們的目標(biāo)，直接尋找起來(lái)比較困難，幸而這個(gè)目標(biāo)與網(wǎng)絡(luò)的最小剪切有密切關(guān)系。

　　一個(gè)流網(wǎng)絡(luò)的頂點(diǎn)可以劃分成兩個(gè)不相交的集合X和Y，源點(diǎn)s和匯點(diǎn)t分屬于這兩個(gè)集合，連接X(jué)和Y的邊稱(chēng)為這個(gè)流網(wǎng)絡(luò)的st-剪切（st-cut，也稱(chēng)為截、割或切割）。我們用淺色圓圈表示包含源點(diǎn)的集合X，深色圓圈表示包含匯點(diǎn)的集合Y，這樣就很容易看出一個(gè)流網(wǎng)絡(luò)的st-剪切：

　　既然st-剪切是邊的集合，那么集合中邊的容量之和就是st-剪切的容量。一個(gè)流網(wǎng)絡(luò)有很多種不同的st-剪切，其中容量最小的一個(gè)就是最小st-剪切。

　　st-剪切包含了所有源點(diǎn)到匯點(diǎn)的通道，一個(gè)顯而易見(jiàn)的結(jié)論是：st-剪切的流值等于這個(gè)網(wǎng)絡(luò)流的值。更進(jìn)一步，任何網(wǎng)絡(luò)流的值都不會(huì)超過(guò)st-剪切的容量，這也意味著st-剪切代表著流網(wǎng)絡(luò)的瓶頸，最小st-剪切的容量不會(huì)小于最大流的值，這個(gè)定理稱(chēng)為最大流-最小剪切定理。該定理也可以反過(guò)來(lái)表述：網(wǎng)絡(luò)流的值最大不會(huì)大于任意一個(gè)給定的st-剪切的容量。當(dāng)X只包含源點(diǎn)或Y只包含匯點(diǎn)時(shí)，最大流-最小剪切定理最為直觀。

　　最小st-剪切代表補(bǔ)給線上最難走或最重要的路段，只要破壞這些路段，就能以最小的代價(jià)掐斷敵軍的補(bǔ)給，即使只破壞了一部分，也能有效降低敵軍的補(bǔ)給能力。既然最小st-剪切和最大流存在關(guān)聯(lián)關(guān)系，我們就可以在尋找最大流時(shí)順帶找出最小st-剪切，這仍然需要使用殘存網(wǎng)。在殘存網(wǎng)中，將源點(diǎn)和從源點(diǎn)出發(fā)可以到達(dá)的頂點(diǎn)看作集合X，剩下的頂點(diǎn)看作集合Y，對(duì)于邊v→w，如果滿(mǎn)足v屬于X，w屬于Y，那么v→w就是最小st-剪切中的一條邊。

　　以下圖為例，在殘存網(wǎng)中源點(diǎn)能夠到達(dá)的頂點(diǎn)只有v₃，原網(wǎng)絡(luò)的最小st-剪切是：

　　可以根據(jù)這種思路在FordFulkerson中添加尋找最小st-剪切的實(shí)現(xiàn)。

1 class FordFulkerson(): 2 def __init__(self, G:Network): 3 self.G = G 4 self.max_flow = 0 # 最大流 5 …… （省略部分參考上一章的相關(guān)代碼） 6 def min_st_cut(self): 7 ''' 找到最小st-剪切 ''' 8 X = [self.G.s] # st-剪切的X集合 9 stack = [self.G.s] 10 while len(stack) > 0: 11 v = stack.pop() 12 for e in self.G.edges_from(v): # 所有從v頂點(diǎn)流出的邊 13 if e.w != self.G.t and e.w not in X and e.residual_cap_to(e.w) > 0: 14 X.append(e.w) 15 stack.append(e.w) 16 Y = list(set(self.G.V) - set(X)) # st-剪切的X集合 17 st_cut = [e for e in self.G.E if e.v in X and e.w in Y] # 連接X(jué)和Y的邊 18 return X, Y, st_cut 19 20 def display_st_cut(self, X, Y, st_cut): 21 print('X={0}, Y={1}'.format(X, Y)) 22 print('st-cut={}'.format([str(e) for e in st_cut]))

　　min_st_cut使用深度優(yōu)先搜索尋找最小st-剪切。由于這種方法需要借助殘存網(wǎng)，因此在使用min_st_cut前需要首先執(zhí)行一次計(jì)算最大流的操作。現(xiàn)在可以計(jì)算出乙軍的轟炸目標(biāo)了：

姜子牙的押糧官

　　在《封神演義》中，姜子牙經(jīng)過(guò)金臺(tái)拜將之后，擔(dān)任“掃蕩成湯天寶大元帥”一職，代武王伐紂。率領(lǐng)六十萬(wàn)西岐大軍浩浩蕩蕩，東進(jìn)朝歌。所謂“三軍未動(dòng)，糧草先行”，在臨行前，姜子牙任命了四個(gè)先鋒官的同時(shí)，又任命了楊戩、土行孫、鄭倫三個(gè)押糧官。

　　押糧前必先征糧，單從一個(gè)地方征糧恐怕不足以支持一場(chǎng)滅國(guó)戰(zhàn)爭(zhēng)，假設(shè)下圖是西岐的糧道。

　　邊的容量代表糧道的運(yùn)力，楊戩、土行孫、鄭倫分別從三v₁、v₂、v₃個(gè)征糧地同時(shí)出發(fā)，將糧草運(yùn)往唯一的前沿陣地t，由于運(yùn)糧過(guò)程中十分安全，所以三人可以在每個(gè)節(jié)點(diǎn)處合兵或分兵，怎樣行進(jìn)才能使糧道發(fā)揮出最大運(yùn)力呢？

多個(gè)源點(diǎn)與多個(gè)匯點(diǎn)

　　問(wèn)題可以規(guī)約成典型的最大流問(wèn)題，但與之前介紹的st-網(wǎng)絡(luò)不同，糧道圖中有多個(gè)源點(diǎn)（或者說(shuō)沒(méi)有源點(diǎn)），如此一來(lái)將會(huì)對(duì)最大流的相關(guān)算法造成影響，怎么辦呢？

　　其實(shí)很簡(jiǎn)單，在三個(gè)源點(diǎn)前再加入一個(gè)超級(jí)源點(diǎn)，這樣一來(lái)v₁、v₂、v₃就變成了普通的節(jié)點(diǎn)，它們也符合守恒定律，原網(wǎng)絡(luò)也轉(zhuǎn)換成了st-網(wǎng)：

　　與此類(lèi)似，也可以通過(guò)建立一個(gè)超級(jí)匯點(diǎn)來(lái)處理多個(gè)匯點(diǎn)的情況。

糧道的最大運(yùn)力

　　有了超級(jí)節(jié)點(diǎn)后，只要把初始數(shù)據(jù)輸入交給計(jì)算機(jī)就可以了。

1 import network_flow as nf 2 3 V = [0, 1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12, 13] 4 E = [nf.Edge(0, 1, 18), nf.Edge(0, 2, 18), nf.Edge(0, 3, 18), nf.Edge(1, 4, 9), 5 nf.Edge(1, 5, 9), nf.Edge(2, 5, 9), nf.Edge(2, 6, 9), nf.Edge(3, 6, 9), 6 nf.Edge(3, 7, 9), nf.Edge(4, 8, 3), nf.Edge(4, 9, 12), nf.Edge(5, 9, 6), 7 nf.Edge(5, 10, 14), nf.Edge(6, 10, 7), nf.Edge(6, 11, 5), nf.Edge(7, 11, 10), 8 nf.Edge(7, 12, 12), nf.Edge(8, 13, 8), nf.Edge(9, 13, 8), nf.Edge(10, 13, 8), 9 nf.Edge(11, 13, 8), nf.Edge(12, 13, 8)] 10 s, t = 0, 13 11 G = nf.Network(V, E, s, t) 12 ford_fullkerson = nf.FordFulkerson(G) 13 ford_fullkerson.start() 14 ford_fullkerson.display()

　　最大流是33，下圖是根據(jù)程序運(yùn)行結(jié)果映射的網(wǎng)絡(luò)流。

　　最大流是確定的，但押糧路線并不是唯一的，最大流算法和邊的輸入順序都會(huì)對(duì)它產(chǎn)生影響。對(duì)于增廣路徑最大流算法來(lái)說(shuō)，尋找增廣路徑的算法也會(huì)影響最終的押糧路線。

　　

---

　　?作者：我是8位的

　　出處：http://www.cnblogs.com/bigmonkey

　　本文以學(xué)習(xí)、研究和分享為主，如需轉(zhuǎn)載，請(qǐng)聯(lián)系本人，標(biāo)明作者和出處，非商業(yè)用途！?

　　掃描二維碼關(guān)注公眾號(hào)“我是8位的”

轉(zhuǎn)載于:https://www.cnblogs.com/bigmonkey/p/11010891.html

與50位技術(shù)專(zhuān)家面對(duì)面20年技術(shù)見(jiàn)證，附贈(zèng)技術(shù)全景圖

總結(jié)

以上是生活随笔為你收集整理的网络流(3)——找到最小st-剪切的全部?jī)?nèi)容，希望文章能夠幫你解決所遇到的問(wèn)題。

如果覺(jué)得生活随笔網(wǎng)站內(nèi)容還不錯(cuò)，歡迎將生活随笔推薦給好友。