《最小生成树算法及其在天然气管道网中的应用研究》-工学论文，计算机论文-论文范文参考-科学狗论文网

标题

最小生成树算法及其在天然气管道网中的应用研究

范文

张淑萍

摘要：在城市的快速化建设发展中，天然气系统是非常重要的基础设施之一，是保障人民基本生活的物质基础。但是，天然气管网非常复杂，怎样合理设计其铺设布局，直接关系着整个系统的可靠性、安全性。利用生成树算法，可以将环状管网转化成树状管网，确定天然气管道的最短路线，进而优化天然气管道铺设方案。本文简单介绍了最小生成树算法及其在天然气管道铺设布局中的应用。

关键词：最小生成树;算法;天然气管道网;深度优先;遍历

中图分类号：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中以来表示，七个小区之间的距离连接如图1所示，为节约资金，需要设计最短线路，并且确保该线路能都连接7个小区，保证小区的天然气管道使用。

上图即为由点和边所构成的无项图，通常由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.

【通联编辑：王力】

随便看

科学优质学术资源、百科知识分享平台，免费提供知识科普、生活经验分享、中外学术论文、各类范文、学术文献、教学资料、学术期刊、会议、报纸、杂志、工具书等各类资源检索、在线阅读和软件app下载服务。