电缆铺设问题.doc

电缆铺设问题摘要本文解决的是军营电缆铺设最优策略的图论问题。首先,根据题意分析 12 个营之间边的权值特点,然后,确定采用 prim 算法和 Dijkstra 标号算法解决问题, 最后,自定义 ijd 函数, 建立以最小权值和为目标函数的最优路径问题。对于问题一:假设各个营点为顶点,各营点间的路线为边,通过采用 prim 算法求得原图的最小生成树进而求出最短铺设路线。采用类比推理的思想,由易到难推出目标函数为最小权值和,用 matlab 软件编程求解出最短电缆铺设长度为 206 千米。通过将结果图与原题图进行对比,可以判断出结果的合理性。下表为问题一中电缆铺设具体路线:(单位:千米) 边1-3 1-11 1-8 8-4 8-2 2-12 12-9 12-6 12-5 5-10 10-7 总长3545181552315********** 对于问题二:同问题一,将各个营点假设为顶点,各营点间的路线假设为边, 目标函数依然为最小权值和。通过 Dijkstra 标号算法运用 matlab 软件编程求解出在问题二条件下的最短电缆铺设长度为 308 千米。通过将结果图与原题图进行对比,可以判断出结果的合理性。下表为问题二中电缆铺设具体路线: (单位:千米) 边1-3 1-11 1-4 1-5 1-7 1-8 4-9 7-10 长3545202729182613 边10-6 8-2 2-12 12-9 12-6 12-5 8-2 10-7 长21523151417513 总长 308 由于各边所选用电缆线的截面以及线损(权值)在规划方案确定之前是无法知道的,所以在模型改进中提出 prim 算法的改进。本模型还适用于单向最短路线问题。关键词: 类比推理无向图 prim 算法 Dijkstra 算法最小生成树 1. 问题重述 问题背景在21世纪的今天,信息交流和物质交流日益频繁,交流的路线也日趋复杂化。怎样从复杂的交通网中找出最优的交通路径,方便人们的交流,也成为人们所关心的问题。最优路径的选择,作为图与网络技术研究中的一个经典问题一直在出门旅游、重要机构的选址、工程规划、地理信息系统、通信和军事运筹学等领域有着十分广泛的应用,。 问题所给信息某次军事演习 12个大本营之间的电缆铺设构成的通讯网络图如下,从图中可以清晰地看出各大本营之间的地理位置分布情况,也可以清楚地读出各大本营之间的距离(单位:千米)。. 图一: 12个大本营之间的路线及距离(单位:千米) 问题的提出问题一: 要保证任意两营之间都有线缆连结,问至少要铺设多长的线缆? 问题二:为了保证在其他任意三个营节点遭到破坏通讯中断时, 1 营和 12 营仍然可以通讯,求此种情况下的最小铺设长度和铺设方法? 2. 模型假设假设一: 只考虑距离,不考虑其它因素对题目所求最小距离的影响; 假设二: 每两个营之间铺设的电缆均为直线; 假设三: 不考虑其它电缆的故障对所求线路电缆的影响; 假设四:不考虑各营的大小和体积,各营可视为一个个点,点与点之间的线路可以视为无向图的直线边。 3. 符号说明符号符号意义 e 无向图中各点所对应的边( ) ew 无向图中各点所对应的边的权值 V 无向图中节点的点集 ijD 无向图中任意两点的距离 v 无向图中节点 ijd 无向图中任意两点的连接状态 0 ijd ????,(不连接) 1,(连接) 3. 数据分析根据原题所给图一,做出如下权值表: 表一:各营点间边的权值 123456789 10 11 12 100 35 20 270 29 1800 450 2000 40005000 23 30000000000 40000 15 260 610 50 46 29 380 160 17 60000 210 14 7000 1300 800000 9 000 15 10000 11 00 12 0 题目给出了 12个营及连接各营的 20条赋权值的边,将各营点视作点,将各边视为直线。各营点周围边的权重大小不一,例如 6 营点,最大权重为 46 ,最小为 14 。题中权重最小为 5,最大为 61。其中 1营点与 5营点连接的边数最多,均为 6条,在这两点周围边的取舍尤为关键。 3营点只与 1营点相关,故不予考虑, 4. 问题分析本文研究的是一个最优化路径问题。问题中给出了一个由 12 个营构成的复杂的电缆连接网络图。本文需要从复杂的连接网络图中选出最短的电缆连接路线。题目所给电缆连接网络图为无向图,故欲求在各种情况下的最短电缆铺设路径的长度,只需求各路径的权值总和的最小值即可。针对问题一: 要求保证任意两营之间都有线缆连结,求最短路径,故需用 11