基于树普利母算法的通信网络规划

基于树普利母算法的通信网络规划

1运用c语言环境下的仿真研究方法在配电网架中的应用实例随着通信网络的需求的增加，通信网络的建立经济效益和工作效率的提高已成为通信网络建立的一个重要问题。对于复杂的通信网络构架,通信网络构架过程工作量大,若按照传统的方式进行构架,会造成构架效率低下,而且会对资源造成极大的浪费。针对既需要保证良好工作效率又需要提高经济效益实际需求,提出应用一种实用性很强的算法应用在网络通讯构架上,这种算法很好地被运用在配电网架扩展规划中。而本文重点该算法对通信网络架设进行总体分析最优动态规划,讨论网络规划中各个城市之间的线路权重的选取方法,设计适用于各个城市网络的节点-支路邻接表的数据存储结构具体实现仿真研究方法,最后在C语言环境下中实现,效果很好。实例仿真结果验证,该方法可有效减少资源浪费和提高计算速度的优点,这样的方法不仅可以有效提高通信网络架设经济效益,而且可以保证通信网络架设工作效率,此研究非常具有现实意义。2网络构建描述和算法描述2.1基于prim算法的通信网络架构仿真研究对于复杂的通信网络构架,只有采用合理的设计才能达到较好的目的与效果,否则不仅工作量大而且效率低下。针对既需要保证良好的工作效率,又需要提高经济效益的实际需求情况,在研究分析网络通信构架方案时,采用数据结构分析的方法,对通信网络构架进行动态规划,应用最小生成树的Prim算法,对通信网络架设分析,并且结合具体实例中的通信网络构架问题,实现具体仿真研究,最终达到规划设计合理的目的。2.2计算复杂度不同常用的构造最小生成树的方法有Prim算法和Kruskal算法,二者又有着区别。Prim算法的时间复杂度为O(n2),与图的边数无关,因此该算法适合于求边稠密的网的最小生成树。而克鲁斯卡尔算法的时间复杂为O(eloge),与图中的顶点数无关,因此该算法适合于求边稀疏的网的最小生成树。本题考虑在实际生活中可能有较复杂的网图,边有较多可能性。所以通信网络构架采用Prim算法。3成树tu,te设置对于通信网络构架过程规划应用Prim算法进行求解。首先必须了解Prim算法的基本思想:从顶点集V中任取一个顶点u1,将生成树T(U,TE)设置为仅有一个结点u1的树,即U={u1};只要U是V的真子集,就从所有u∈U,v∈V-U的边(u,v)中选取一条具有最小权值的边(u,v),将顶点v加入U中,将边(u,v)加入TE中。如此进行n-1次,每次往生成树里加入一个顶点和一条边,直到U=V时,最小生成树构造完毕,这时集合T中包含了最小生成树的n-1条边。3.1运用通信线路建造城市间的通信网络如图1Prim算法实现过程图所示。Prim算法实现过程是根据Prim算法的基本思想而产生的,具体的算法实现过程,以尽可能少的总造价建造城市间的通信网络,把n个城市联系在一起。在这n个城市中,任意两个城市间都可以建造通信线路,通信线路的造价依据城市间的距离的不同而不同;从而构造一个通信线路造价网络,在网络中顶点表示城市,顶点之间的边表示城市之间可构造通信线路,每条边的权值表示该条通信线路的造价,要想使总的造价最低,实际上就是寻找该网络的最小生成树。3.2最小代价生成树的选择问题在图论中,常常将树定义为一个无回路的连通图。一个连通图G的子图如果是一棵包含G的所有顶点的树,则该子图称为G的生成树(SpanningTree)。可以用连通网来表示N个城市以及N个城市间可能设置的通信线路,其中网的顶点表示城市,边表示两城市这间的线路,赋于边的权值表示相应的代价。对于N个顶点的连通网可以建立许多不同的生成树,每一棵生成树都可以是一个通信网。现在,我们要选择这样一棵生成树,也就是使总的耗费最少。这个问题就是构造连通网的最小代价生成树(MinimumCostSpanningTree)(简称为最小生成树)的问题。一棵生成树的代价就是树上各边的代价之和。构造最小生成树可以有多种算法。其中多数算法利用了最小生成树的下列一种简称为MST的性质:假设N=(V,{E})是一个连通网,U是顶点集V的一个非空子集。若(u,v)是一条具有最小权值(代价)的边,其中u∈U,v∈V-U,则必存在一棵包含边(u,v)的最小生成树。可以用反证法证明之。假设网N的任何一棵最小生成树都不包含(u,v)。设T是连通网上的一棵最小生成树,当将边(u,v)加入到T中时,由生成树的定义,T中必存在一条包含(u,v)的回路。另一方面,由于T是生成树,则T上必存在另一条边(u’,v’),其中u′∈U,v′∈V-U,且u和u′之间,v和v′之间均有路径相通。删去边(u′,v′),便可消除上述回路,同时得到另一棵生成树T′。因为(u,v)的代价不高于(u’,v’),则T′的代价也不高于T,T′是包含(u,v)的一棵最小生成树。由此和假设矛盾。即可得出N的任何一棵最小生成树都可能包含(u,v)。4例如，关于通信网络架构过程的实践研究4.1各城市之间通信网络的距离及每公里费用在掌握算法后,通过一个应用性的实例来针对通信网络构架实例,选择合适算法,进行详细分析。某省的七个城市需要架设通信网络系统,为连接这七个城市,每两个城市之间的距离如下表1所示。考虑地理环境的影响,综合考虑各城市之间的距离和每公里修建通信网络的费用,各城市之间修建网络每公里的费用可用与10000元之间的比较来估计(表2)。最终通过仿真研究说明,如何架设通信网络,使总费用最小。4.2各城市之间通信网络的费用为了便于求解此实际问题,首先,对本问题作如下假设:假设各城市之间架设网络每公里的费用等于或小于10000元,并对“完全是”,“可认为是”等对费用的描述以表3中的具体费用替代。表4为根据表3的费用假设后各城市之间架设通信网络的费用(单位:×102元/千米)。用连通网络表示七个城市以及七个城市间可能设置的通信线路,其中网的顶点表示城市,边表示两城市之间的线路,赋予边的权值表示相应的架设费用。具体的以R1~R7代表七个城市,R1~R7(各城市)之间以边相连,每条边代表七个城市间可能设置的通信线路,赋予边的权值表示相应的架设费用。4.3连通网络地的计算具体用Prim算法构造最小生成树的过程分为七个步骤,具体如下:STEP1,构造连通网N(V,E),(V表示顶点,E表示边)。TE是N上最小生成树中边的集合。形成如上图所示的无向连通网。构造连通网如图2所示。STEP2,从顶点集合U={R0}(R0∈V),边的集合TE{}开始,在所有R∈U,v∈V-U的边(R,v)∈E中找一条代价最小的边(R0,v0),把这条边并入集合TE,同时将v0并入集合U。构造连通网图选择了R1到R2路径。STEP3,因为U≠V,重复执行第二步操作。构造连通网图选择了R2到R5路径。STEP4,因为U≠V,重复执行第二步操作。构造连通网图选择了R5到R4路径。STEP5,因为U≠V,重复执行第二步操作。构造连通网图选择了R5到R3路径。STEP6,因为U≠V,重复执行第二步操作。构造连通网图选择了R5到R6路径。STEP7,因为U≠V,重复执行第二步操作。此时U=V,算法执行完毕。TE中必有6条边,则T=(V,TE)为N的最小生成树。构造连通网图选择了R6到R7路径。最后连通网如图3所示。由上述计算可得,使总费用最小的假设方案如图4所示。由此过程我们可以得出结论,若后选轻边集中的轻边不止一条,可任选其中的一条扩充到T中。连通网的最小生成树不一定是惟一的,但它们的权相等。最小的总费用为217400元。4.4运行界面及结果在C语言的运行环境下,调试运行程序后,输入图的顶点及边上的权值信息,当输入的两个顶点的编号为-1时结束。运行界面如图5所示。运行结果如图6所示。使用该算法不仅对于7个城市之间架设通信网络的问题可以求解,并且对于任意N(N<30)个城市之间的通信网络问题也可以解决,只要输入任意两城市间的距离或修建费用,就可以进行最小代价路径的生成。由运行结果可知,最小的总费用为217400元。5仿真与验证算法仿真过程运用了非常广泛应用的运筹学分支图与网络的基本概念与模型,具体应用了有向图与容量网络、流与可行流等概念以及最小生成树的思想来求解架设通信网络使总费用最小的实际问题。最终采用Prim算法,结合通信网络构架的实际