电缆铺设问题

《电缆铺设问题》由会员上传分享，免费在线阅读，更多相关内容在行业资料-天天文库。

1、电缆铺设问题摘要本文解决的是军营电缆铺设最优策略的图论问题。首先，根据题意分析12个营之间边的权值特点，然后，确定采用算法和标号算法解决问题，最后，自定义函数，建立以最小权值和为目标函数的最优路径问题。对于问题一：假设各个营点为顶点，各营点间的路线为边，通过采用算法求得原图的最小生成树进而求出最短铺设路线。采用类比推理的思想，由易到难推出目标函数为最小权值和，用软件编程求解出最短电缆铺设长度为206千米。通过将结果图与原题图进行对比，可以判断出结果的合理性。下表为问题一中电缆铺设具体路线：（单位：千米）边1-31-111-88-48-22-1212-912-612-55

2、-1010-7总长354518155231514171613216对于问题二：同问题一，将各个营点假设为顶点，各营点间的路线假设为边，目标函数依然为最小权值和。通过标号算法运用软件编程求解出在问题二条件下的最短电缆铺设长度为308千米。通过将结果图与原题图进行对比，可以判断出结果的合理性。下表为问题二中电缆铺设具体路线：（单位：千米）边1-31-111-41-51-71-84-97-10长3545202729182613边10-68-22-1212-912-612-58-210-7长21523151417513总长308由于各边所选用电缆线的截面以及线损（权值）在规划方

3、案确定之前是无法知道的，所以在模型改进中提出算法的改进。本模型还适用于单向最短路线问题。关键词：类比推理无向图算法算法最小生成树191.问题重述1.1问题背景在21世纪的今天，信息交流和物质交流日益频繁，交流的路线也日趋复杂化。怎样从复杂的交通网中找出最优的交通路径，方便人们的交流，也成为人们所关心的问题。最优路径的选择，作为图与网络技术研究中的一个经典问题一直在出门旅游、重要机构的选址、工程规划、地理信息系统、通信和军事运筹学等领域有着十分广泛的应用,对该问题求解的算法设计有着重要的理论和应用价值.在错综复杂的网络中找出最优路线显得至关重要。1.2问题所给信息某次军事

4、演习12个大本营之间的电缆铺设构成的通讯网络图如下，从图中可以清晰地看出各大本营之间的地理位置分布情况，也可以清楚地读出各大本营之间的距离（单位：千米）。.图一：12个大本营之间的路线及距离（单位：千米）1.3问题的提出问题一：要保证任意两营之间都有线缆连结，问至少要铺设多长的线缆？问题二：为了保证在其他任意三个营节点遭到破坏通讯中断时，1营和12营仍然可以通讯，求此种情况下的最小铺设长度和铺设方法？2.模型假设假设一：只考虑距离，不考虑其它因素对题目所求最小距离的影响；假设二：每两个营之间铺设的电缆均为直线；19假设三：不考虑其它电缆的故障对所求线路电缆的影响；假设四

5、：不考虑各营的大小和体积，各营可视为一个个点，点与点之间的线路可以视为无向图的直线边。3.符号说明符号符号意义无向图中各点所对应的边无向图中各点所对应的边的权值无向图中节点的点集无向图中任意两点的距离无向图中节点无向图中任意两点的连接状态1.数据分析根据原题所给图一，做出如下权值表：表一：各营点间边的权值12345678910111210035202702918004502000400050002330000000000400001526061050462938016017600002101470001300800000900015100001100120题目给出了12

6、个营及连接各营的20条赋权值的边19，将各营点视作点，将各边视为直线。各营点周围边的权重大小不一，例如6营点，最大权重为46，最小为14。题中权重最小为5，最大为61。其中1营点与5营点连接的边数最多，均为6条，在这两点周围边的取舍尤为关键。3营点只与1营点相关，故不予考虑，1.问题分析本文研究的是一个最优化路径问题。问题中给出了一个由12个营构成的复杂的电缆连接网络图。本文需要从复杂的连接网络图中选出最短的电缆连接路线。题目所给电缆连接网络图为无向图，故欲求在各种情况下的最短电缆铺设路径的长度，只需求各路径的权值总和的最小值即可。针对问题一：要求保证任意两营之间都有线

7、缆连结，求最短路径，故需用11条边连接这12个点，即求最小生成树。采用算法基于顶点来实现最小生成树。假设使用邻接矩阵来存储图，在算法实现的过程中，需要以下两类信息：（1）集合T1内各顶点到集合T2中各顶点的权值最小的边的权值（其中T2集合是表示这些集合中的点已经是最小生成树中的点了）；（2）集合T1内各顶点距离集合T2最小的顶点。据此，问题一中最小生树的形成分析如下图所示：图二：问题一分析流程图19针对问题二：要求保证在其他任意三个营节点遭到破坏通讯中断时，1营和12营仍然可以通讯，故1营与12营之间有4条互不重合的铺设路线。又根据数据分