最短路径多种算法的实际应用及研究

装订线“工大出版社杯”第十三届西北工业大学数学建模竞赛暨全国大学生数学建模竞赛选拔赛题目B题密封号2012年5月2日剪切线密封号2012年5月2日通信工程学院第队队员1队员2队员3姓名冯鸣月李璇李晓扬班级0111310111510111512摘要在生活中，道路施工问题随处可见。怎样用尽量少的施工量使道路达到更好的连通性是一个值得讨论的问题。在建设中要考虑结点选择，路线设计等问题。根据这些特点，我们建立了5个有创新性思想的模型以解决这3个问题。对于问题1我们用Prim算法首先建立了模型——总路程最短的最小生成树E。对模型进行了合理的理论证明和推导，所给出的理论证明结果大约为416，然后借助于Floyd算法和Matlab软件，计算出E中任意两入口最短路程，将之与此两点间直线距离的1.4倍进行比较验证。对于问题2我们将矩形边沿内区域网格化。(取网格距离为1米)。第一个模型把平面中的点化为离散化粒子群，通过引入若干“虚设站”并构造一个新的最小生成树，寻求结点数目给定条件下的最短路径之和最小值。第二个模型是求网格距离的最小值。把两点间的连通方式近似为网格直线（即需平行于坐标轴），用直线化简法求得最终结点。对于问题3通过分析讨论，本文根据所建的模型，提出了一种很有价值的跨学科类比模型设想。（本文是将结点问题转化为有公式背景的物理电路问题，可以利用已有的物理公式与定理将问题简化）。在已知条件下，模型给出的方案是令人满意的。并且，由于本文所给算法的普适性，它的实用性很强，对于一般实际生活中的普遍问题提供解决办法和思路，并可以推广到解决其他类似问题，可以获得较高使用价值，为我们的实际生活提供便利，并满足效益最大化。值得一提的是，对于问题一、二，本文提出了两种不同的模型，并分别进行了针对性讨论。并对问题三运用了跨学科类比思想。关键词：Prim算法，Floyd算法,最小生成树，0-1规划思想。决策区域网格化，直线简化法，回归分析思想，跨学科类比法。3目录一问题重述.......................................................................................................................................4二问题分析.......................................................................................................................................5三模型假设.......................................................................................................................................6四定义与符号说明...........................................................................................................................6五模型的建立与求解.......................................................................................................................71.1模型准备.......................................................................................................................................71.1.1最小生成树：......................................................................................................................71.1.2Prim算法：.............................................................................................................................71.1.3Floyd算法:...............................................................................................................................81.2问题1的两个模型.......................................................................................................................81.2.1模型Ｉ：最小生成树模型...................................................................................................81.2.2模型II：0—1规划模型....................................................................................................131.2.3问题1的两种模型的比较.................................................................................................151.3问题2的两个模型.....................................................................................................................151.3.1模型I：离散化结点选址模型..........................................................................................151.3.2模型II：直线简化模型.....................................................................................................181.3.3两种模型的比较................................................................................................................201.4问题3的模型.............................................................................................................................201.4.1模型：电路模拟选址模型.................................................................................................20六模型评价及推广.........................................................................................................................22七参考文献.....................................................................................................................................234一问题重述西安某大学计划建一个形状为矩形或其他不规则图形的公园，不仅为了美化校园环境，也是想为其学生提供更的生活条件。公园计划有若干个入口，现需要建立一个模型去设计道路让任意两个入口相连（可以利用公园四周的边，即默认矩形的四条边上存在已经建好的道路，此道路不计入道路总长），使总的道路长度和最小，前提要求是任意的两个入口之间的最短道路长不大于两点连线的1.4倍。提炼问题已知条件可知，1.主要设计对象可假设为如图所示的矩形公园，其相关数据为：长200米，宽100米，2.1至8各入口的坐标分别为：P1(20,0),P2(50,0),P3(160,0),P4(200,50),P5(120,100),P6(35,100),P7(10,100),P8(0,25).3.在矩形公园内修建道路时，道路的交点只能在已设或所求交叉点或八个入口。4.入口与入口间距离为通过矩形四条边上的距离（此道路不计入道路总长）或平面上两点依次连线所得距离之和。5.任意的两个入口之间的最短路径长不大于两点连线的1.4倍。6.新修的道路与四周的连接只能与8个路口相通，而不能连到四周的其它点。7.新建道路需满足以上约束条件，并使道路总和最少。分析问题可知，所求为问题一：矩形内确定4个道路交叉点为：A(50,75)，B(40,40)，C(120,40)，D(115,70）。求满足约束条件后的总路程最短、道路设计路线图，并求出新修建道路的长度。。问题二：现在公园内可以任意修建道路，求在满足条件下使总路程最少时道路交叉点的坐标，画出道路设计，计算新修路的总路程。问题三：若公园内有一条矩形的湖R1(140,70),R2(140,45),R3=(165,45),R4=(165,70)，新修的道路不能通过，但可以到达湖四周的边。重复完成问题二的任务。5二问题分析本类型问题属于最短路径数学问题，对于解决此类问题一般采用求最小生成树的数学方法的分析。对于求解最短路径，传统的思路是需要使用计算量很大的且效率偏低的穷举法及其相似算法，这里我们先据根据Prim算法找到最短路径的连通方案，再利用Flod算法和题目要求，求出任意两点间的最短路径，对结果进行修正。1.1问题1的分析问题1属于已知各点的位置和距离求最短路径问题。对于已知的相邻点间路径可分为三类：入口与入口间的直线或折线最短路径（直接由图看出，并由条件“最短路径长不大于两点连线的1.4倍”进行约束）；入口与交叉点间直线路径；交叉点与交叉点间直线距离。这里还要注意矩形边界线上的路径长度不计入总长度内，因此边界距离应计为0。得出任意两点间最短路径后形成邻接矩阵，根据Prim算法求出12个点的最短路径之和与最短路径时的连通方案（这里“连通”指任意一点出发总能找到一条路径到达其余个点）。由于所求连通方案中一些两间折线距离可能不满足小于等于折线1.4倍，因此最后需用Floyd法则求出任意两点间连通距离与1.4倍直线距离进行比较。对问题1所要求的结果进行分析。1.2问题2的分析问题2属于不指定备选点的结点选址数学问题，对于解决此类问题一般可采用重心法、避圈法和直线化简法求得。在选址模型中。一般采用两种方法来计算节点间的距离：一种是直线距离，也叫欧几里德距离(EuclideanMetric)；另一种是折线距离(RectilinearMetTic)，即为把平面网格化后的网格距离。针对这两种距离，本题可分别建立两个模型。第一个模型把平面中的点化为离散化粒子群，按照