最大流算法在礦井通風(fēng)系統(tǒng)中的應(yīng)用

劉義磊，黃素果

畢節(jié)學(xué)院資源與安全工程學(xué)院，貴州畢節(jié) 551700

0 引言

在實(shí)際生產(chǎn)、生活過程當(dāng)中，真實(shí)網(wǎng)絡(luò)的結(jié)點(diǎn)和邊都是有容量限制的，我們一般需要知道這樣一個(gè)網(wǎng)絡(luò)中源和匯這兩個(gè)指定結(jié)點(diǎn)之間傳輸?shù)淖畲罅髁?，并找出達(dá)到這個(gè)最大流量的具體辦法，網(wǎng)絡(luò)最大流問題就是描個(gè)問題的數(shù)學(xué)模型。

礦井通風(fēng)系統(tǒng)設(shè)計(jì)所需的一個(gè)重要的主要參數(shù)就是礦井通風(fēng)所需最小風(fēng)量，它也是對(duì)各種分風(fēng)算法進(jìn)行選擇的前提條件。礦井通風(fēng)系統(tǒng)形成之后，礦井最小總風(fēng)量就是不受分風(fēng)算法影響的一個(gè)定值。但是由于風(fēng)速太大時(shí)會(huì)導(dǎo)致粉塵增多等現(xiàn)象，針對(duì)不同的巷道先頂了不同的風(fēng)速上限，因此對(duì)于通風(fēng)系統(tǒng)來說其最大風(fēng)量和最小風(fēng)量都是有限制的，最終都?xì)w結(jié)到網(wǎng)絡(luò)的極值流問題，其中重要的也就是最大流問題。

1 最大流算法

最大流問題是網(wǎng)絡(luò)流理論的核心問題之一，它牽涉到特殊的線性規(guī)劃，是一個(gè)經(jīng)典的優(yōu)化組合問題。通俗地講，最大流問題就是在網(wǎng)絡(luò)當(dāng)中以最快捷的辦法把特定物質(zhì)從某處輸送至另一處。該問題源于美蘇之間的爭(zhēng)端，美國(guó)想準(zhǔn)確獲得有關(guān)蘇聯(lián)能夠最快的獲得國(guó)際補(bǔ)給的鐵路線路，以及如何最大限度地切斷其補(bǔ)給線路。最終通過調(diào)查計(jì)算發(fā)現(xiàn)這兩個(gè)問題相互聯(lián)系，不可分割對(duì)待，并且最大流問題得到合理處理的同時(shí)，也解決了最徹底地切斷蘇聯(lián)補(bǔ)給的最小割問題。

最大流問題發(fā)展到今天，學(xué)者們建立了一系列較為完善的理論，也尋找出了許多的算法。如Ford-Fulkson算法、Dinic算法、Gold-berg推進(jìn)和重標(biāo)號(hào)算法以及Gold-berg和Rao的二分長(zhǎng)度阻塞流算法等等，這些經(jīng)典算法及相關(guān)技術(shù)對(duì)網(wǎng)絡(luò)最大流問題的研究起到了非常重要的推動(dòng)作用。

1.1 Ford-Fulkson增載軌算法和Dinic阻塞流算法

Ford-Fulkson算法第一次將組合優(yōu)化的方法應(yīng)用到最大流問題。初次將剩余網(wǎng)絡(luò)、增載軌等概念引入，把最大流問題的求解進(jìn)行歸納總結(jié)，成為從一個(gè)初值開始不斷遞增直到求得最優(yōu)解的迭代過程，打下了用組合方法進(jìn)行求解的基礎(chǔ)。

Ford-Fulkerson Algorithm可以概括為：Residual networks augmenting paths and cuts三大思想，最重要的一點(diǎn)的是利用Residue network的論點(diǎn)求解出maximum flow。

將最大流問題的求解過程當(dāng)做一個(gè)迭代的過程，每次迭代都是為了使網(wǎng)絡(luò)中的流量增大，那么如果想最大限度地減少計(jì)算量，那么只有想法設(shè)法將迭代次數(shù)減少，并且降低每一步的復(fù)雜程度。如果想將迭代次數(shù)降低，那么需要每次迭代時(shí)都要使網(wǎng)絡(luò)中的流量遞增程度盡可能的增大。比較方便的是找出網(wǎng)絡(luò)中的一部分作為子圖，然后求出該子圖中所需的最大流，最終在剩余的網(wǎng)絡(luò)里重復(fù)這一步驟。

Dinic算法首次將距離這一定義延伸到求解過程中來，它在網(wǎng)絡(luò)中定義出了分層網(wǎng)絡(luò)，這是一個(gè)非常獨(dú)特的無環(huán)網(wǎng)絡(luò)，分層網(wǎng)絡(luò)就是僅保留距離相鄰的結(jié)點(diǎn)之間的邊，然后在定義出的分層網(wǎng)絡(luò)中進(jìn)一步求阻塞流。

1.2 Push-relabel algorithms算法

Push-relabel algorithms算法的主要思路是在網(wǎng)絡(luò)中，流出的量可能比流進(jìn)的量還要多，有流量進(jìn)來就放其流入，流不出去時(shí)再做處理。Push-relabel algorithms算法的流程如下：

1）設(shè)定一個(gè)函數(shù)f(x)，它是一個(gè)高度函數(shù)，表示的意義是x點(diǎn)的高度，作為一個(gè)中間參考坐標(biāo)，只有比其高的點(diǎn)能往比其低的點(diǎn)流動(dòng)；

2）程序運(yùn)行時(shí)，設(shè)source node的高度是x(node數(shù))，除此之外的點(diǎn)的高度都是0，這樣source node就足以流往其它任何一個(gè)點(diǎn)；

3）然后讓source node往其它所有緊挨的node里都注入特定的流量，然后計(jì)算剩余網(wǎng)絡(luò)的狀態(tài)；

4）對(duì)每一個(gè)active node都重復(fù)Relabel的動(dòng)作，如果在其中某個(gè)node有流體存在，但是和它所相鄰的所有node的f(x)都高于它，這時(shí)要為它的f(x)增加一條可以流出去的支路；

5）然后對(duì)每一個(gè)能夠做Push動(dòng)作的node重復(fù)Push；

6）反復(fù)執(zhí)行Relabe和Push的工作，直到無任何active node，最后從source node流出的總的流量就是最大流量。

Push-relabel algorithms提供了最大流的新的思路，并且它的效率也非常的高，復(fù)雜度僅僅為O(V2E)，比一般的算法占有一定的優(yōu)勢(shì)。

2 求解最大流的通路法在礦井通風(fēng)系統(tǒng)中的應(yīng)用

已知某礦井的通風(fēng)網(wǎng)絡(luò)結(jié)構(gòu)簡(jiǎn)圖G如圖1所示，對(duì)其進(jìn)行加虛分支，形成新的網(wǎng)絡(luò)結(jié)構(gòu)圖G′，如圖2所示，在通風(fēng)網(wǎng)絡(luò)系統(tǒng)的改造過程中，確定最大流是必不可少的，在此應(yīng)用通路法來求解該網(wǎng)絡(luò)的最大流。通路法確定通風(fēng)網(wǎng)絡(luò)最大流為以下四個(gè)步驟：1）增加虛分支；2）求通路；3）最小可增廣通路；4）通路增廣

圖1中各分支的容量和容許流為 ：e1（12，0），e2（10，0），e3（20，0），e4（9，0），e5（8，0），e6（8，0），e7（7，0），e8（18，0）。

對(duì)于圖2，a=9，b=10。所加虛分支的容量依次為：

c91=c12=12，c95=c56=12，c4，10=c34=20，c8，10=c78=18。

可確定出圖2的通路為：

P1={e9，e1，e2，e3，e11}，P2={e9，e1，e2，e5，e8，e12}，

P3={e10，e6，e4，e2，e3，e11}，P4={e10，e6，e7，e8，e12}，

P5={e10，e6，e4，e2，e5，e8，e12}。

最小可增廣通路為P4。

圖1 某礦通風(fēng)網(wǎng)絡(luò)簡(jiǎn)圖

圖2 加虛分支后的通風(fēng)網(wǎng)絡(luò)圖

對(duì)P4中的各分支進(jìn)行增廣，增廣后P4中各分支的容量和容許流量分別為 ：e10（8，7），e6（8，7），e7（7，7），e8（18，7），e12（18，7）。然后繼續(xù)搜索最小可增廣通路，并進(jìn)行通路增廣，直到找不到可增廣通路為止，隨后依次進(jìn)行增廣的通路為P3，P2和P1，通路增廣過程完成后，用下式計(jì)算最大流，

至于如何使風(fēng)流按照一定的方式流動(dòng)，可采用增阻法、降阻法或增能法進(jìn)行風(fēng)量調(diào)節(jié)。

3 結(jié)論

1）介紹了最大流問題的研究歷史，總結(jié)了這段時(shí)期內(nèi)人們建立的最大流問題較為完善的理論和算法，并分析了經(jīng)典算法及相關(guān)技術(shù)對(duì)網(wǎng)絡(luò)最大流問題的研究起到的推動(dòng)作用；2）針對(duì)求解最大流在礦井通風(fēng)系統(tǒng)中的應(yīng)用實(shí)例進(jìn)行分析，該實(shí)例用通路法求解最大流，只需進(jìn)行4次增廣，通過與其他方法的對(duì)比可知該方法具有運(yùn)算量小的優(yōu)點(diǎn)，能夠在復(fù)雜的網(wǎng)絡(luò)問題中極大地減小運(yùn)算量，從而減小出錯(cuò)概率、減輕工作負(fù)擔(dān)。

[1]張憲超，陳國(guó)良.小容量網(wǎng)絡(luò)上的最大流算法[J].計(jì)算機(jī)研究與發(fā)展，2001(2).

[2]沈金龍，喻錦華.計(jì)算機(jī)通信網(wǎng)最大流算法的分析和實(shí)現(xiàn)[J].南京郵電學(xué)院學(xué)報(bào)，1994(4).

[3]凌永發(fā)，王杰，李正明.網(wǎng)絡(luò)最大流問題典型組合算法研究[J].云南民族大學(xué)學(xué)報(bào)：自然科學(xué)版，2006(3).

[4]解季萍，楊超，謝剛.網(wǎng)絡(luò)最大流問題和典型阻塞流算法研究[J].西南林學(xué)院學(xué)報(bào)，2005(2).