最小生成树算法及其在企业生产计划中的应用

VIP免费

3.0 韩鲁英 2024-09-24 4 4 1.46MB 38 页 150积分

侵权投诉

浙江财经学院本科生毕业论文（设计）

最小生成树算法及其在企业生产计划中的应用

摘要：宽带网络是中国电信赖以生存发展的根本，是中国电信在全业务经营时期打

造差异化竞争优势的基础保证。在国家加快推进三网融合的战略背景下，光纤到户成为

有线接入通信网络的长远发展目标，也是电信运营商实现三网融合的主要解决方案。本

文从计算机学科——图论的角度入手，利用 Kruskal 求解最小生成树的算法，对构建贵

州省贵阳市小河区电信网络线路干线进行研究。我们利用无向图的概念对小河区带主要

网点及其距离进行网络的抽象，然后设计出相应的有效算法，给出其实质求解意义，并

最终得出结论。本文的结论可作为贵州省贵阳市小河区未来电信网络线路布线的参考。

关键词：最小生成树；Kruskal 算法；AutoCAD；电信网络

The Minimum Spanning TreeAlgorithm and its Application in the Plan of

the Enterprise Production

Abstract：The broadband network is the foundation of China Telecom. It is the basic

guarantee for China Telecom to gain differentiation competitive advantage during the full

service period. Presently, under the strategic background that our country accelerates the

cooperation of three nets, Fiber to the Home, as the long-term developmental goal for cable

access communication network, is the main solution for Telecom operators to realize the

cooperation between three nets. From the perspective of Graph theory of computer science,

and according to Kruskal’s Minimum Spanning Tree algorithm , this article conducts a

research of telecommunications network trunk lines which belong to Telecommunications

network of Xiaohe district, Guiyang, Guizhou province. First of all, to abstract the graph of

the main networks in Xiaohe district and their distance, according to the concept of graph.

Then to provide the algorithm process, its essential algorithm significance and give a

conclusion. The conclusion of this paper can be used as circuit wiring reference to the future

telecommunication network of Xiaohe district.

Key words：minimum spanning tree; Kruskal algorithm;autoCAD; telecommunications

network

Generated by Foxit PDF Creator © Foxit Software

http://www.foxitsoftware.com For evaluation only.

浙江财经学院本科生毕业论文（设计）

1引言............................................................................................................................. 1

2关于最小生成树的基本概念和定理............................................................................... 1

2.1 运筹学基础知识................................................................................................... 1

2.2 图论基础知识....................................................................................................... 2

2.3 图的基本概念....................................................................................................... 2

2.4 最小生成树........................................................................................................... 3

3最小生成树的两种算法...................................................................................................4

3.1 Kruskal 算法..........................................................................................................4

3.2 Prim 算法.............................................................................................................. 5

4贵州省贵阳市小河区电信网络布线研究........................................................................6

4.1 贵阳市小河区电信网络目前执行方案.................................................................6

4.1.1 主干层规划方案和投资............................................................................. 7

4.1.2 配线层规划方案和投资............................................................................. 9

4.1.3 引入层规划方案和投资............................................................................. 9

4.1.4 入户光缆规模及投资................................................................................. 9

5基于最小生成树的贵阳市小河区电信网络优化............................................................ 9

5.1 对贵阳市小河区电信网络问题的抽象说明......................................................... 9

5.2 理想状态下小河小河区的网络模型建立........................................................... 11

5.3 Kruskal 算法及求解........................................................................................... 14

5.3.1 Kruskal 算法的描述及实质......................................................................18

5.3.2 Kruskal 算法的求解过程.........................................................................19

6结论分析........................................................................................................................26

参考文献............................................................................................................................. 27

致谢词................................................................................................................................. 36

Generated by Foxit PDF Creator © Foxit Software

http://www.foxitsoftware.com For evaluation only.

浙江财经学院本科生毕业论文（设计）

1引言

随着当今社会信息化程度的不断加剧，计算机网络已经逐渐覆盖到人们生活的每一

个领域，因而计算机网络的优化成为可持续发展模式下的一个热门问题。作为网络优化

中的一个重要工具—最小生成树，在交通网、电力网、电信网络、管道网等设计中均有

广泛的应用，所以如何通过利用最小生成树对各种网络问题进行优化成为各企业、各部

门关心的话题。2010 年1月13 日，国务院常务会议决定加快推进电信网、广播电视网、

互联网三网融合，并审议通过了推进三网融合的总体方案，三网融合已经进入了实质性

推进阶段。同时，我们知道宽带网络是中国电信赖以生存发展的根本，如何在三家网络

中保持竞争优势，如何以更加节约资源的设计方案独占鳌头，是中国电信在全业务经营

时期打造差异化竞争优势的基础保证。

假设一家电信公司需要在

个地区之间建立电信网络，由图论知识我们知道至少需

要

−

条线路来连接这

个地区,那么如何在最节省经费的前提下建立这个电信网络

呢？因为在任意两个地区之间可以连接一条路径，每条路经有一定的长度，因而这

个

地区之间最多可以连接

( 1) 2

−n n 条路径。电信公司建立网络的问题关键是如何在保证

个城市之间连通性的前提下，使得网络建设费用最小。此时，我们可以将

个地区间的

连通网络用一个连通图

( , )

G V E

来表示,其中每个地区用图的顶点表示,地区间的路

径用边表示，我们利用赋于边的权值的方式来表示两个地区间的路经长度。由图论知识，

可知任何一个连接

个顶点的连通图至少有 n-1 条边（此时为图

的一棵生成树）。但是

在一个连通网络中，生成树是不唯一的,任何一棵生成树都可以作为一个电信网络。此

时，我们将利用图中每条边的权值。因为图

的每条边具有一定的权值,生成树上所有

边的权值之和称为生成树的费用。最小生成树( Minimum Cost Spanning Tree) 就是其中

费用最小的生成树。构造最小生成树可以有多种算法,常用的有两个：Prim 算法和

Kruskal 算法。本文主要通过利用 Kruskal 算法的实现来设计贵州省贵阳市小河区电信网

络设计的最小费用方案。

2关于最小生成树的基本概念和定理

2.1 运筹学基础知识

运筹学是 20 世纪 30-40 年代发展起来的一门新兴学科。该学科的研究对象是人类

对各种资源的运用及筹划决策问题，该学科的研究目的在于了解和发现这种运用及筹划

Generated by Foxit PDF Creator © Foxit Software

http://www.foxitsoftware.com For evaluation only.

浙江财经学院本科生毕业论文（设计）

决策活动的基本规律，以便发挥有限资源的最大效益，从而实现总体最优的目标。

运筹学在自然科学、社会科学、工程技术生产实践、经济建设及现代化管理中有着

重要的意义。随着科学技术和社会经济建设的不断进步，运筹学得到迅速的发展和广泛

的应用。作为运筹学的重要组成部分—网络最优化问题已成为当今社会的热门问题。网

络问题在各种实际背景问题中以各种各样的形式存在，交通、电子和通讯网络遍及人们

日常生活的各个方面，网络规划也广泛应用于解决不同领域中的各种问题，如：生产、

分配、项目计划、厂址选择、资源管理和财务策划等。网络规划为描述系统各组成部分

之间的关系提供了非常有效的直观和概念上的帮助，广泛应用于科学、社会和经济活动

的各个领域中。

运筹学的理论和方法具有以下特点：运筹学解决问题的基本方法是最优化理论和技

术，从系统的观点出发，以整体最优为目标，研究各组成部分的功能及其相互间的影响，

协调各部门之间的关系，找出使问题获得最佳效果、最优解答或者付诸实施的最好行动

方案。

2.2 图论基础知识

图是一种数据元素之间具有多对多关系的非线性数据结构，图中的每个元素可有多

个前驱元素和多个后继元素，任意两个元素都可以相邻。图是刻画离散结构的一种有力

工具。在运筹规划、网络研究和计算机程序流程分析中，都存在图的应用问题，在生活

中，我们经常用图来表达文字难以描述的信息，如城市交通图，线路图、网络图等等。

2.3 图的基本概念

1．图：图是由表示具体事物的点（顶点）的集合 1 2

{ , , }

V v v v

和表示事物之间关

系的边的集 1 2

{ , , , }

E e e e

所组成，且

中元素

是由

中的无序元素对

( , )

i j

v v

表示，

即

( , )

i j

e v v

，并称这类图为无向图，记为

( , )

G V E

。若

中任意两点

u v

都连通，即

u v

之间存在一条链，则称

为连通图，否则称为非连通图。

2．链：无向图中一个顶点与边交错而成的非空有限序列称为链，若链中无重复的

顶点，则称该链为初等链。

3．圈：若有一条链的起始顶点和终止顶点相同，称该链为圈。

4．路：无重复点的简单链叫做路。如图 2.1，首尾相连的路叫做回路，如图 2.1

中的 DEF 称为一回路。

5．若

中任意两点

都连通，即

之间存在一条链，则称

为连通图，否则

称为非连通图。

http://www.foxitsoftware.com For evaluation only.

文档加载中……请稍候！
如果长时间未打开，您也可以点击刷新试试。

下载文档到电脑，查找使用更方便

150 积分 4人已下载

立即下载 VIP免费下载

摘要：

mYl_�"~Ï[f–bg,yÑukÕN‹ºe‡ÿ‹¾‹¡ÿIg\ubh{—lÕSÊQvW(ONuN§‹¡RN-v„^”u(dX‰�ÿ[½^&Q~Üf/N-Výu5Oá�VNåu[XSÑ\Uv„h9g,ÿf/N-Výu5OáW(QhNR¡~Ï„%eögbS�]î_SzÞN‰OR¿v„Wúx@OÝ‹Á0W(Vý[¶R _ëc¨�ÛNQ‡�Tv„bue€ÌfoNÿQI~¤R0b7bN:g~¿c¥Qe�OáQ~Üv„•�ÜSÑ\UvîhÿN_f/u5Oá�Ð„%UF[žs°NQ‡�Tv„N;‰�‰ãQ³e¹hH0g,e‡NÎ‹¡{...

展开>> 收起<<

最小生成树算法及其在企业生产计划中的应用.pdf

共38页,预览4页

还剩页未读，继续阅读

最小生成树算法及其在企业生产计划中的应用

相关推荐

开通VIP享超值会员特权

作者详情

相关内容

推荐作者

热门标签

举报选择: