最小生成樹(shù)算法及其在天然氣管道網(wǎng)中的應(yīng)用研究

張淑萍

摘要：在城市的快速化建設(shè)發(fā)展中，天然氣系統(tǒng)是非常重要的基礎(chǔ)設(shè)施之一，是保障人民基本生活的物質(zhì)基礎(chǔ)。但是，天然氣管網(wǎng)非常復(fù)雜，怎樣合理設(shè)計(jì)其鋪設(shè)布局，直接關(guān)系著整個(gè)系統(tǒng)的可靠性、安全性。利用生成樹(shù)算法，可以將環(huán)狀管網(wǎng)轉(zhuǎn)化成樹(shù)狀管網(wǎng)，確定天然氣管道的最短路線，進(jìn)而優(yōu)化天然氣管道鋪設(shè)方案。本文簡(jiǎn)單介紹了最小生成樹(shù)算法及其在天然氣管道鋪設(shè)布局中的應(yīng)用。

關(guān)鍵詞：最小生成樹(shù);算法;天然氣管道網(wǎng);深度優(yōu)先;遍歷

中圖分類號(hào)：TP301 ? ? ? ? ? ? ? ? ?文獻(xiàn)標(biāo)識(shí)碼：A

文章編號(hào)：1009-3044（2020）17-0214-03

天然氣系統(tǒng)是現(xiàn)實(shí)生活中是關(guān)乎日常生活的基礎(chǔ)設(shè)施，我國(guó)對(duì)天然氣管網(wǎng)的也十分重視，由于現(xiàn)實(shí)的需求以及國(guó)家的支持，我國(guó)的天然氣配套發(fā)展也在不斷地完善，同時(shí)燃?xì)馍a(chǎn)能力也在迅速地提高，由于發(fā)展的快速，我國(guó)天然氣管網(wǎng)系統(tǒng)的不斷的得以提升，隨著管網(wǎng)布局的擴(kuò)大以及天然氣用量需求的增大，天然氣管道網(wǎng)的建設(shè)及布局成為重要的考量項(xiàng)目，為更進(jìn)一步的適應(yīng)發(fā)展的需求天然氣管道網(wǎng)絡(luò)需要一種新的模式，利用最小生成樹(shù)算法將傳統(tǒng)的環(huán)裝光網(wǎng)改進(jìn)為樹(shù)狀管網(wǎng)，增加其覆蓋面積并且縮短其線路支路是一種良好的選擇。

1最小生成樹(shù)算法

最小生成樹(shù)算法是數(shù)據(jù)結(jié)構(gòu)圖中的一種重要的算法應(yīng)用，其要求得到一棵生成樹(shù)，即從一個(gè)帶權(quán)無(wú)向完全圖中選擇n-1條邊，并且這個(gè)圖仍然保持聯(lián)通狀態(tài)，并且還要保證樹(shù)的權(quán)最小。其中最長(zhǎng)用的當(dāng)屬Prim算法與Kruskal算法，以下是兩種算法的具體介紹。

1）Prim算法

Prim算法于1957年提出，又稱為邊割法[1]，其算法的基本思想為任意選取區(qū)域中一節(jié)點(diǎn)a構(gòu)成集合At，之后，不斷地在A-At中選擇一點(diǎn)ak到集合At中抹點(diǎn)權(quán)最小的邊，例如選擇ai，構(gòu)成（ak，ai）加入樹(shù)T之中，并且命令A(yù)t=AtU|ak|，最終確定At=A。

Step1：設(shè)a為A的任意一個(gè)頂點(diǎn)，下指令：S0={a}，E0=Φ，k=0;

Step2：若Sk=A，則程序運(yùn)行結(jié)束，即生成了以Sk為頂點(diǎn)集，Ek為邊集的最小生成樹(shù);

Step3：若Sk≠A，若[Sk，St]=Φ，則最小生成樹(shù)各個(gè)節(jié)點(diǎn)不連通，程序停止運(yùn)行;

若Sk=A，程序繼續(xù)運(yùn)行，設(shè)w（ek）=minw（e），e∈{Sk，Stk}，ek=akak，下命令：Sk+1=SkU{ak，}，Ek+1=EkU{ek}，k=k+1，程序繼續(xù)返回Step2運(yùn)行[11]。

該算法主要針對(duì)點(diǎn)進(jìn)項(xiàng)操作，算法較為簡(jiǎn)單，一般用于求邊稠密管道網(wǎng)線連接最小生成樹(shù)，因此正好適用于聯(lián)通網(wǎng)的最小生成樹(shù)[2]。

2）Kruskal算法

該方法又稱之為避圈法，其算法主要思想在于每次選取最小權(quán)值的邊e加入?yún)^(qū)域T中，如果邊e在T中可以構(gòu)成回路，則邊e既可以定義為回路中的最長(zhǎng)邊，此時(shí)，今次那個(gè)刪減，只到區(qū)域中達(dá)到n=1條邊為止。此時(shí)區(qū)域T中不含有任何的回路，即證明形成了最小生成樹(shù)[3]。

Kruskal算法的算法步驟具體設(shè)計(jì)為：

Step1：在給定網(wǎng)絡(luò)中按照權(quán)值大小將邊由小到大排序，w（e1）≤w（e2）≤w（e3）≤…≤w（en）≤w（en-1），此時(shí)下命令：T0=（V，Φ），i=1，J=0;

Step2：若Tj+ej-1含有回路，則繼續(xù)執(zhí)行Step3，否則，直接執(zhí)行Step4;

Step3：置i=i+1，若i≤m，則執(zhí)行Step2，否則程序停止，既在給定網(wǎng)絡(luò)中不存在最小生成樹(shù);

Step4：下命令Tj+1=Tj+ej+1，j=j+1;

Step5：若j=n-1，則程序結(jié)束，給定網(wǎng)絡(luò)中存在最小生成樹(shù)即Ti，否則，返回Step3繼續(xù)執(zhí)行程序。

Kruskal算法對(duì)邊進(jìn)行計(jì)算操作，適合于求邊稀疏的最小生成樹(shù)，在大區(qū)域網(wǎng)線管道鋪設(shè)計(jì)算中尤為適合。

2 Prim算法求最小生成樹(shù)

2.1最小生成樹(shù)舉例

上文中提到Prim算法主要對(duì)點(diǎn)進(jìn)行操作，首先選取一個(gè)頂點(diǎn)加入生成樹(shù)之中，之后對(duì)點(diǎn)所在的邊進(jìn)行排序，通過(guò)對(duì)比好的權(quán)值最小的邊，將其斷電與另一斷電都加入至生成樹(shù)中，重復(fù)步驟直至所有端點(diǎn)都加入至生成樹(shù)之中。下面列舉一個(gè)較為簡(jiǎn)單的例子：

假設(shè)某地區(qū)天然氣管道需要通往7個(gè)小區(qū)，在圖1中以來(lái)表示，七個(gè)小區(qū)之間的距離連接如圖1所示，為節(jié)約資金，需要設(shè)計(jì)最短線路，并且確保該線路能都連接7個(gè)小區(qū)，保證小區(qū)的天然氣管道使用。

上圖即為由點(diǎn)和邊所構(gòu)成的無(wú)項(xiàng)圖，通常由G表示，圖中小區(qū)可以稱之為無(wú)項(xiàng)圖G的節(jié)點(diǎn)，圖中線條即小區(qū)間的管道連接即為無(wú)方圖的邊，而各個(gè)管道施工設(shè)計(jì)的花費(fèi)稱之為無(wú)向圖的權(quán)，此時(shí)無(wú)向圖就成了賦權(quán)圖[4]。

圖2為沒(méi)有閉合曲線的賦權(quán)圖，此時(shí)可以稱之為樹(shù)，圖2中的小區(qū)（點(diǎn)）與管道線路（邊）構(gòu)成了樹(shù)，如果，圖2所示線路的權(quán)是圖1網(wǎng)絡(luò)區(qū)域中是最小值，則此時(shí)的樹(shù)即為最小生成樹(shù)。

2.2使用Prim算法求最小生成樹(shù)

仍以上節(jié)所述的小區(qū)天然線管道鋪設(shè)為例，求其管道鋪設(shè)的花費(fèi)最低，即樹(shù)圖中權(quán)值最低，以簡(jiǎn)圖示意：

令，X=U，y=A-U，頂點(diǎn)①∈X，頂點(diǎn)②，③，④。⑤，⑥，⑦等屬于y，在與頂點(diǎn)①向關(guān)聯(lián)的邊中，邊（1，3）的權(quán)值為最小值，因此，將③移動(dòng)到X中，在剩余頂點(diǎn)中，從y移動(dòng)到X的候選頂點(diǎn)為②，④，⑤，⑦，因?yàn)檫叄?，3）的權(quán)值最小，因此，將②由y移至X，之后候選頂點(diǎn)為④，⑤，⑥，⑦，由于在一端點(diǎn)處于y區(qū)域，一端點(diǎn)處于X區(qū)域的邊中，權(quán)值最小的邊為（2，6）因此，將⑥移至X區(qū)，此時(shí)剩余的候選頂點(diǎn)為④，⑤，⑦，由于在一端點(diǎn)處于y區(qū)域，一端點(diǎn)處于X區(qū)域的邊中，權(quán)值最小的邊為（6，7）因此，將⑦由y移至X區(qū)，此時(shí)的剩余頂點(diǎn)為④，⑤，由于在一端點(diǎn)處于y區(qū)域，一端點(diǎn)處于X區(qū)域的邊中，權(quán)值最小的邊為（6，5），因此將⑤移至X區(qū)，此時(shí)剩余候選頂點(diǎn)為④，邊（5，4）的權(quán)值最小，將④由y移至X，此時(shí)得到最小生成樹(shù)，如圖4所示[5，6]：

2.3深度優(yōu)先遍歷

遍歷指沿著某條路徑，一次對(duì)樹(shù)中每個(gè)節(jié)點(diǎn)做一次且僅一次的訪問(wèn)。此方法在最小生成樹(shù)的基礎(chǔ)上進(jìn)行布線，分析討論每一個(gè)節(jié)點(diǎn)，對(duì)節(jié)點(diǎn)進(jìn)行確認(rèn)，刪除不需要的節(jié)點(diǎn)，以確保所選擇的方案更加合理規(guī)范。

遍歷是二叉樹(shù)中重要的運(yùn)算，首先明確二叉樹(shù)的基本定義，一棵非空的二叉樹(shù)有三個(gè)基本組成部分，分別是根節(jié)點(diǎn)（N）、左子樹(shù)（L），右子樹(shù)（R）。優(yōu)先遍歷的具體操作內(nèi)容如下：1）訪問(wèn)結(jié)點(diǎn)（N）;2）遍歷該結(jié)點(diǎn)的左子樹(shù)（L）;3）遍歷該結(jié)點(diǎn)的右子樹(shù)（R）。這三種操作內(nèi)容可以構(gòu)成六種算法執(zhí)行次序，分別是NLR、LPN、LNR、NRL、RLN、RNL，這六種算法執(zhí)行次序又可以分為兩部分：前三種序列與后三種序列，前三種序列與后三種序列呈現(xiàn)對(duì)稱的關(guān)系。若訪問(wèn)節(jié)點(diǎn)均第一次經(jīng)過(guò)節(jié)點(diǎn)計(jì)算時(shí)，此時(shí)的遍歷為前序遍歷，而如果訪問(wèn)節(jié)點(diǎn)均在第二次經(jīng)過(guò)結(jié)點(diǎn)時(shí)，此時(shí)的遍歷為中序遍歷，如果訪問(wèn)結(jié)點(diǎn)均是在第三次經(jīng)過(guò)結(jié)點(diǎn)，則此時(shí)為后序遍歷。對(duì)第一次、第二次與第三次經(jīng)過(guò)的節(jié)點(diǎn)進(jìn)行列表統(tǒng)計(jì)，可以得到遍歷序列，為前序序列，中序序列與后序序列[7，8]。

前序序列，后序序列與中序序列都屬于線性序列，并且都有且僅有一個(gè)開(kāi)始結(jié)點(diǎn)與一個(gè)終端結(jié)點(diǎn)，其余的結(jié)點(diǎn)都有且僅有一個(gè)前趨結(jié)點(diǎn)與后繼結(jié)點(diǎn)。

2.4刪除不需要的節(jié)點(diǎn)算法舉例——以天然氣調(diào)壓站為例

優(yōu)先遍歷最主要的作用在于刪除不需要的節(jié)點(diǎn)，天然氣管道網(wǎng)絡(luò)在設(shè)計(jì)中需要設(shè)計(jì)調(diào)壓站，因?yàn)檎{(diào)壓站的設(shè)計(jì)與制作也需要一定的費(fèi)用，因此，為控制成本，首先要保證以下幾點(diǎn)得以滿足：

首先，天然氣管道網(wǎng)線的鋪設(shè)基于最小生成樹(shù)的基礎(chǔ)，保證所選的管線最優(yōu)，并且保證權(quán)值最小;

其次，假定最小生成樹(shù)中所有的結(jié)點(diǎn)為調(diào)壓站;

再次，利用優(yōu)先遍歷算法，對(duì)調(diào)壓器所在節(jié)點(diǎn)進(jìn)行分析，保證每一個(gè)節(jié)點(diǎn)都得以分析，刪除不必要的節(jié)點(diǎn)。

最后，分析所選擇出的方案的實(shí)際可操作性，結(jié)合實(shí)際情況對(duì)方案進(jìn)行修改，最終確定最合適的管道設(shè)計(jì)方案。

以下舉例說(shuō)明刪除節(jié)點(diǎn)的算法，某地正在鋪設(shè)天然氣管道，已知調(diào)壓站的建設(shè)成本為7萬(wàn)元，每米管線的成本為100元。如果兩節(jié)點(diǎn)之間的距離超過(guò)700米，則，兩節(jié)點(diǎn)之間的距離超過(guò)調(diào)壓站的價(jià)格，此時(shí)兩節(jié)點(diǎn)之間的道路不適合做天然氣管道;如果，兩節(jié)點(diǎn)之間的距離小于700米，并且某一節(jié)點(diǎn)的上一級(jí)節(jié)點(diǎn)與其所有下一級(jí)節(jié)點(diǎn)的距離均小于700米，則建議在其上一級(jí)建設(shè)調(diào)壓站。

3采用最小生成樹(shù)算法設(shè)計(jì)天然氣管道鋪設(shè)布局的案例

在實(shí)際建設(shè)中，由于各道路情況不同，各管道的內(nèi)徑也不同，因此以管道投資作為權(quán)值時(shí)，對(duì)管道賦權(quán)會(huì)很困難，在此情況下，需要計(jì)算平均管道的價(jià)格。

假設(shè)現(xiàn)在需要在n個(gè)城市之間建立天然氣管道，那么需要n-1條管道連接n個(gè)城市。

以北非國(guó)家利比亞Qirah鎮(zhèn)的供天然氣整體規(guī)劃為例，Qirah鎮(zhèn)位于沙提地區(qū)首府巴拉克鎮(zhèn)以東 14 公里，是利比亞南部沙提地區(qū)的重要城鎮(zhèn)，其位于Tarabulus-Ash Shwayrif-Brak主要公路上。其管道鋪設(shè)所涉及的最重要的居民點(diǎn)有4處，分別為HatiyatDabdab，AbuQaraqrah，Dabdab，Ashkidah。

首先分析其地理因素，Qirah鎮(zhèn)中心地帶非常平坦，地形劃分較為明顯，東部與南部偏低，坡度較緩，有部分植被;西部與北部屬于砂礫地形，有大量堅(jiān)實(shí)的沙土和沙礫，無(wú)植被，適合于建房;其東部與南部適合于種植作物，西部或北部適合于居住。根據(jù)利比亞最近一次全國(guó)人口普查顯示即2006年進(jìn)行的人口普查顯示，Qirah鎮(zhèn)人口總數(shù)為5699人，戶口總數(shù)為835戶。

根據(jù)利比亞國(guó)家空間規(guī)劃政策（NPSP）研究預(yù)測(cè)：利比亞全國(guó)2010—2020 年人口平均增長(zhǎng)率為1.7%，2020—2030 年人口平均增長(zhǎng)率為1.4%，呈現(xiàn)下降趨勢(shì)。根據(jù)利比亞人口預(yù)測(cè)可以推算出1981～2000 年Qirah鎮(zhèn)預(yù)測(cè)的人口平均增長(zhǎng)率為3.6%，在2000年左右Qirah鎮(zhèn)人口會(huì)達(dá)到3400人但是Qirah鎮(zhèn)的實(shí)際人口在 2006 年已達(dá)到5699人，因此1981—2006年的人口預(yù)測(cè)增長(zhǎng)率偏低，根據(jù)計(jì)算其實(shí)際的人口平均增長(zhǎng)率已經(jīng)達(dá)到 4.88%，根據(jù)之前的預(yù)測(cè)及人口實(shí)際增長(zhǎng)經(jīng)驗(yàn)，再次對(duì)Qirah鎮(zhèn)的人口平均增長(zhǎng)率進(jìn)行預(yù)測(cè)[9，10]。

2008—2015 年為 3.66%，2016—2025 年預(yù)測(cè)人口增長(zhǎng)率為 2.00%。

P2015=P2006×（1+x）9=5699×（1+3.66%）9≈7880（人）

P2025=P2015×（1+x）10=7880×（1+2.00%）10≈9610（人）

其中，P代表人口數(shù)，X代表某時(shí)間段人口增長(zhǎng)率。

因此，可以得出結(jié)論近Qirah鎮(zhèn)近期人口為7880 人，遠(yuǎn)期人口約 9610 人。以上，可以大致得出Qirah鎮(zhèn)的用氣人數(shù)。

根據(jù)當(dāng)?shù)卣囊笠约熬用竦膶?shí)際生活情況，可以初步估計(jì)低壓天然氣干管管徑在 de32～de40，天然氣管道選用 pe 天然氣管，管徑的選擇可以采用 de40，參照我國(guó)的管道價(jià)格對(duì)管道價(jià)格進(jìn)行推算：de40 管價(jià)格約為 4.5元/米，燃?xì)夤艿冷佋O(shè)的開(kāi)挖填埋費(fèi)用約為 6.5元/米，因此可以初步的推算出管道總價(jià)格為11.0 元/米。

天然氣管道設(shè)計(jì)的最優(yōu)化，通俗來(lái)講即在滿足所有用戶的用氣需求時(shí)，所投入成本最低。天然氣管道網(wǎng)建設(shè)中的投資主要集中于兩個(gè)方面：1）天然氣管道建設(shè);2）調(diào)壓站建設(shè)。根據(jù)上文分析可知，天然氣管道投資與調(diào)壓站投資存在于負(fù)相關(guān)的關(guān)系，若在管線網(wǎng)中只建設(shè)以一個(gè)管線，則需要在最小生成樹(shù)的所有邊，即所用用戶點(diǎn)之間鋪設(shè)管線，此時(shí)調(diào)壓站的投資最小，而管道線路的投資最大;反之，增加調(diào)壓站的數(shù)目，可以使得管線道路的投資減少，而調(diào)壓站的投資增多。

根據(jù)第一章提高的程序?qū)irah鎮(zhèn)進(jìn)行燃?xì)夤芫W(wǎng)設(shè)計(jì)，根據(jù)原方案選用低壓管網(wǎng)，采用 5 個(gè)調(diào)壓站，在實(shí)際設(shè)計(jì)時(shí)為調(diào)壓站提供了大的供氣面積，并且將管網(wǎng)設(shè)置為環(huán)狀管網(wǎng)布置，用以充分確保供氣可靠性與可持續(xù)性，在后期的設(shè)計(jì)方案中，結(jié)合最小生成樹(shù)算法選用中壓管網(wǎng)與低壓管網(wǎng)相結(jié)合的設(shè)計(jì)，將低壓管網(wǎng)改進(jìn)為樹(shù)狀設(shè)計(jì)，而將中壓管網(wǎng)設(shè)置成環(huán)裝管網(wǎng)，并且將調(diào)壓站增加為10個(gè)，由于Qirah鎮(zhèn)的人口規(guī)模不算太大，而且人口增長(zhǎng)呈現(xiàn)平緩趨勢(shì)，因此采用低壓管網(wǎng)與中壓管網(wǎng)相結(jié)合，并引入樹(shù)狀布置能夠充分滿足當(dāng)?shù)厝嗣竦墓庑枨蟆?/p>

4結(jié)束語(yǔ)

由于燃?xì)夤艿赖慕ㄔO(shè)也呈現(xiàn)出集約化的模式，因此針對(duì)燃?xì)夤芫W(wǎng)的布置，現(xiàn)逐步趨向于利用計(jì)算機(jī)對(duì)管道網(wǎng)絡(luò)整體工程進(jìn)行分析，計(jì)算機(jī)分析對(duì)于情況較為復(fù)雜的區(qū)域燃?xì)夤芫W(wǎng)布置具有十分顯著的優(yōu)勢(shì)，其可以化繁為簡(jiǎn)，減小工作量，另外，可以針對(duì)復(fù)雜節(jié)點(diǎn)的賦權(quán)圖設(shè)計(jì)程序，以最快的方式確定最小生成樹(shù)演算，能及時(shí)有效的分析節(jié)點(diǎn)動(dòng)態(tài)，及時(shí)確立最優(yōu)管線設(shè)置情況，因此，可以極大地提高工程的效率，并且實(shí)現(xiàn)了管道設(shè)計(jì)最優(yōu)化的問(wèn)題。

參考文獻(xiàn)：

[1] 胡藝文，崔勇，姬德森，等.基于prim和dijkstra組合算法的配電網(wǎng)新增容量規(guī)劃方法[J].中國(guó)農(nóng)村水利水電，2015（6）：179-182.

[2] 薛瑞，司倩楠，等.邊權(quán)相同的最小生成樹(shù)改進(jìn)算法[J].信陽(yáng)師范學(xué)院學(xué)報(bào)：自然科學(xué)版，2015（4）：597-600.

[3] 馮雪平，宋曉輝，梁英，等.基于最小生成樹(shù)及改進(jìn)遺傳算法的含分布式電源配電網(wǎng)孤島劃分方法[J].高電壓技術(shù)，2015，41（10）：3470-3478.

[4] 蔣小娟，張安，陳永，等.內(nèi)部節(jié)點(diǎn)受限的最小生成樹(shù)問(wèn)題算法研究[J].計(jì)算機(jī)工程與應(yīng)用，2017（10）：35-37.

[5] 湯天波. Pathfinder算法優(yōu)化研究[J].計(jì)算機(jī)應(yīng)用與軟件，2015，32（11）：277-280.

[6] 王磊.最短路算法和最小生成樹(shù)算法在配電網(wǎng)絡(luò)重構(gòu)中的應(yīng)用研究[D].西安理工大學(xué)，2009.

[7] 胡藝文，崔勇，姬德森，等.基于prim和dijkstra組合算法的配電網(wǎng)新增容量規(guī)劃方法[J].中國(guó)農(nóng)村水利水電，2015（6）：179-182.

[8] 趙林，朱桂斌，文玉強(qiáng)，等.基于最小生成樹(shù)的規(guī)則圖像碎片復(fù)原算法[J].計(jì)算機(jī)技術(shù)與發(fā)展，2016，26（6）：69-72.

[9] 宋國(guó)治，王鋮，涂遙，等.基于Prim初始種群選取優(yōu)化遺傳算法的三維片上網(wǎng)絡(luò)低功耗映射[J].計(jì)算機(jī)應(yīng)用，2017，37（1）：90-96.

【通聯(lián)編輯：王力】