基于最小分支剩余容量的礦井通風(fēng)網(wǎng)絡(luò)極值流算法

摘要：為計(jì)算礦井最大通風(fēng)量，針對最短增廣鏈算法隨機(jī)選取增廣鏈，造成增廣鏈缺失和極值流偏小的問題，提出一種基于最小分支剩余容量的礦井通風(fēng)網(wǎng)絡(luò)極值流算法。該算法在選取增廣鏈時，選擇中間分支剩余容量最小的增廣鏈進(jìn)行增廣；每次增廣完畢后，優(yōu)先選擇與增廣完畢的增廣鏈包含相同分支的增廣鏈進(jìn)行下一次增廣。利用Excel Solver解算模型與BA無標(biāo)度隨機(jī)網(wǎng)絡(luò)進(jìn)行仿真實(shí)驗(yàn)，結(jié)果表明該算法比最短增廣鏈算法解算時間短，且避免了增廣鏈缺失。研究結(jié)論為礦井最大通風(fēng)量的計(jì)算提供理論參考。

關(guān)鍵詞：礦井通風(fēng)網(wǎng)絡(luò)；極值流；增廣鏈；最小分支剩余容量；分層剩余網(wǎng)絡(luò)

中圖分類號：X936 文獻(xiàn)標(biāo)志碼：A 文章編號：1008-0562（2024）02-0150-06

0 引言

礦井通風(fēng)情況對礦山安全具有重要意義，礦井最大通風(fēng)量是核定礦井通風(fēng)能力、礦井通風(fēng)阻力的重要依據(jù)。極值流算法是計(jì)算礦井最大通風(fēng)量的常用方法之一。近年來，關(guān)于礦井通風(fēng)網(wǎng)絡(luò)極值流算法的研究取得了一定進(jìn)展。羅甜甜等提出一種重置節(jié)點(diǎn)下標(biāo)的算法，對節(jié)點(diǎn)下標(biāo)按照制定的規(guī)則重新編號，使網(wǎng)絡(luò)圖更清晰直觀，節(jié)約了增廣鏈的尋找時間，規(guī)避了最短增廣鏈算法的反復(fù)構(gòu)造分層剩余網(wǎng)絡(luò)與增廣鏈選取隨機(jī)的缺陷。趙禮峰等將剩余網(wǎng)絡(luò)替換成余網(wǎng)絡(luò)，并根據(jù)其特點(diǎn)劃分成若干個區(qū)域，降低算法空間復(fù)雜度。韓穎錚等提出一種基于有效反向網(wǎng)絡(luò)的算法，降低了節(jié)點(diǎn)深度計(jì)算次數(shù)，同時避免了反復(fù)搜索無效路徑。江錦成等、趙禮峰等基于預(yù)流推進(jìn)算法提出了相應(yīng)的改進(jìn)算法，其穩(wěn)定性和速度都優(yōu)于預(yù)流推進(jìn)算法。尚文天等利用最大流算法滿足節(jié)點(diǎn)流量平衡與可行流具有上下界容量限制的條件，提出一種有上下界風(fēng)量約束的礦井風(fēng)量極值流算法。林俊余等通過記錄搜索狀態(tài)的記憶化搜索方法，規(guī)避重復(fù)搜索網(wǎng)絡(luò)流中的無效部分，提高了最大流算法執(zhí)行效率。

最短增廣鏈算法作為通風(fēng)網(wǎng)絡(luò)極值流的經(jīng)典算法，簡化了通風(fēng)網(wǎng)絡(luò)，降低了算法的復(fù)雜度，是求解極值流的常用算法之一。最短增廣鏈算法在增廣鏈的選擇上具有隨機(jī)性，易導(dǎo)致增廣鏈缺失，造成通風(fēng)網(wǎng)絡(luò)極值流偏小。本文提出一種基于最小分支剩余容量的礦井通風(fēng)網(wǎng)絡(luò)極值流算法，制定最小分支剩余容量規(guī)則，并依此確定增廣順序，以解決最短增廣鏈算法增廣鏈缺失的問題。

1 最小分支剩余容量算法

1.1 極值流的相關(guān)定義

定義1 有向連通圖及其網(wǎng)絡(luò)。設(shè)有向連通圖為D=（V，A），其中V為節(jié)點(diǎn)集合，包含源點(diǎn)vs、匯點(diǎn)vt和中間點(diǎn)vi。A為D的弧集，定義一個非負(fù)整值函數(shù)c，稱其為容量函數(shù)，對于任意弧a∈A，稱c（a）為弧a上的容量，此時構(gòu)成一個網(wǎng)絡(luò)（即通風(fēng)網(wǎng)絡(luò)），記為G=（VA，c）。

定義2剩余網(wǎng)絡(luò)。非飽和分支及其節(jié)點(diǎn)的集合稱為剩余網(wǎng)絡(luò)，記為G（f）=（V，A（f），c（f））。f為通風(fēng)網(wǎng)絡(luò)G的可行流。

定義3 分層剩余網(wǎng)絡(luò)。分層剩余網(wǎng)絡(luò)G’（f）記錄剩余網(wǎng)絡(luò)G（f）中各節(jié)點(diǎn)的層次，根據(jù)寬度優(yōu)先搜索法（BFS），基于剩余網(wǎng)絡(luò)G（f）構(gòu)建通風(fēng)網(wǎng)絡(luò)G關(guān)于可行流廠的分層剩余網(wǎng)絡(luò)G'（f），在G’（f）中可以得知源點(diǎn)vs到各個節(jié)點(diǎn)vi的最短路徑。

定義4 中間分支。與源分支終點(diǎn)、匯分支起點(diǎn)互不關(guān)聯(lián)的分支稱為中間分支（vi，vj），其容量記為c（vi，vj）。

定義5 最小分支剩余容量規(guī)則。在G'（f）中，將中間分支按照其剩余容量從小到大進(jìn)行排序，優(yōu)先選擇剩余容量較小的中間分支所在的增廣鏈進(jìn)行增廣；若增廣鏈的中間分支剩余容量相同，則優(yōu)先選擇除中間分支外含有最小剩余容量分支的增廣鏈進(jìn)行增廣。每次增廣完畢后，除源分支和匯分支外，優(yōu)先選擇與剛增廣完畢的增廣鏈包含相同分支的增廣鏈進(jìn)行增廣；若包含相同分支的增廣鏈不止一條，則優(yōu)先選擇除中間分支外含有較小剩余容量分支的增廣鏈進(jìn)行增廣。

1.2 最小分支剩余容量算法的解算步驟

最小分支剩余容量算法的解算步驟見圖1。

2 算例分析與比較

以圖2所示的通風(fēng)網(wǎng)絡(luò)為例，分別用最小分支剩余容量算法和最短增廣鏈算法解算網(wǎng)絡(luò)的極值流。其中，各分支旁的數(shù)值為該分支的容量、流量。

2.1 最小分支剩余容量算法解算過程

設(shè)初始流fi為零流，構(gòu)建分層剩余網(wǎng)絡(luò)G’（f1），見圖3，其中各分支旁的數(shù)值為該分支的剩余容量。

圖3中包括（v2，v5）、（v2，v6）、（v4，v6）和（v3，v7）4條中間分支，記U={（v4，v6），（v2，v5），（v3，v7），（v2，v6））。選擇包含（v4，v6）的增廣鏈u1=vsv1v4v6v8vt進(jìn)行增廣，流值為δ1=min{130，30，20，60，120}=20，（v4，v6）分支變?yōu)轱柡头种В蕜h除分=（v4，v6）與（v1，v4），對f1進(jìn)行增廣，令f2 =f1，更新f2與分層剩余網(wǎng)絡(luò)G'（f2），見圖4。

由圖4可知，G'（f2）中增廣鏈u2=vsv1v2v6v8vt與增廣鏈u1包含相同分支（V6，V8），其增廣流值為δ2=min{110，50，60，40，100}=40，（v6，v8）分支變?yōu)轱柡头种?，故刪除分支（v6，v8）和（v2，v6），對f2進(jìn)行增廣，令f3 =f2，f3與分層剩余網(wǎng)絡(luò)G'（f3）見圖5。

由圖5可知，G'（f3）中增廣鏈u3=vsv1v2v5v8vt與u2包含相同分支（v1，v2），u3增廣流值為δ3=min {70，10，30，30，60} =10，刪除分支（v1，v2）、（v2，v5）和（v5，v8），增廣后令f4=f3，f4與分層剩余網(wǎng)絡(luò)G'（f4）見圖6。

在G'（f4）中選擇含有中間分支（v3，v7）的增廣鏈u4=vsv1v3v7v8vt進(jìn)行增廣，其增廣的流值為δ4=min{60，40，40，20，50}=20。對u4進(jìn)行增廣后，令f5=f4，f5與分層剩余網(wǎng)絡(luò)G'（f3）見圖7。

由圖7 （b）可知，在G'（f5）中已不存在從源點(diǎn)vs到匯點(diǎn)vt的增廣鏈，重新構(gòu)造分層剩余網(wǎng)絡(luò)，刪除分層剩余網(wǎng)絡(luò)中容量為0的弧，令f6=f5，重新構(gòu)建分層剩余網(wǎng)絡(luò)G'（f6），見圖8。

在G'（f6）中對增廣鏈u5=vsv1v3v7v5v8vt進(jìn)行增廣，增廣流值為δ5 =min{40，20，40，20，30} =20。對u5增廣后，令f7=f6，構(gòu)造f7與分層剩余網(wǎng)絡(luò)G'（f7），見圖9。

由圖9 （b）可知，在G'（f7）中不存在從源點(diǎn)vs到匯點(diǎn)vt的增廣鏈，已不能進(jìn)行增廣，構(gòu)建剩余網(wǎng)絡(luò)G（f7），見圖10。其中虛線分支代表通風(fēng)網(wǎng)絡(luò)G的極值流f7，實(shí)線分支代表通風(fēng)網(wǎng)絡(luò)G的剩余容量c'（vt，vj），虛分支與前向分支不構(gòu)成閉環(huán)。G（f7）各分支的極值流f與剩余容量c'（vi，vj）見表1，最小分支剩余容量算法解算的極值流為110。

2.2 最短增廣鏈算法解算過程

設(shè)初始可行流f1為零流，構(gòu)建剩余網(wǎng)絡(luò)G（f1），求出分層剩余網(wǎng)絡(luò)G'（f1），見圖3。在G'（f1）中，源點(diǎn)vs到匯點(diǎn)vt的增廣鏈有u1=vsv1v2v5v8vt，u2=vsv1v3v7v8vt，u3=vsv1v4v6v8vt，u4=vsv1v2v6v8vt。沿著u1～u4對極值流f1進(jìn)行增廣，流值分別為δ1'=30，δ2'=20，δ3'=20，δ4'=20，增廣后，刪除飽和分支，令f2'=f1'，f2'與分層剩余網(wǎng)絡(luò)G'（f2'），見圖11。

由圖11 （b）可知，G'（f2'）中不存在從源點(diǎn)vs到匯點(diǎn)vt的增廣鏈，構(gòu)建剩余網(wǎng)絡(luò)G（f2'），見圖12。G（f2'）中各分支的極值流fn'與剩余容量C'（vi，vj）見表2。圖12中，實(shí)線分支代表通風(fēng)網(wǎng)絡(luò)G（f2'）的剩余容量，虛線分支代表通風(fēng)網(wǎng)絡(luò)的極值流。最短增廣鏈算法解算的極值流為90，小于最小分支剩余容量算法求得的極值流。最短增廣鏈算法隨機(jī)選擇增廣鏈，易造成增廣鏈缺失，導(dǎo)致通風(fēng)網(wǎng)絡(luò)極值流偏小。

3 算法的驗(yàn)證與效率對比

3.1 算法驗(yàn)證

為檢驗(yàn)新算法的準(zhǔn)確性，在Microsoft Excel中建立通風(fēng)網(wǎng)絡(luò)G的數(shù)學(xué)模型。根據(jù)通風(fēng)網(wǎng)絡(luò)G中各節(jié)點(diǎn)vi與各分支（vi，vj）之間的拓?fù)潢P(guān)系，在Excel中構(gòu)建關(guān)于通風(fēng)網(wǎng)絡(luò)G的數(shù)學(xué)模型，并插入SUMIF函數(shù)計(jì)算通風(fēng)網(wǎng)絡(luò)G中各節(jié)點(diǎn)vi的容差αi。

利用Excel Solver解算模型。在Excel中設(shè)置規(guī)劃求解的各項(xiàng)參數(shù)，添加約束，使通過每條分支的極值流fn不超過該分支的分支容量c（vi，vj）。然后利用單純線性規(guī)劃的求解方法解算通風(fēng)網(wǎng)絡(luò)G的極值流fn，解算結(jié)果見表3。

由表3可知，模型解算的極值流為110，極值流及各分支的流量與最小分支剩余容量算法的解算結(jié)果相同，驗(yàn)證了最小分支剩余容量算法的準(zhǔn)確性。且最小分支剩余容量算法比最短增廣鏈算法解算的極值流更大，說明最小分支剩余容量算法對增廣鏈的選擇優(yōu)于最短增廣鏈算法，可以求出通風(fēng)網(wǎng)絡(luò)G的實(shí)際極值流及各分支（vi，vj）流值分配。

3.2 算法效率對比

為比較最小分支剩余容量算法和最短增廣鏈算法的效率，以MATLAB為仿真實(shí)驗(yàn)平臺，采用BA無標(biāo)度隨機(jī)網(wǎng)絡(luò)進(jìn)行仿真實(shí)驗(yàn)，分別將通風(fēng)網(wǎng)絡(luò)節(jié)點(diǎn)數(shù)設(shè)為500、1 000、1 500、2 000、2 500、3 000，在每種規(guī)模下解算10次并計(jì)算平均解算時間。仿真實(shí)驗(yàn)對比結(jié)果見表4。由表4可知，在兩種算法中，最小分支剩余容量算法的解算時間短，解算效率高。

4 結(jié)論

（1）提出了基于最小分支剩余容量的礦井通風(fēng)網(wǎng)絡(luò)極值流算法，制定了最小分支剩余容量規(guī)則，明確了增廣鏈的選擇順序。通過算例分析，證明了最小分支剩余容量算法可以避免最短增廣鏈算法導(dǎo)致的增廣鏈缺失。

（2）通過對通風(fēng)網(wǎng)絡(luò)的Excel Solver模型解算，得到與最小分支剩余容量算法的計(jì)算結(jié)果相同的實(shí)際極值流，驗(yàn)證了該算法的準(zhǔn)確性。

基金項(xiàng)目：內(nèi)蒙古自治區(qū)自然科學(xué)基金項(xiàng)目（2022LHMS05019; 2022LHMS05020）;內(nèi)蒙古自治區(qū)高等學(xué)校科學(xué)研究重點(diǎn)項(xiàng)目 （NJ2221025）