通信网络的设计问题

《通信网络的设计问题》由会员分享，可在线阅读，更多相关《通信网络的设计问题（25页珍藏版）》请在装配图网上搜索。

1、-通信网络的设计问题摘 要本文针对通讯网络设计问题，使用图论中最小生成树法、节点排除法、网络故障分析法、比照分析法等方法，分别构建普里姆prim模型、节点故障模型、链路故障模型等模型，使用Matlab软件编辑算法，得到通讯网络总费用最省的铺设方案、可靠性条件下最省铺设方案以及综合条件下最省铺设方案。针对问题一要求，具体要求为使得通信网络的总铺设费用最省，首先使用了简化模型分析、反证法等方法，证明最小生成树算法能测算无向图遍历节点的最省方案，其次应用最小生成树法中的普里姆prim算法构造通讯网络总费用最省模型使用Matlab软件编程，得到最优铺设方案并作图。针对问题二要求任意一个结点出现故障时，

2、其它结点间仍然能够保持通信畅通的可能性都到达90%时最省铺设方案设计问题，首先使用节点排除法进展处理，找到重要节点，利用树图将节点分类，再通过分类失效节点与有效节点连接到达通畅性要求，最后使用Matlab软件编程得出节点故障模型下最省铺设方案。针对问题三要求，任意一条链路被破坏时，能够保持通信畅通的结点都能够到达90%时最省铺设方案设计问题，首先找到重要链路，并分析链路影响的节点，用树图将节点分类，再通过分类失效节点与有效节点连接到达通畅性要求，最后使用Matlab软件编程得出链路故障模型下最省铺设方案。针对问题四要求，综合考虑网络的可靠性以及铺设费用确定合理的铺设方案问题，首先比照分析问题二

3、与问题三的节点分类，得出节点稳定性比链路稳定性更重要的结论；再通过节点故障模型分别构造通信畅通的可能性都到达85%、90%、95%时所对应的最低铺设费用，使用Matlab软件编程，得到综合考虑下的铺设方案。本文后续对模型进展了误差分析。还基于对问题四中可靠性不仅仅与节点和链路的稳定性有关，还与节点的度有关，故引进节点的度对模型进展改良，并利用蚁群算法建立综合目标下的铺设模型；最后对模型做出了纵向的推广和横向的推广。关键词：网络通讯设计；最小生成树法；故障分析法；蚁群算法；matlab1 问题的重述一、背景知识传统的通信网络是由传输、交换和终端三大局部组成。传输是传送信息的媒体，交换是各种终端交

4、换信息的中介体，终端是指用户使用的话机、手机、 机和计算机等。现代电信网是由专业机构以通信设备硬件和相关工作程序软件有机建立的通信系统，为个人、企事业单位和社会提供各类通信效劳的总和。现在计算机网络技术在各个领域的应用围已经逐步广泛起来，其开展也在不断的推动人类社会逐渐走向信息时代。网络技术的开展不仅促进了社会生产力的提高，也为人们的生活带来了很大的方便。然而，与此同时也存在着很多缺乏，诸如平安隐患、信息漏洞等，这些对于人们的工作和生活造成了很大的影响。我们在需要在研究通信网络铺设问题时的费用问题时，也要充分考虑其的可靠性。可靠性是其重要的整体指标，通信网络的可靠性不仅与通信设备、链路有关，而

5、且还与网络构造有关。由于网络构造的复杂多变，通信网络的可靠性分析一直是个棘手的问题。二、相关资料180个节点之间的距离表和铺设线路的单位费用表见附表1；三、要解决的问题问题1要使得通信网络的总铺设费用最省，请建立问题的数学模型，设计求解算法，给出铺设方案，并讨论方案的可靠性；问题2考虑到通信网络结点的可靠性，假设要求任意一个结点出现故障时，其它结点间仍然能够保持通信畅通的可能性都到达90%，请建立问题的数学模型，设计求解算法，并给出使总铺设费用最少的铺设方案；问题3：考虑到通信网络链路的可靠性，假设要求任意一条链路被破坏时，能够保持通信畅通的结点都能够到达90%，请建立问题的数学模型，设计求解

6、算法，并给出使总铺设费用最少的铺设方案；问题4：综合考虑网络的可靠性以及铺设费用，试确定合理的铺设方案。2 问题的分析一、问题的总分析对于问题的总分析，可以给出四个问题整体框架图，见图1图1 四个问题的整体框架图二、对具体问题的分析1对问题一的分析*通信公司拟建一个具有80个结点的通信网络，需要在这些结点之间铺设线路，进展数据传输。我们需要根据附件容建立数学模型，并设计算法使得通信网络的总铺设费用最省，并证明可靠性。我们引入图论中普里姆算法Prim算法，算法对通信网络的每条路的铺设费用总额进展模拟测算，形成铺设费用的最小生成树，并通过简化模型进展检验算法的可靠性。2对问题二的分析问题要求这80

7、个节点任意一个节点出现故障时，其它节点间仍然能够保持通信畅通的可能性都到达90%，在问题一所得出的最小生成树的的根底上，假设其中只有一个重要节点发生故障时，会造成八个节点以上故障，则通信畅通的可能性就不能到达90%，故通过节点删除法找到重要节点，再从重要节点引起故障的其他失效节点中找到一个节点与其他正常节点连通使得发生故障的节点数少于八个即可，并且改良方案所铺设的费用是最省的。3对问题三的分析问题要求79个链路中任意一条链路被破坏时，能够保持通信畅通的节点都能够到达90%。同样在问题一所得出的最小生成树的的根底上，我们考虑到假设其中只要有一个重要链路被破坏时，会造成八个节点以上故障，则通信畅通

8、的可能性就不能保证到达90%，所以，我们可以通过逐个分析每条链路，找到重要链路，一个链路被破坏会使最小生成树分割成两个局部，其中一局部则是失效的，然后再从重要链路被破坏而引起的其他失效节点中找到一个节点与其他正常节点连通使得发生故障的节点数少于或等于八个，我就能保证通信畅通的可能性到达90%，并且我们要找到的这个节点与其他正常节点连通所铺设的费用是最省的。4对问题四的分析问题要综合考虑网络的可靠性以及铺设，试确定合理的铺设方案。首先比照分析问题二与问题三的节点分类，发现问题三中节点的分类包含了问题二中节点的分类，假设满足了了节点稳定性的要求，则一定能满足链路稳定性的要求，故得出节点稳定性比链路

9、稳定性更重要的结论；再通过节点故障模型分别构造通信畅通的可能性都到达85%、90%、95%时所对应的最低铺设费用，使用Matlab软件编程，综合考虑稳定性和铺设费用得出铺设方案。3 模型的假设1 两个节点之间的费用仅由节点之间的距离和铺设线路的单位费用决定；2 各节点和各链条间发生故障是相互独立的，节点1发生故障不影响节点2发生故障；3每个节点的重要性是相等的，不存在次级差异；4任意两个节点之间可以进展连接，且一个节点可以连接的节点不受限制；5网路的稳定性与节点所连的链路条数无关，即每个节点和链路出现故障的可能性是相等的；4 名词解释与符号说明一、名词解释1最小生成树：一个有 n 个结点的连通

10、图的生成树是原图的极小连通子图，且包含原图中的所有 n 个结点，并且有保持图连通的最少的边。2普里姆算法Prim算法指可在加权连通图里搜索最小生成树。意即由此算法搜索到的边子集所构成的树中，不但包括了连通图里的所有顶点，且其所有边的权值之和亦为最小。二、主要符号说明序号符号符号说明1表示加权连通图的节点集合2表示加权连通图的边集合3表示集合中的任意节点4表示初始的节点集合5表示集合中的元素6表示中的节点但不是中的节点7表示一个0、1变量，0，1分别表示选中和未选中8表示节点i到节点j铺设线路所花费的费用9Z表示所选的铺设方案所花费的总费用10表示最小生成树的链路5 模型的建立与求解一、问题一的

11、分析与求解1问题的分析问题要求根据附件容建立数学模型，并设计算法使得通信网络的总铺设费用最省，并证明可靠性；我们引入图论中普里姆算法Prim算法，算法对通信网络的每条路的铺设费用总额进展模拟测算，形成铺设费用的最小生成树，并通过简化模型进展检验算法的可靠性。本文中连通图的顶点为80个通讯网络的节点，所有边的权值为两节点之间的铺设通讯链路的总费用，通过普里姆算法可以得出联通所有顶点并且使总铺设费用最低的树图，即相对于问题一的最优铺设方案。2问题的求解模型总铺设费用最省模型 模型的建立普里姆算法Prim算法的步骤：从单一点开场，普里姆算法按照以下步骤逐步扩大树中所含节点的数目，直到遍历连通图的所有

12、节点。首先设加权连通图的节点集合为，边集合为，初始化，其中为集合中的任意节点，其次在集合中选取权数最小的边，其中为集合中的元素，而不是，如果存在权数一样的可任选其中之一，再次，将参加到，重复第二第三步，直到。引入一个变量，时说明该路径未被选中，1则表示被选中为总结点数建立的数学模型如下算法流程图见图2图2 问题一的算法流程图为了更好的表现算法容，用以下简化模型来表示并验证：表1普里姆算法例如图设置一个加权连通图，顶点集合为，边集合为。为顶点，连线为边,边上数字为权值选择顶点集合中任意顶点，此处选择为初始点。顶点a、b、c、d都有与直接相连的边，选取其中权重最小的点图中为a下一个顶点为距离a或最

13、近的顶点，a距离c为10，距d为6，距b为5；距c为10，距d为15，距b为15；所以最短的距离是a到b得距离为5，连接a与b继续重复上面的步骤。可以发现距离a,b和最短的是b到c得距离为5，连接b和c。最后d与a,b,c,之中最短的距离为c到d的连线为6，故连接c到d,得出了最小生成树。轨迹为到a到b到c到d 模型可靠性的检验反证法：设生成的树为,假设存在使得总花费；则一定存在一个不属于；将参加，而在本被其他点连接，参加后会形成一个环；而一定小于环中*一边的权重，这与在生成树时每次都取权重最小值的步骤矛盾；故假设不成立，原模型成立。 模型的求解根据matlab运行结果见表1程序见附录1，可以

14、得到通信网络的总铺设费用为2947800元。得到的最优铺设方案如图3。表1 问题一结果图连接顺序12345678节点序号346170623647219连接顺序910111213141516节点序号5352737849713连接顺序1718192021222324节点序号4028425366672254连接顺序2526272829304647节点序号1652561851127417连接顺序4849505152535455节点序号10442367564821连接顺序5657585960616263节点序号1129201550327226连接顺序6465666768697071节点序号4396379

15、24396569连接顺序7273747576777879节点序号5737482541146080图3最优铺设方案图二、问题二的分析与求解1对问题的分析在问题一所得出的最小生成树的的根底上，我们考虑到假设其中只要有一个重要节点发生故障时，会造成八个节点以上故障，则通信畅通的可能性就不能保证到达90%，所以，我们可以通过节点删除法找到重要节点，然后再从重要节点引起故障的其他失效节点中找到一个节点与其他正常节点连通使得发生故障的节点数少于八个，我们就能保证通信畅通的可能性到达90%，并且我们要找到的这个节点与其他正常节点连通所铺设的费用是最省的。可以给出具体的算法流程图，如图4，图4问题二的算法流程

16、图2对问题的求解我们以节点22为中心节点，可以将最小生成树分成四个大局部：为节点22左边局部，为节点22右上方局部，为节点22右下方局部，即为剩下的局部，即=22 56 54。例如局部，当这局部有节点出现故障时，我们通过或的点与这个故障点引起的失效点之间用最省的方案再铺设一条线路后，保证任一点发生故障后也能使通信畅通的可能性到达90%。通过此方法，我们可以在局部找到重要节点70，局部找到重要节点51，局部找到重要节点77。找到重要节点后，要考虑这三个重要节点任一发生故障时，怎么增加最省的铺设线路问题，然后我们再分别将、分成两个局部，第一局部是重要节点出现故障后造成可靠性小于90%的节点之和，即

17、我们必需增加铺设线路的点，第二局部是重要节点发生故障后不影响可靠性的节点之和。所以可分为:B=13426615032;C=703681466676247692291949285783520802439406379273713425337;可分为:D=303845831596048E=5112463341686573182152439165525可分为:F=7111747217104415G=772366457757645对于任意节点发生故障时，要通过增加铺设后保证至少有70个节点是通信畅通的。所以这六个局部要考虑连接的方案有：BD和； BF和D；DF 和B；B、D和；可以通过matlab编程见

18、附录程序2分别计算9条线路各自最小的费用，然后计算4个方案费用。费用最小的方案所对应的线路即是我们要增加的铺设线路。Matlab算出的结果见表2：表2 问题二结果图节点1节点2铺设费用6168528817645467152861685282354465102470BD是60-61连接，对应费用为209100元；是2-10连接，对应费用为47000元，所以增加的总费用为256100元。BF是1-72连接，对应费用为78000元；D是15-38连接，对应费用为53600元，所以增加的总费用为131600元。DF 是15-38连接，对应费用为53600元， B是61-68连接，对应费用为52800元

19、，所以增加的总费用为106400元。B是61-68连接，对应费用为52800元；D是15-38连接，对应费用为53600元；是2-10连接，对应费用为47000元；所以增加的总费用为153400元。通过比拟4个方案，可以得知第三个方案所需要增加的费用是106400元，所以总的铺设费用=+106400=3054200元。增加的路线如图5。图5 任一节点出现故障可靠性到达90%的最优铺设方案图三、问题三的分析与求解1对问题的分析同样在问题一所得出的最小生成树的的根底上，我们考虑到假设其中只要有一个重要链路被破坏时，会造成八个节点以上故障，则通信畅通的可能性就不能保证到达90%，所以，我们可以通过逐

20、个分析每条链路，找到重要链路，一个链路被破坏会使最小生成树分割成两个局部，其中一局部则是失效的，然后再从重要链路被破坏而引起的其他失效节点中找到一个节点与其他正常节点连通使得发生故障的节点数少于或等于八个，我就能保证通信畅通的可能性到达90%，并且我们要找到的这个节点与其他正常节点连通所铺设的费用是最省的。2对问题的求解在第二问的根底上，我们已经将最小生成树分成四个大局部、和。再比方局部，当这局部的一个链路被破坏时，我们通过或的点与这个故障点引起的失效点之间用最省的方案再铺设一条线路后，保证任何一条链路被破坏后也能使通信畅通的可能性到达90%。通过此方法，我们可以在局部找到的重要链路是70与6

21、2之间的链路，在局部找到重要链路是18与51之间的链路，在局部找到重要链路是76与77之间的链路。找到三个重要的链路、和后，我们要研究这三个重要链路任一发生故障时，怎么增加最省的铺设线路问题，这三个重要的链路任意一个被破坏时都会导致其所在的局部被分割成两个小的局部，一个局部中的节点都是有效的，一个局部的节点都是失效的。所以我们将分成：=1342661503270368146667=6247692291949285783520802439406379273713425337所以我们将分成：=5130384583159604812684665334173=182152439165525所以我们将分

22、成：=7723664577571117472171044157645=7645=22 56 54比方链路被破坏后，会导致局部的节点都失效，保持通信畅通的节点就不能到达90%，同样，和也是如此，即要保证这三条链路之一破坏时，、和都不能失效，所以要考虑的连接方案有：和； 和；和；、和通过Matlab见附录程序3算出的结果如表3：表3 问题三结果图节点1节点2铺设费用6168528817645467152861685282354465102470是61-68连接，对应费用为52800元；是2-10连接，对应费用为47000元，所以增加的总费用为998000元。是8-17连接，对应费用为64500元；

23、是23-54连接，对应费用为46500元，所以增加的总费用为111000元。是46-71连接，对应费用为52800元， 是61-68连接，对应费用为52800元，所以增加的总费用为105600元。是是2-10连接，对应费用为47000元，是23-54连接，对应费用为46500元，；是61-68连接，对应费用为52800元，；所以增加的总费用为146300元。通过比拟4个方案，可以得知第一个方案所需要增加的费用最省，费用是是99800元，所以总的铺设费用=+99800=3047600元。图6 任一链路出现故障可靠性到达90%的最优铺设方案图四、问题四的分析与求解1对问题的分析在问题二及问题三的根

24、底上，首先比照分析问题二与问题三的节点分类，发现问题三中节点的分类包含了问题二中节点的分类，假设满足了了节点稳定性的要求，则一定能满足链路稳定性的要求，故得出节点稳定性比链路稳定性更重要的结论；再通过节点故障模型分别构造通信畅通的可能性都到达85%、90%、95%时所对应的最低铺设费用，使用Matlab软件编程，综合考虑稳定性和铺设费用得出铺设方案。2对问题的求解我们以节点22为中心节点，可以将最小生成树分成四个大局部：为节点22左边局部，为节点22右上方局部，为节点22右下方局部，即为剩下的局部，即=22 56 54。所问题二中可分为:B=13426615032;C=703681466676

25、247692291949285783520802439406379273713425337;问题三中将可分为：=1342661503270368146667=6247692291949285783520802439406379273713425337可见问题三中的节点分类包括了问题二中的分类问题二中可分为:D=303845831596048E=5112463341686573182152439165525问题三中将分成：=5130384583159604812684665334173=182152439165525利用matlab求解结果见表4。程序间附录程序4表4 问题四结果图节点1节点2铺

26、设费用节点1节点2铺设费用26332070636425761382716246510302675342039413000110326340592738363810922431190066751296631011908176451962565364128101962565可见问题三中的节点分类包括了问题二中的分类故节点稳定性的要求更高，即只要满足了节点稳定性就能满足链条稳定性的要求，下面仅考虑节点稳定性需求下的故障模型。当假设要求任意一个结点出现故障时，其它结点间仍然能够保持通信畅通的可能性都到达85%时，通过问题二与问题三的模型计算出的最省铺设方案为3047600元。分配方案为：图7 通畅度8

27、5%时最省铺设方案同样假设要求任意一个结点出现故障时，其它结点间仍然能够保持通信畅通的可能性都到达90%时，通过问题二与问题三的模型计算出的最省铺设方案为3054200元。分配方案为：图8 通畅度90%时最省铺设方案同样假设要求任意一个结点出现故障时，其它结点间仍然能够保持通信畅通的可能性都到达90%时，通过问题二与问题三的模型计算出的最省铺设方案为3578800元。分配方案为：图9 通畅度95%时最省铺设方案可见当通畅度从85%增加至90%时，费用仅仅增加了6400元，而当通畅度从90%增加至95%时，费用增加了524600元，应选择90%的通畅度，此时可以满足当一个节点或一个链条出现故障时

28、，其它结点间仍然能够保持通信畅通的可能性都到达90%，且费用适中，可以同时满足稳定性和铺设本钱的条件，故此题选择图5所示的铺设方案为综合的最优方案。6 误差分析一、误差分析1在取得两节点之间的距离数据时由于人工记取数据或者测量距离的工具不标准，会造成读取数据的误差，从而造成模型的误差。2在论文中直接认为总的铺设费用是有距离和节点单位费用决定的，在实际解决问题中，总铺设费用还要考虑其他因素的影响。3在问题二的分析方法中，我们直接认为每个节点之间发生故障的概率是一样的，其实有的节点发生故障的概率大，我们考虑的太理想化，而且有的节点发生故障会导致其他*些节点发生故障的概率增大或者减小。7 模型的评价

29、与推广一、模型的优点 1本文对问题有合理的猜测、假设、计算以及检验；2按照需要求解的问题灵活选取数据，而不是每次都使用同一个数据；3问题三在求解出来之后又提出一个新思路，并且有一个新的解法。一题两解，并且可以互相验证结果；4研究问题时循序渐进，在求解的过程中慢慢进步，逐步完善。二、模型的缺点1求解问题时用的数据是自己观察，手工计数的，这样得出的数据难免会有些误差，有些没有考虑到的因素；2在最后模型改良的时候，我们提出了思路和解法但是由于时间有限，我们并没有将最后的具体结果计算出来；三、模型的推广1排队论模型我们所研究的排队论是把排队论应用到交通中，道路发生事故时堵车所形成的类似排队现象这种情况

30、运用排队论的相关知识来求解，我们还可以将排队论延伸到其它的领域，比方车站买票、医院取药、通讯效劳等其它领域；2交通流模型由于进出匝道或交通事故等原因而形成的交通瓶颈，是导致高速道路交通拥挤和堵塞的最主要的根源，我们通过这个模型不仅仅能够对解决堵车时的排队长度问题还可以解决密度，速度等其他的交通指标；3在解决第三问时，我们发现交通堵塞问题与管道收缩而导致的运动气流中形成冲动波过程很相似，所以我们就通过研究后者的模型来类比我们要解决的问题，这种联想类比法也可以推广到其它问题。8 模型的改良此题中线路的可靠性仅仅考虑了节点和链路的稳定性，在保证连通性的情况下最小化了铺设本钱；但未考虑流量因素，流量与

31、节点的度有关，节点的度是指与节点直接连接的链路的数量，流量因素是指：一个节点的度越多，流过这个节点的最大流量就越大。所以，流量可以看作是图中节点的度数之和的增函数。而在节点度之和一定的情况下，各个节点度数的波动越大，度数小的节点就成为流量的约束。因此，流量的大小是节点度数的方差函数。令代表图中度的均值，代表方差构造流量函数： 1而本文问题一中有铺设本钱的目标函数为： 2将两个因素综合考虑，这里利用线性加权的方法将其综合，首先将式1、2归一化，然后定义偏好系数，越接近0表是决策者越倾向于费用因素，越接近于1越倾向于流量因素，所以，最终的目标函数为：设置约束条件，其中假定每一个节点的度数属于2,5

32、的闭区间。但凡有节点度数不在词区间的方案都被认为是不可行解。为防止蚂蚁在寻优的过程中产生不可行解，定义low,up为度的约束区间。对于每一个节点i，其度，在此定义一个函数：则可以定义罚函数为：预算本钱的约束：因为前面推导出了一个新目标函数，所有铺设本钱不再是要优化的对象。而在实际过程中，决策放能够承当的最大铺设本钱一定不大于预算。所以，定义一个最大预算。根据心理学的知识，决策者对费用的容忍度通常都是在与最小本钱的比拟中产生的，所以定义一个容忍百分比其取值如下：相应的最大容忍度为。节点稳定性的约束：首先引入一个故障矩阵，表示在节点和节点之间存在连接线时，连接线出现故障的概率。仍然假定节点不会出现

33、故障，所有故障都来自于链路。而每一条边对于点来说是并联的，利用概率统计的知识，可以求得节点能够正常工作的概率为：令为用户规定的平均最小工作概率。如果在整个网络中所有节点工作的概率的算数平均值大于，则这个网络是可承受的，否则是不可承受的。故由上述分析，这个优化的模型是一个组合优化模型，可以用蚁群算法来求解，这里简要介绍一下蚁群算法的求解过程。1.初始化参数2.利用概率的方法构建蚂蚁的路径。本文综合考虑了最小本钱模型和度约束条件，同时在本模型中又参加了流量及链路概率的影响。如当前位于节点的蚂蚁选择作为下一个节点的概率为：其中，为链路信息素强度； 为一个预先给定的启发式信息，初始值为链路距离的倒数。

34、为本算法设置了启发式信息的优先级：链路如果有一个端点的度为1，则加1 倍，假设链路2 个端点的度都为1，加2 倍。、 是2 个参数，它们分别决定了信息素和启发式信息的相对影响力。代表位于节点的蚂蚁可以直接到达的相邻节点的集合，也就是还没有被蚂蚁访问的节点的集合。Step3 本文使用的后台策略是在蚂蚁前进一步时就计算各个约束的值，看是否满足要求，当有一个约束不再满足要求时，蚂蚁不再前行。一轮路径探索完之后，计算目标函数的值，进而挑选出最优的路径。Step4 在每一轮路径探索之后，更新信息素，更新规则如下：其中为信息素挥发程度；表示第次循环是否选择了链路，如果先择，否则，是常数。5.当路径探索的论

35、述到达时输出结果。因为蚁群算法有较强的收敛性，故当经过不同次数的迭代实验是，会得出较为相近的结果，此时则为最优的结果，最终的结果可有C语言编程完成。参考文献：1 .2 基于蚁群算法的多目标网络铺设策略研究龚承柱1，诸克军1，郭海湘1,2(1. 中国地质大学经济管理学院， 430074；2. 交通大学管理学院， 710049). 3 启源，金星，叶俊.数学模型M ；高等教育，2011，1. z.-附录程序1：%A表示权值矩阵%C表示生成树的权和%visit标记是否访问过1表示访问，0表示未访问，dis记录当前最短距离，R矩阵表示结点序号之间从前往后依次连接clc,clearA=*lsread(d

36、ate.*ls);%权值矩阵节点之间的费用表=距离*单位费用L=length(A);A(A=0)=inf;%初始化邻接矩阵dis=zeros(1,L);dis(:)=inf;%初始化dis数组visit=zeros(1,L);RESULT=zeros(L,L);visit(1)=1;dis(1)=0;ne*t=1;C=0;a=zeros(1,80);%初始时刻1点参加集合中R=zeros(2,79);R(1,:)=1:79;%初始化结果矩阵for k=1:L-1; now=ne*t;%now表示计算的当前节点 m=inf;%m保存当前节点到集合的最短距离 for i=1:L; if visit

37、(i)=0%如果没有标记，开场这个点 dis(i)=min(dis(i),A(now,i);%更新这个i点到集合的最短距离，保存到dis中 if(dis(i)m) m=dis(i); ne*t=i;%记录下最小的那个点，作为下一个计算的点。 end end end C=C+m;%加权值 visit(ne*t)=1;%标记进集合的点 RESULT(k,ne*t)=1;%整合每次标记endfor t=1:79; R(2,t)=find(RESULT(t,:)=1);%按顺序输出节点表示连接过程endR %结果矩阵输出，第一行表示连接顺序，第二行表示表示依次连接节点数C %相应情况下的最省铺设费用程

38、序二：A=*lsread(date.*ls); %权值矩阵节点之间的费用表=距离*单位费用n1=1342661503270368146667;n2=5130384583159604812684665334173;n3=772366457757111747217104415;m1=134266150327036814666762476922919492857835208024;m2=5130384583159604812684665334173182152439165525;m3=7723664577571117472171044157645;m4=542256;%输入六个节点分类矩阵*1=m2

39、 m3 m4;*2=m1 m3 m4;*3=m1 m2 m4;L1=length(n1);L2=length(n2);L3=length(n3);L4=length(m1);L5=length(m2);L6=length(m3);L7=length(m4);%分别求其长度和两两组合长度t=1; for i=1:L1; for j=1:L2; R(t,:)=n1(i) n2(j) A(n1(i),n2(j) t=t+1; end end for i=1:L1; for k=1:L3; R(t,:)=n1(i) n3(k) A(n1(i),n3(k); t=t+1; end end for j=1

40、:L2; for k=1:L3; R(t,:)=n2(j) n3(k) A(n2(j),n3(k); t=t+1; end end for i=1:L1; for p=1:L5+L6+L7; R(t,:)=n1(i) *1(p) A(n1(i),*1(p); t=t+1; end end for j=1:L2; for q=1:L4+L6+L7; R(t,:)=n2(j) *2(q) A(n2(j),*2(q); t=t+1; end end for k=1:L3; for r=1:L4+L5+L7; R(t,:)=n3(k) *3(r) A(n3(k),*3(r); t=t+1; end e

41、nd R1=sortrows(R(1:192,:),3); Result(1,:)=R1(1,:); R2=sortrows(R(193:360,:),3); Result(2,:)=R2(1,:); R3=sortrows(R(361:584,:),3); Result(3,:)=R3(1,:); R4=sortrows(R(585:1101,:),3); Result(4,:)=R4(1,:); R5=sortrows(R(1102:1997,:),3); Result(5,:)=R5(1,:); R6=sortrows(R(1998:2893,:),3);Result(6,:)=R6(1

42、,:);%逐个计算最省费用Result%输出分类比拟下的最省费用及相应连接节点序号程序三：A=*lsread(date.*ls); %权值矩阵节点之间的费用表=距离*单位费用n1=1342661503270368146667;n2=5130384583159604812684665334173;n3=772366457757111747217104415;m1=134266150327036814666762476922919492857835208024;m2=5130384583159604812684665334173182152439165525;m3=7723664577571117

43、472171044157645;m4=542256;*1=m2 m3 m4;*2=m1 m3 m4;*3=m1 m2 m4;L1=length(n1);L2=length(n2);L3=length(n3);L4=length(m1);L5=length(m2);L6=length(m3);L7=length(m4); %分别求其长度和两两组合长度t=1; for i=1:L1; for j=1:L2; R(t,:)=n1(i) n2(j) A(n1(i),n2(j); t=t+1; end end for i=1:L1; for k=1:L3; R(t,:)=n1(i) n3(k) A(n1

44、(i),n3(k); t=t+1; end end for j=1:L2; for k=1:L3; R(t,:)=n2(j) n3(k) A(n2(j),n3(k); t=t+1; end end for i=1:L1; for p=1:L5+L6+L7; R(t,:)=n1(i) *1(p) A(n1(i),*1(p); t=t+1; end end for j=1:L2; for q=1:L4+L6+L7; R(t,:)=n2(j) *2(q) A(n2(j),*2(q); t=t+1; end end for k=1:L3; for r=1:L4+L5+L7; R(t,:)=n3(k)

45、*3(r) A(n3(k),*3(r); t=t+1; endend %分别求其长度和两两组合长度 R1=sortrows(R(1:192,:),3); Result(1,:)=R1(1,:); R2=sortrows(R(193:360,:),3); Result(2,:)=R2(1,:); R3=sortrows(R(361:584,:),3); Result(3,:)=R3(1,:); R4=sortrows(R(585:1100,:),3); Result(4,:)=R4(1,:); R5=sortrows(R(1101:1996,:),3); Result(5,:)=R5(1,:);

46、 R6=sortrows(R(1997:2562,:),3); Result(6,:)=R6(1,:); Result %输出分类比拟下的最省费用及相应连接节点序号附录四A=*lsread(date.*ls); %权值矩阵节点之间的费用表=距离*单位费用n1=263415032;n2=666736814;n3=79634020248039;n4=28491929;m1=65337341;m2=3159604838458;m3=6645775;m4=17104415;*1=m2 m3 m4;*2=m1 m3 m4;*3=m1 m2 m4;L1=length(n1);L2=length(n2);L

47、3=length(n3);L4=length(n4);L5=length(m1);L6=length(m2);L7=length(m3);L8=length(m4);%求矩阵长度t=1 for i1=1:L1; for j1=1:L5; R(t,:)=n1(i1) m1(j1) A(n1(i1),m1(j1); t=t+1; end end for i1=1:L1; for j1=1:L6; R(t,:)=n1(i1) m2(j1) A(n1(i1),m2(j1); t=t+1; end end for i1=1:L1; for j1=1:L7; R(t,:)=n1(i1) m3(j1) A(

48、n1(i1),m3(j1); t=t+1; end end for i1=1:L1; for j1=1:L8; R(t,:)=n1(i1) m4(j1) A(n1(i1),m4(j1); t=t+1; end end for i2=1:L2; for j2=1:L6; R(t,:)=n2(i2) m2(j2) A(n2(i2),m2(j2); t=t+1; end end for i2=1:L2; for j2=1:L7; R(t,:)=n2(i2) m3(j2) A(n2(i2),m3(j2); t=t+1; end end for i2=1:L2; for j2=1:L8; R(t,:)=

49、n2(i2) m4(j2) A(n2(i2),m4(j2); t=t+1; end end for i2=1:L2; for j2=1:L5; R(t,:)=n2(i2) m1(j2) A(n2(i2),m1(j2); t=t+1; end end for i3=1:L3; for j3=1:L7; R(t,:)=n3(i3) m3(j3) A(n3(i3),m3(j3); t=t+1; end end for i3=1:L3; for j3=1:L5; R(t,:)=n3(i3) m1(j3) A(n3(i3),m1(j3); t=t+1; end end for i3=1:L3; for

50、j3=1:L6; R(t,:)=n3(i3) m2(j3) A(n3(i3),m2(j3); t=t+1; end end for i3=1:L3; for j3=1:L8; R(t,:)=n3(i3) m4(j3) A(n3(i3),m4(j3); t=t+1; end end for i4=1:L4; for j4=1:L8; R(t,:)=n4(i4) m4(j4) A(n4(i4),m4(j4); t=t+1; end end for i4=1:L4; for j4=1:L5; R(t,:)=n4(i4) m3(j4) A(n4(i4),m3(j4); t=t+1; end end f

51、or i4=1:L4; for j4=1:L6; R(t,:)=n4(i4) m2(j4) A(n4(i4),m2(j4); t=t+1; end end for i4=1:L4; for j4=1:L7; R(t,:)=n4(i4) m3(j4) A(n4(i4),m3(j4); t=t+1; end end%分别求出最省费用 N=size(R); R1=sortrows(R(1:20,:),3); Result(1,:)=R1(1,:); R2=sortrows(R(21:55,:),3); Result(2,:)=R2(1,:); R3=sortrows(R(56:75,:),3); R

52、esult(3,:)=R3(1,:); R4=sortrows(R(76:95,:),3); Result(4,:)=R4(1,:); R5=sortrows(R(96:115,:),3); Result(5,:)=R5(1,:); R6=sortrows(R(116:151,:),3); Result(6,:)=R6(1,:); R7=sortrows(R(152:171,:),3); Result(7,:)=R7(1,:); R8=sortrows(R(172:191,:),3); Result(8,:)=R8(1,:); R9=sortrows(R(192:207,:),3); Resu

53、lt(9,:)=R9(1,:); R10=sortrows(R(208:235,:),3); Result(10,:)=R10(1,:); R11=sortrows(R(236:251,:),3); Result(11,:)=R11(1,:); R12=sortrows(R(252:267,:),3); Result(12,:)=R12(1,:); R13=sortrows(R(268:295,:),3); Result(13,:)=R13(1,:); R14=sortrows(R(296:344,:),3); Result(14,:)=R14(1,:); R15=sortrows(R(345:372