[工作范文]韦东华论文最终版.doc

《[工作范文]韦东华论文最终版.doc》由会员分享，可在线阅读，更多相关《[工作范文]韦东华论文最终版.doc（57页珍藏版）》请在三一办公上搜索。

1、沈阳建筑大学毕业论文毕 业 论 文 题 目 最小生成树问题在经济学中的应用 学院专业班级 理学院 信息与计算科学06-1班 学 生 姓 名 韦东华 性别 男 指 导 教 师 邢双云 职称 讲师 2010年 6 月 9日IV 摘要 在现实生活中，最小生成树有很高的实用价值。正确地理解掌握如何构造连通图的最小生成树问题，将会给我们带来巨大的经济效益和社会效益。随着最小生成树理论与算法的发展与完善，其在现实生活中的应用越来越广泛。求最小生成树问题能在很多经济学问题中得到很好的应用。因此，对最小生成树在具体的经济学案例中的应用进行研究和完善是必须的，并且有着很高的经济价值，如“最小投资”应用前景非常广

2、泛。 首先本文对Prim算法和Kruskal算法进行了分析研究，设计了它们的java语言程序，此程序可以寻找任意赋权连通图的最小生成树。 其次本文重点用Kruskal算法和Prim算法求解最小生成树算法，对构建最小投资中原城市群快速干线进行了理论研究。把中原城市群九城市及其间距离抽象成无向图，然后给出算法过程以及实质求解意义并获得结论。最后，对构建最小投资中原城市群快速干线的研究，采用了一种新的更为简便的算法-直接生成法。这种方法不需要画出原问题的网络图，只需根据各对象间的关系矩阵，直接得到最小生成树。关键词：最小生成树；Prim算法；Kruskal算法；直接生成法 Abstract In r

3、eal life, the minimum spanning tree has high practical value. Correctly understanding and grasping how to construct the minimum spanning tree problem connected network, will bring us huge economic and social benefits. With the minimum spanning trees theory and algorithm developing and improving, its

4、 application in real life is more and more wide. Minimum spanning tree problem can demand a lot of economic problems in the application well. Therefore, the minimum spanning tree in the specific case of the application of economics to study and perfection is a must, and has a high economic value, su

5、ch as minimum investment has an extensive application prospect. First, this paper has analyzed and studied Prim algorithm and Kruskal algorithm, and has designed their c language programs, their programs can search for any connected graph of minimum spanning tree empowerment. Furthermore, this paper

6、 focuses on using Kruskal algorithm and Prim algorithm for minimum production tree algorithm, and studies the minimum investment of the Construction of Fast Route to the urban agglomeration theory in the Central Plains. First using the concept of undirected graph to abstract Central Plains nine citi

7、es and their urban agglomeration distance map, and then give algorithms for solving process and the real meaning and the conclusions. Finally, to study the minimum investment of the Central Plains Construction of Rapid Link of Cities, applies a new algorithms - the more simple direct production meth

8、od. The method do not need to draw a network diagram of the original problem, only the relationship between objects according to the matrix, the smallest production of the tree directly.Key words: Minimum spanning tree；Prim algorithm；Kruskal algorithm；direct production method目录第一章 绪论11.1 图论的基本知识介绍11

9、.1.1 图论的概述11.1.2 树的概念及性质21.1.3 生成树的概念及性质21.1.4 最小生成树的概念及性质21.2 经济学的基本知识介绍31.2.1 经济学的概念31.2.2 经济学的研究对象31.2.3 经济学的研究方法31.3 本文的内容安排与主要创新点5第二章 Kruskal算法及实例分析62.1 引言62.2 Kruskal算法62.2.1 算法思想262.2.2 算法步骤362.3 实例应用72.3.1 Kruskal的图解说明472.3.2 Kruskal算法的计算机实现59第三章 Prim算法及实例分析113.1 引言113.2 Prim算法113.2.1 算法思想11

10、3.2.2 算法步骤113.3 实例应用123.3.1 Prim算法的图解说明123.3.2 Prim算法的计算机实现133.4 两种算法的比较14第四章 中原城市群轨道干线选择的研究154.1 引言154.2 问题的抽象和说明8154.2.1 理想状态下九城市间距离164.2.2 现实情况下九城市间距离184.2.3 关于轨道交通干线的修正194.2.4 关于算法所使用数据的选择194.3 用Kruskal算法求解204.3.1 算法的实质意义204.3.2 算法描述语言角度的求解过程204.3.3 算法实质意义角度的求解过程214.4 用Prim算法求解224.4.1 算法的实质意义224

11、.4.2 算法描述语言角度的求解过程224.4.3 算法实质意义角度的求解过程23第五章 直接生成法及其应用245.1 引言245.2 直接生产法的相关知识245.2.1 相关定理及推理245.2.2 直接生成法的思想及算法11255.3 用直接生成法求解265.3.1 构造九城市理想距离的上三角矩阵265.3.2 直接生成法求解过程275.4 算法改进295.4.1 求解的结论295.4.2 存在的不足和修正方法30第六章 总结与展望32参考文献33附录一1附录二10附录三15沈阳建筑大学毕业论文最小生成树问题在经济学中的应用第一章 绪论1.1 图论的基本知识介绍1.1.1 图论的概述 图论

12、（Graph Theory）是数学的一个分支。它以图为研究对象。图论中的图是由若干给定的点及连接两点的线所构成的图形，这种图形通常用来描述某些事物之间的某种特定关系，用点代表事物，用连接两点的线表示相应两个事物间具有这种关系。图论本身是应用数学的一部份，因此，历史上图论曾经被好多位数学家各自独立地建立过。关于图论的文字记载最早出现在欧拉1736年的论着中，他所考虑的原始问题有很强的实际背景。1859年，英国数学家哈密顿发明了一种游戏：用一个规则的实心十二面体，它的20个顶点标出世界著名的20个城市，要求游戏者找一条沿着各边通过每个顶点刚好一次的闭回路，即（绕行世界）。用图论的语言来说，游戏的目

13、的是在十二面体的图中找出一个生成圈。这个问题后来就叫做哈密顿问题。由于运筹学、计算机科学和编码理论中的很多问题都可以化为哈密顿问题，从而引起广泛的注意和研究。在图论的历史中，还有一个最著名的问题-四色猜想。这个猜想说，在一个平面或球面上的任何地图能够只用四种颜色来着色，使得没有两个相邻的国家有相同的颜色。每个国家必须由一个单连通域构成，而两个国家相邻是指它们有一段公共的边界，而不仅仅只有一个公共点。20世纪80-90年代曾邦哲的综合系统学（结构论）将“四色猜想”命题转换等价为“互邻面最大的多面体是四面体”。四色猜想有一段有趣的历史，每个地图可以导出一个图，其中国家都是点，当相应的两个国家相邻时

14、这两个点用一条线来连接，所以四色猜想是图论中的一个问题。它对图的着色理论、平面图理论、代数拓扑图论等分支的发展起到推动作用。1.1.2 树的概念及性质 树是图论中重要概念之一，它在计算机科学中应用非常广泛，这里将介绍树的一些基本性质和应用。一个连通且无回路的无向图称为树。树中度数为1的结点称为树叶，度数大于1的结点称为分枝点或内点。一个无回路的无向图称为森林，它的每个连通分图是树。给定图T，以下关于树的定义是等价的。(1)无回路的连通图。(2)无回路且，其中是边数，是结点数。(3)连通且。(4)无回路，但增加一条新边，得到一个且仅有一个回路。(5)连通，但删去任一边后便不连通。(6)每一对结点

15、之间有一条且仅有一条路。1.1.3 生成树的概念及性质 若图的生成子图是一棵树，则该树称为的生成树。设图有一棵生成树，则中的边称为树枝。图的不在生成树中的边称为弦。所以弦的集合称作生成树的补。连通图至少有一棵生成树。1.1.4 最小生成树的概念及性质假定是具有个结点的连通图。对应于的每一条边，指定一个正数，把称为边的权，（可以是长度，运输量，费用等）。的生产树也有一个树权，它是的所有边权的和。定义：在图的所有生成树中，树权最小的那棵生成树，称作最小生成树。MST性质：设是一个连通图，是顶点集的真子集。若是中一条“一个端点在中（例如：),另一个端点不在中的边（例如：),且具有最小权值，则一定存在

16、的一棵最小生成树包括此边。1.2 经济学的基本知识介绍1.2.1 经济学的概念 经济学（economics）是研究人类社会在各个发展阶段上的各种经济活动和各种相应的经济关系及其运行、发展的规律的科学。经济活动是人们在一定的经济关系的前提下，进行生产、交换、分配、消费以及与之有密切关联的活动，在经济活动中，存在以较少耗费取得较大效益的问题。经济关系是人们在经济活动中结成的相互关系，在各种经济关系中，占主导地位的是生产关系。经济学是对人类各种经济活动和各种经济关系进行理论的、应用的、历史的以及有关方法的研究的各类学科的总称。经济学又可称为经济科学（economic sciences）经济学（eco

17、nomics）即：经世济民的科学。是研究人类个体及其社会在自己发展的各个阶段上的各种需求和满足需求的活动及其规律的学科。1.2.2 经济学的研究对象经济学研究的三个基本问题: (1)生产什么以及生产多少。生产电视还是生产电脑、生产大炮还是生产黄油（希特勒的选择是：宁要大炮不要黄油）；生产多少台电视机、多少台电脑，用多少资源生产大炮，用多少资源生产黄油。 (2)怎样生产。用什么样的方法来生产这么多的产量与劳务，与生产方式，技术水平直接有关。 (3)为谁生产。生产出来的产量和劳务用什么样方式分配到社会的各个成员中，即怎样分配。经济学除了上述的三个基本问题外，还研究以下三方面的内容： (1) 社会稀

18、缺的资源是否得到充分使用。 (2) 社会资源总量的变动。 (3) 货币的稳定性。1.2.3 经济学的研究方法经济学有一套以数量分析为特征的分析方法。主要有：实证分析法、边际分析法、均衡分析法、静态分析法、比较静态分析法、动态分析法、长期与短期分析法、个量与总量分析法等。(1)实证分析法： 经济学中的实证分析法来于哲学上的实证主义方法。实证分析是一种根据事实加以验证的陈述，而这种实证性的陈述则可以简化为某种根据经验数据加以证明的形式。在运用实证分析法来研究经济问题时，就是要提出用于解释事实的理论，并以此为根据做出预测。这也就是形成经济理论的过程。(2)边际分析法：边际分析法是利用边际概念对经济行

19、为和经济变量进行数量分析的方法。所谓边际，就是额外或增加的意思，即所增加的下一个单位或最后一个单位。在经济学分析中，简单地说，边际是指对原有经济总量的每一次增加或减少。严格地说，边际是指自变量发生微小变动时，因变量的变动率。(3)均衡分析法： 均衡本来是物理学概念。引入经济学后均衡是指经济体系中各种相互对立或相互关联的力量在变动中处于相对平衡而不在变动的状态。对经济均衡的形成与变动条件的分析，叫做均衡分析法。分为局部均衡分析和一般均衡分析 局部均衡分析法，是在不考虑经济体系某一局部以外的因素的影响的条件下，分析这一局部本身所包含的各种因素相互作用中，均衡的形成与变动的方法。一般均衡分析法，是相

20、对与局部均衡分析法而言的。它是分析整个经济体系的各个市场、各种商品的供求同时达到均衡的条件与变化的方法。(4)静态分析法 静态分析法是完全抽象掉时间因素和经济变动过程，在假定各种条件处于静止状态的情况下，分析经济现象的均衡状态的形成及其条件的方法。 (5)比较静态分析法 比较静态分析法是对个别经济现象的一次变动的前后，以及两个或两个以上的均衡位置进行比较而撇开转变期间和变动过程本身的分析方法。 (6)动态分析法 动态分析法是考虑到时间因素，把经济现象的变化当作一个连续过程，对从原有的均衡过度到新的均衡的实际变化过程进行分析的方法。1.3 本文的内容安排与主要创新点本文共计七章第一章 重点介绍了

21、图论的相关知识，以及树的有关概念。同时也介绍了经济学有关的知识，包括经济学的研究对象，研究方法等。 第二章 本章在对Kruskal算法分析的基础上，设计了该算法的Java语言程序，并通过对分公司及总公司间架设网络的实例研究来说明该算法的应用。第三章 本章在对Prim算法分析的基础上，设计了该算法的Java语言程序，并通过对分公司及总公司间架设网络的实例研究来说明该算法的应用。第四章 主要用Kruskal算法和Prim算法对中原城市群间的轨道干线选择进行了研究，找出最优干线图。第五章 本章用了一种新的算法对中原城市群间轨道干线选择问题进行了研究，此方法不需要画出网络分布图，既是直接生成法。本章也

22、是论文的重点部分。第六章 本章主要介绍了动态规划思想，同时用此思想对中原城市群轨道干线问题进行了实际的优化，从现实的角度更优化了干线方案。第七章本章为总结与展望部分。本文的主要创新之处有以下几点:(1)通过对Kruskal算法与Prim算法的研究分析，对这两种算法做了比较。(2)利用Prim算法对中原城市群轨道干线问题进行研究，找出了最优干线图。(3)本文最大的创新是利用了直接生成法对中原城市群轨道干线问题进行研究。第二章 Kruskal算法及实例分析2.1 引言 目前，求最小生成树的算法已经相当成熟，常用的经典算法1有避圈法(Kruskal算法)、边割法(Prim算法)、破圈法、Sollin

23、算法、Dijkstra算法等。本章在对Kruskal算法分析的基础上，设计了该算法的Java语言程序，并通过对分公司及总公司间架设网络的实例研究来说明该算法的应用。2.2 Kruskal算法2.2.1 算法思想2 Kruskal 算法每次选择条边，所使用的贪婪准则是：从剩下的边中选择一条不会产生环路的具有最小耗费的边加入已选择的边的集合中。注意到所选取的边若产生环路则不可能形成一棵生成树。Kruskal算法分步，其中是网络中边的数目。按耗费递增的顺序来考虑这条边，每次考虑一条边。当考虑某条边时，若将其加入到已选边的集合中会出现环路，则将其抛弃，否则，将它选入。2.2.2 算法步骤3Step1

24、把的边按权值由小到大排序，即。令。Step2 若含有回路，则执行Step3；否则执行Step4。Step3 置,若，则执行Step2；否则停止，中不存在最小生成树。Step4 令，并置。Step5 若，则结束，是最小生成树；否则执行Step3。2.3 实例应用某公司规模不断扩大，在全国各地设立了多个分公司，为了提高公司的工作效率使各分公司之间的信息可以更快、更准确的进行交流，该公司决定要在各分公司之间架设网络，由于地理位置和距离等其它因素，使各分公司之间架设网线的费用不同，公司想使各分公司之间的网络畅通并且把费用降到最低，那么应该怎样来设计各分公司及总公司间的线路？该公司的所有分公司及总公司的

25、所在位置如图2-1所示。顶点代表位置及名称，边代表可以架设网线的路线，边上的数字代表架设该网线所需要的各种花费的总和。这样就构成了一个赋权连通图，从而问题就转化为求所得到的赋权连通图的最小生成树。图2-1分公司及总公司间架设网络的布线图3678452163642510181252.3.1 Kruskal的图解说明4 根据2.2.2的算法步骤来进行图解说明： （1）Step1 建立边由小到大的顺序表2-1各边权值排序 边 （5,8）（2,4）（3,6）（4,7）（1,2）（6,7）（1,3）（3,4）（4,5） （7,8） （2,5） 权值 1 2 3 4 5 5 6 6 8 10 12（2）S

26、tep2 取出（5,8），不形成回路，转Step4，将该边存入中，得到(图2-2） 图2-2 Kruskal算法图解 边 权值 MST边 （5,8） 1 要 （2,4） 2 要 （3,6） 3 要 （4,7） 4 要 （1,2） 5 要 （6,7） 5 要 （1,3） 6 不要 （3,4） 6 不要 （4,5） 8 要 （7,8） 10 不检查 （2,5） 12 不检查852746311（3）由于，即，转Step3； 图2-3 Kruskal算法图解852746315281543（4）经过九次迭代后，Step2取出（4，5），不形成回路，转Step4，将该边存入中，得到，如图2-3所示。 （5

27、）Step5 由7=7，即，结束。表2-2 各边的选取情况 边 权值 MST边 （5,8） 1 要 （2,4） 2 要 （3,6） 3 要 （4,7） 4 要 （1,2） 5 要 （6,7） 5 要 （1,3） 6 不要 （3,4） 6 不要 （4,5） 8 要 （7,8） 10 不检查 （2,5） 12 不检查2.3.2 Kruskal算法的计算机实现5 Step1 输入图的顶点数及边数； Step2 将图的各边端点及权值输入； Step3 程序的运行结果为： the set of the minimum spanning tree of the graph： edge(5，8)，right

28、：l edge(2，4)，right：2 edge(3，6)，right：3 edge(4，7)，right：4 edge(1，2)，right：5 edge(6，7)，right：5 edge(4，5)，right：8 the sum of right of the graph：28 Step4 所得最小生成树如图2-4。图2-4 Kruskal算法得最小生成树 852746315281543第三章 Prim算法及实例分析3.1 引言目前，求最小生成树的算法已经相当成熟，常用的经典算法1有避圈法(Kruskal算法)、边割法(Prim算法)、破圈法、Sollin算法、Dijkstra算法等。

29、本章在对Prim算法分析的基础上，设计了该算法的Java语言程序，并通过对分公司及总公司间架设网络的实例研究来说明该算法的应用。3.2 Prim算法3.2.1 算法思想任意选取一节点构成集合,然后不断在中选一点到中某点（如：）权最小的边加入树T中，并令直至。3.2.2 算法步骤Step1 设为的任一顶点，令。Step2 若，结束，以为顶点集，为边集的图即是的最小生成树；否则执行Step3。Step3 构造,若=,则不连通，停止；否则，设， ，令，置，执行Step2。 3.3 实例应用同样是对第二章的分公司及总公司间架设网络问题的进行研究与说明。3.3.1 Prim算法的图解说明 1Step1

30、= ,；Step2 由，转Step3； 1 2 3 4 5 6 7 8 图3-1 Prim算法图解21Step3 2图3-2 Prim算法图解125选出最小者（1,2），权值为5，并将 添加到点集中，得到；将（1,2）存入中得,如图3-2所示。 :12 = , 1 2 4 7 6 3 5 8图3-3 Prim算法图解852746315281543经过七次迭代后，即得到该图的最小生成树，如图3-3所示。 3.3.2 Prim算法的计算机实现Step1 输入图的顶点数；Step2输入图的邻接矩阵；Step3最后得到的结果为：the set of eht minimum spanning tree

31、of the graph：path 1：from vertex 1 to vertex 2right：5path 2：from Vertex 2 to vertex 4right：2path 3：from vertex 4 to vertex 7，right：4path 4：from vertex 7 to vertex 6，right：5path 5：from vertex 6 to vertex 3，,49ht：3path 6：from vertex 4 to vertex 5，right：8path 7：from vertex 5 to vertex 8，right：1the sum r

32、ight of the minimum spanning tree of the graph：28Step4所得最小生成树如图3-4。图3-4 Prim算法得的最小生成树852746315281543 3.4 两种算法的比较从两种算法的实现步骤可以看出，Prim算法实现起来简捷清晰，并且使用的判断语句较少，而Kruskal算法实现起来相对来说步骤多、判断语句多；再由两种算法的图解可以看出Prim相对来说更清晰、更易实现和理解；从结果来看，利用Prim算法从顶点出发求出用邻接矩阵来表示图的最小生成树与利用Kruskal算法求结构体数组所示图的最小生成树是一致的；由程序本身可以看出Kruskal算

33、法与顶点数无关，所以适合求边稀疏的网络的最小生成树，而Prim算法与边数无关，所以适合求边稠密的网络的最小生成树。第四章 中原城市群轨道干线选择的研究 4.1 引言目前，在中部崛起经济发展战略指导下，建设和发展中原城市群，已成为河南省经济发展战略的重要组成部分。发达的交通网络，对于河南省经济发展和中原城市群迅速崛起将起到积极、巨大的推动作用。大力发展轨道交通已经成为解决城市内和城际间人员流动量大与交通设施运载力不足之间矛盾的主要途径，规划建设城际间快速轨道交通已经成为城市群城镇体系和经济发展的迫切需要6。本章应用计算机学科的图论中用于求解无向图中的最小生成树的Kruskal算法与Prim算法，

34、从最小投资角度出发，求解中原城市群九城市间快速轨道交通干线的构建问题，提供干线运输服务7，即新建一条客运专用轨道交通快速通道，其建成目标：连接中原城市群九城市；投资最少、造价最低、总道路长度最短；与省内原有航空、铁路、公路交通网络相辅相成，实现轨道交通客货分离。这是将计算机学科的算法应用于解决现实问题的尝试，对于解决现实生活中类似问题有着深远的指导意义。4.2 问题的抽象和说明8从计算机学科图论的角度来看，在现实世界的若干事物(有限或无限)或社会上的若干现象之间均存在着某种联系。对于中原城市群快速轨道交通干线问题，可以用小圆圈表示城市，用边表示城市之间联通道路，边上的权是用以表示两地间距离的公

35、里数。网络的构成可采用点-点邻接关系来描述9。由于边的权决定了路线选择的结果和最终轨道干线的投资，因此，必须认真探讨中原城市群九城市之间的距离问题，综合考虑理想状态和现实情况的影响。中原城市群包括郑州、洛阳、开封、新乡、焦作、许昌、平顶山、漯河、济源九城市(图4-1)。 图4-1 中原城市群九城市的地理位置4.2.1 理想状态下九城市间距离 首先从理想状态下,无向完全图角度来看中原城市群九城市间距离。无向完全图是指：图中顶点和顶点间的边没有方向性；图中任意2个顶点之间均有边相连。如果考虑一种比较理想状态下的城市连通网络，在具有9个顶点(也即9个城市)的情况下，应该有个边(也即交通连线)将任意顶

36、点连接。在理想状况下，中原城市群九城市间距离为不考虑河流、山川等因素影响的直线距离(表4-1)。其中：表中城市后边字母分别为该城市的汽车牌照代码。 表4-1 中原城市群九城市间理想(直线)距离 km 城市郑州A开封B洛阳C平顶山D新乡G焦作H许昌K漯河L济源U郑州A - - - - - - - - -开封B 60 - - - - - - - -洛阳C 130 170 - - - - - - -平顶山D 120 155 135 - - - - - -新乡G 65 70 150 185 - - - - -焦作H 70 115 100 175 55 - - - -许昌K 85 100 150 55

37、145 150 - - -漯河L 140 145 200 65 195 180 55 - -济源U 105 165 60 170 120 60 170 215 - 理想状态下，两两城市之间均存在直线连接的交通道路，根据表4-1中的中原城市群两两城市之间的直线距离，可以得到城市群的交通道路抽象图(图4-2)。 图4-2 中原城市群九城市间交通道路理想状态抽象图4.2.2 现实情况下九城市间距离在实际生活中，不是任意两城市间都有直线连通的交通线路。如郑州-济源就不存在直达道路，可以通过中转城市到达目的地。可以选择济源-焦作-郑州或济源-洛阳-郑州两条线路。同样地，郑州-平顶山可考虑郑州-许昌-平顶

38、山、郑州-漯河则必须选择郑州-许昌-漯河线路。基于这种现实情况，中原城市群九城市间现实距离如表4-2。 表4-2 中原城市群九城市间现实距离 km城市郑州A开封B洛阳C平顶山D新乡G焦作H许昌K漯河L济源U郑州A - - - - - - - - -开封B 60 - - - - - - - -洛阳C 130 170 - - - - - - -平顶山D 120 180 130 - - - - - -新乡G 65 70 175 185 - - - - -焦作H 70 130 95 190 55 - - - -许昌K 80 100 140 55 145 150 - - -漯河L 135 140 195 65 200 205 55 - -济源U 130 190 60 190 115 60 200 255 - 结合现实道路连通情况，对中原九城市间交通道路图进行图论抽象，获得了现实距离无向图(图4-3)。在图4-3中，不仅可以看到中原城市群所处的大致地理方位，亦可得知其间道路连通及其间距离的大致情况。 图4-3 中原城市群九城市间现实距离抽象图LDKBA