問題12 最大流量

在高速公路網(wǎng)中有車流，在互聯(lián)網(wǎng)上有信息流，在自來水管網(wǎng)中有水流，在公用電網(wǎng)中有電流。。。網(wǎng)絡(luò)大都和某種流聯(lián)系在一起，網(wǎng)絡(luò)的作用就是要保障那些流的通暢。對于網(wǎng)絡(luò)中流量的研究是一個具有普遍意義的主題。

研究網(wǎng)絡(luò)中的流問題可有多個不同的視角和目標(biāo)追求。

本章作者介紹的是兩個節(jié)點(diǎn)之間可能經(jīng)過的最大流量。

為了讓讀者能夠理解，首先介紹了一個只有三個節(jié)點(diǎn)的有向帶權(quán)網(wǎng)絡(luò)（圖）。

然后介紹一個有四個節(jié)點(diǎn)的有向帶權(quán)圖。

通過兩個實(shí)例的介紹，讀者可以慢慢體會到這個問題的挑戰(zhàn)之處了。

?

然后，本章詳細(xì)介紹了經(jīng)典Ford-Fulkerson算法（1956年發(fā)明），從方法的動機(jī)，基本的思路，算法執(zhí)行舉例，給出了一種算法描述后，簡略討論了算法為什么會結(jié)束、為什么可以求出最優(yōu)解，運(yùn)行效率，算法的適用性等問題。

?

【作者感受】

最大流問題就是在容量網(wǎng)絡(luò)中，尋找流量最大的可行流。它是一種組合最優(yōu)化問題，一個特殊的線性規(guī)劃問題，所以它的應(yīng)用場景是很多的，涉及很多熱門領(lǐng)域，如運(yùn)籌學(xué)。所以，求解最大流問題的算法有很多的。

?

我個人認(rèn)為，最大流問題是算法學(xué)習(xí)的一個分水嶺，因?yàn)橐獙W(xué)習(xí)并基本理解，并能夠真的能夠應(yīng)用的好，是需要相當(dāng)高的水平，很多計算機(jī)專業(yè)的學(xué)生都不明白，甚至都沒學(xué)過（因?yàn)楹芏嗨惴ㄕn程都不講）

?

當(dāng)然，在一些經(jīng)典的應(yīng)用領(lǐng)域中，有工具提供最大流的方法，或者有高手已經(jīng)實(shí)現(xiàn)好了最大流的程序，用就是了。