最小生成樹算法及其在天然氣管道網中的應用研究
2020-09-29 07:51:13張淑萍
電腦知識與技術 2020年17期
張淑萍
摘要：在城市的快速化建設發展中，天然氣系統是非常重要的基礎設施之一，是保障人民基本生活的物質基礎。但是，天然氣管網非常復雜，怎樣合理設計其鋪設布局，直接關系著整個系統的可靠性、安全性。利用生成樹算法，可以將環狀管網轉化成樹狀管網，確定天然氣管道的最短路線，進而優化天然氣管道鋪設方案。本文簡單介紹了最小生成樹算法及其在天然氣管道鋪設布局中的應用。
關鍵詞：最小生成樹;算法;天然氣管道網;深度優先;遍歷
中圖分類號：TP301 ? ? ? ? ? ? ? ? ?文獻標識碼：A
文章編號：1009-3044（2020）17-0214-03
天然氣系統是現實生活中是關乎日常生活的基礎設施，我國對天然氣管網的也十分重視，由于現實的需求以及國家的支持，我國的天然氣配套發展也在不斷地完善，同時燃氣生產能力也在迅速地提高，由于發展的快速，我國天然氣管網系統的不斷的得以提升，隨著管網布局的擴大以及天然氣用量需求的增大，天然氣管道網的建設及布局成為重要的考量項目，為更進一步的適應發展的需求天然氣管道網絡需要一種新的模式，利用最小生成樹算法將傳統的環裝光網改進為樹狀管網，增加其覆蓋面積并且縮短其線路支路是一種良好的選擇。
1最小生成樹算法
最小生成樹算法是數據結構圖中的一種重要的算法應用，其要求得到一棵生成樹，即從一個帶權無向完全圖中選擇n-1條邊，并且這個圖仍然保持聯通狀態，并且還要保證樹的權最小。其中最長用的當屬Prim算法與Kruskal算法，以下是兩種算法的具體介紹。
1）Prim算法
Prim算法于1957年提出，又稱為邊割法[1]，其算法的基本思想為任意選取區域中一節點a構成集合At，之后，不斷地在A-At中選擇一點ak到集合At中抹點權最小的邊，例如選擇ai，構成（ak，ai）加入樹T之中，并且命令At=AtU|ak|，最終確定At=A。
Step1：設a為A的任意一個頂點，下指令：S0={a}，E0=Φ，k=0;
Step2：若Sk=A，則程序運行結束，即生成了以Sk為頂點集，Ek為邊集的最小生成樹;
Step3：若Sk≠A，若[Sk，St]=Φ，則最小生成樹各個節點不連通，程序停止運行;
若Sk=A，程序繼續運行，設w（ek）=minw（e），e∈{Sk，Stk}，ek=akak，下命令：Sk+1=SkU{ak，}，Ek+1=EkU{ek}，k=k+1，程序繼續返回Step2運行[11]。
該算法主要針對點進項操作，算法較為簡單，一般用于求邊稠密管道網線連接最小生成樹，因此正好適用于聯通網的最小生成樹[2]。
2）Kruskal算法
該方法又稱之為避圈法，其算法主要思想在于每次選取最小權值的邊e加入區域T中，如果邊e在T中可以構成回路，則邊e既可以定義為回路中的最長邊，此時，今次那個刪減，只到區域中達到n=1條邊為止。此時區域T中不含有任何的回路，即證明形成了最小生成樹[3]。
Kruskal算法的算法步驟具體設計為：
Step1：在給定網絡中按照權值大小將邊由小到大排序，w（e1）≤w（e2）≤w（e3）≤…≤w（en）≤w（en-1），此時下命令：T0=（V，Φ），i=1，J=0;
Step2：若Tj+ej-1含有回路，則繼續執行Step3，否則，直接執行Step4;
Step3：置i=i+1，若i≤m，則執行Step2，否則程序停止，既在給定網絡中不存在最小生成樹;
Step4：下命令Tj+1=Tj+ej+1，j=j+1;
Step5：若j=n-1，則程序結束，給定網絡中存在最小生成樹即Ti，否則，返回Step3繼續執行程序。
Kruskal算法對邊進行計算操作，適合于求邊稀疏的最小生成樹，在大區域網線管道鋪設計算中尤為適合。
2 Prim算法求最小生成樹
2.1最小生成樹舉例
上文中提到Prim算法主要對點進行操作，首先選取一個頂點加入生成樹之中，之后對點所在的邊進行排序，通過對比好的權值最小的邊，將其斷電與另一斷電都加入至生成樹中，重復步驟直至所有端點都加入至生成樹之中。下面列舉一個較為簡單的例子：
假設某地區天然氣管道需要通往7個小區，在圖1中以
上圖即為由點和邊所構成的無項圖，通常由G表示，圖中小區可以稱之為無項圖G的節點，圖中線條即小區間的管道連接即為無方圖的邊，而各個管道施工設計的花費稱之為無向圖的權，此時無向圖就成了賦權圖[4]。
圖2為沒有閉合曲線的賦權圖，此時可以稱之為樹，圖2中的小區（點）與管道線路（邊）構成了樹，如果，圖2所示線路的權是圖1網絡區域中是最小值，則此時的樹即為最小生成樹。
2.2使用Prim算法求最小生成樹
仍以上節所述的小區天然線管道鋪設為例，求其管道鋪設的花費最低，即樹圖中權值最低，以簡圖示意：
令，X=U，y=A-U，頂點①∈X，頂點②，③，④。⑤，⑥，⑦等屬于y，在與頂點①向關聯的邊中，邊（1，3）的權值為最小值，因此，將③移動到X中，在剩余頂點中，從y移動到X的候選頂點為②，④，⑤，⑦，因為邊（2，3）的權值最小，因此，將②由y移至X，之后候選頂點為④，⑤，⑥，⑦，由于在一端點處于y區域，一端點處于X區域的邊中，權值最小的邊為（2，6）因此，將⑥移至X區，此時剩余的候選頂點為④，⑤，⑦，由于在一端點處于y區域，一端點處于X區域的邊中，權值最小的邊為（6，7）因此，將⑦由y移至X區，此時的剩余頂點為④，⑤，由于在一端點處于y區域，一端點處于X區域的邊中，權值最小的邊為（6，5），因此將⑤移至X區，此時剩余候選頂點為④，邊（5，4）的權值最小，將④由y移至X，此時得到最小生成樹，如圖4所示[5，6]：
2.3深度優先遍歷
遍歷指沿著某條路徑，一次對樹中每個節點做一次且僅一次的訪問。此方法在最小生成樹的基礎上進行布線，分析討論每一個節點，對節點進行確認，刪除不需要的節點，以確保所選擇的方案更加合理規范。
遍歷是二叉樹中重要的運算，首先明確二叉樹的基本定義，一棵非空的二叉樹有三個基本組成部分，分別是根節點（N）、左子樹（L），右子樹（R）。優先遍歷的具體操作內容如下：1）訪問結點（N）;2）遍歷該結點的左子樹（L）;3）遍歷該結點的右子樹（R）。這三種操作內容可以構成六種算法執行次序，分別是NLR、LPN、LNR、NRL、RLN、RNL，這六種算法執行次序又可以分為兩部分：前三種序列與后三種序列，前三種序列與后三種序列呈現對稱的關系。若訪問節點均第一次經過節點計算時，此時的遍歷為前序遍歷，而如果訪問節點均在第二次經過結點時，此時的遍歷為中序遍歷，如果訪問結點均是在第三次經過結點，則此時為后序遍歷。對第一次、第二次與第三次經過的節點進行列表統計，可以得到遍歷序列，為前序序列，中序序列與后序序列[7，8]。
前序序列，后序序列與中序序列都屬于線性序列，并且都有且僅有一個開始結點與一個終端結點，其余的結點都有且僅有一個前趨結點與后繼結點。
2.4刪除不需要的節點算法舉例——以天然氣調壓站為例
優先遍歷最主要的作用在于刪除不需要的節點，天然氣管道網絡在設計中需要設計調壓站，因為調壓站的設計與制作也需要一定的費用，因此，為控制成本，首先要保證以下幾點得以滿足：
首先，天然氣管道網線的鋪設基于最小生成樹的基礎，保證所選的管線最優，并且保證權值最小;
其次，假定最小生成樹中所有的結點為調壓站;
再次，利用優先遍歷算法，對調壓器所在節點進行分析，保證每一個節點都得以分析，刪除不必要的節點。
最后，分析所選擇出的方案的實際可操作性，結合實際情況對方案進行修改，最終確定最合適的管道設計方案。
以下舉例說明刪除節點的算法，某地正在鋪設天然氣管道，已知調壓站的建設成本為7萬元，每米管線的成本為100元。如果兩節點之間的距離超過700米，則，兩節點之間的距離超過調壓站的價格，此時兩節點之間的道路不適合做天然氣管道;如果，兩節點之間的距離小于700米，并且某一節點的上一級節點與其所有下一級節點的距離均小于700米，則建議在其上一級建設調壓站。
3采用最小生成樹算法設計天然氣管道鋪設布局的案例
在實際建設中，由于各道路情況不同，各管道的內徑也不同，因此以管道投資作為權值時，對管道賦權會很困難，在此情況下，需要計算平均管道的價格。
假設現在需要在n個城市之間建立天然氣管道，那么需要n-1條管道連接n個城市。
以北非國家利比亞Qirah鎮的供天然氣整體規劃為例，Qirah鎮位于沙提地區首府巴拉克鎮以東 14 公里，是利比亞南部沙提地區的重要城鎮，其位于Tarabulus-Ash Shwayrif-Brak主要公路上。其管道鋪設所涉及的最重要的居民點有4處，分別為HatiyatDabdab，AbuQaraqrah，Dabdab，Ashkidah。
首先分析其地理因素，Qirah鎮中心地帶非常平坦，地形劃分較為明顯，東部與南部偏低，坡度較緩，有部分植被;西部與北部屬于砂礫地形，有大量堅實的沙土和沙礫，無植被，適合于建房;其東部與南部適合于種植作物，西部或北部適合于居住。根據利比亞最近一次全國人口普查顯示即2006年進行的人口普查顯示，Qirah鎮人口總數為5699人，戶口總數為835戶。
根據利比亞國家空間規劃政策（NPSP）研究預測：利比亞全國2010—2020 年人口平均增長率為1.7%，2020—2030 年人口平均增長率為1.4%，呈現下降趨勢。根據利比亞人口預測可以推算出1981～2000 年Qirah鎮預測的人口平均增長率為3.6%，在2000年左右Qirah鎮人口會達到3400人但是Qirah鎮的實際人口在 2006 年已達到5699人，因此1981—2006年的人口預測增長率偏低，根據計算其實際的人口平均增長率已經達到 4.88%，根據之前的預測及人口實際增長經驗，再次對Qirah鎮的人口平均增長率進行預測[9，10]。
2008—2015 年為 3.66%，2016—2025 年預測人口增長率為 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代表人口數，X代表某時間段人口增長率。
因此，可以得出結論近Qirah鎮近期人口為7880 人，遠期人口約 9610 人。以上，可以大致得出Qirah鎮的用氣人數。
根據當地政府的要求以及居民的實際生活情況，可以初步估計低壓天然氣干管管徑在 de32～de40，天然氣管道選用 pe 天然氣管，管徑的選擇可以采用 de40，參照我國的管道價格對管道價格進行推算：de40 管價格約為 4.5元/米，燃氣管道鋪設的開挖填埋費用約為 6.5元/米，因此可以初步的推算出管道總價格為11.0 元/米。
天然氣管道設計的最優化，通俗來講即在滿足所有用戶的用氣需求時，所投入成本最低。天然氣管道網建設中的投資主要集中于兩個方面：1）天然氣管道建設;2）調壓站建設。根據上文分析可知，天然氣管道投資與調壓站投資存在于負相關的關系，若在管線網中只建設以一個管線，則需要在最小生成樹的所有邊，即所用用戶點之間鋪設管線，此時調壓站的投資最小，而管道線路的投資最大;反之，增加調壓站的數目，可以使得管線道路的投資減少，而調壓站的投資增多。
根據第一章提高的程序對Qirah鎮進行燃氣管網設計，根據原方案選用低壓管網，采用 5 個調壓站，在實際設計時為調壓站提供了大的供氣面積，并且將管網設置為環狀管網布置，用以充分確保供氣可靠性與可持續性，在后期的設計方案中，結合最小生成樹算法選用中壓管網與低壓管網相結合的設計，將低壓管網改進為樹狀設計，而將中壓管網設置成環裝管網，并且將調壓站增加為10個，由于Qirah鎮的人口規模不算太大，而且人口增長呈現平緩趨勢，因此采用低壓管網與中壓管網相結合，并引入樹狀布置能夠充分滿足當地人民的供氣需求。
4結束語
由于燃氣管道的建設也呈現出集約化的模式，因此針對燃氣管網的布置，現逐步趨向于利用計算機對管道網絡整體工程進行分析，計算機分析對于情況較為復雜的區域燃氣管網布置具有十分顯著的優勢，其可以化繁為簡，減小工作量，另外，可以針對復雜節點的賦權圖設計程序，以最快的方式確定最小生成樹演算，能及時有效的分析節點動態，及時確立最優管線設置情況，因此，可以極大地提高工程的效率，并且實現了管道設計最優化的問題。
參考文獻：
[1] 胡藝文，崔勇，姬德森，等.基于prim和dijkstra組合算法的配電網新增容量規劃方法[J].中國農村水利水電，2015（6）：179-182.
[2] 薛瑞，司倩楠，等.邊權相同的最小生成樹改進算法[J].信陽師范學院學報：自然科學版，2015（4）：597-600.
[3] 馮雪平，宋曉輝，梁英，等.基于最小生成樹及改進遺傳算法的含分布式電源配電網孤島劃分方法[J].高電壓技術，2015，41（10）：3470-3478.
[4] 蔣小娟，張安，陳永，等.內部節點受限的最小生成樹問題算法研究[J].計算機工程與應用，2017（10）：35-37.
[5] 湯天波. Pathfinder算法優化研究[J].計算機應用與軟件，2015，32（11）：277-280.
[6] 王磊.最短路算法和最小生成樹算法在配電網絡重構中的應用研究[D].西安理工大學，2009.
[7] 胡藝文，崔勇，姬德森，等.基于prim和dijkstra組合算法的配電網新增容量規劃方法[J].中國農村水利水電，2015（6）：179-182.
[8] 趙林，朱桂斌，文玉強，等.基于最小生成樹的規則圖像碎片復原算法[J].計算機技術與發展，2016，26（6）：69-72.
[9] 宋國治，王鋮，涂遙，等.基于Prim初始種群選取優化遺傳算法的三維片上網絡低功耗映射[J].計算機應用，2017，37（1）：90-96.
【通聯編輯：王力】
