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

装 订 线 “工大出版社杯”第十三届西北工业大学数学 建模竞赛暨全国大学生数学建模竞赛选拔赛题目 B 题 密封号 2012 年5 月2 日 剪 切 线 密封号 2012 年5 月2 日 通信工程 学院 第 队 队员1 队员2 队员3 姓名 冯鸣月 李璇 李晓扬 班级 011131 011151 011151 摘 要 在生活中，道路施工问题随处可见。怎样用尽量少的施工量使道路达到更好的连通 性是一个值得讨论的问题。在建设中要考虑结点选择，路线设计等问题。根据这些特点， 我们建立了5 个有创新性思想的模型以解决这3 个问题。 对于问题 1 我们用Prim 算法首先建立了模型——总路程最短的最小生成树E 。对 模型进行了合理的理论证明和推导，所给出的理论证明结果大约为 416 ，然后借助于 Floyd 算法和Matlab 软件，计算出E 中任意两入口最短路程，将之与此两点间直线距 离的1.4 倍进行比较验证。 对于问题2 我们将矩形边沿内区域网格化。(取网格距离为1 米) 。第一个模型把平 面中的点化为离散化粒子群，通过引入若干“虚设站”并构造一个新的最小生成树，寻 求结点数目给定条件下的最短路径之和最小值。第二个模型是求网格距离的最小值。把 两点间的连通方式近似为网格直线（即需平行于坐标轴），用直线化简法求得最终结点。 对于问题3 通过分析讨论，本文根据所建的模型，提出了一种很有价值的跨学科类 比模型设想。（本文是将结点问题转化为有公式背景的物理电路问题，可以利用已有的 物理公式与定理将问题简化）。 在已知条件下，模型给出的方案是令人满意的。并且，由于本文所给算法的普适性， 它的实用性很强，对于一般实际生活中的普遍问题提供解决办法和思路，并可以推广到 解决其他类似问题，可以获得较高使用价值，为我们的实际生活提供便利，并满足效益 最大化。 值得一提的是，对于问题一、二，本文提出了两种不同的模型，并分别进行了针对 性讨论。并对问题三运用了跨学科类比思想。 关键词： Prim 算法， Floyd 算法, 最小生成树，0-1 规划思想。 决策区域网格化，直线简化法，回归分析思想，跨学科类比法。 2 目录 一 问题重述4 二 问题分析5 三 模型假设6 四 定义与符号说明6 五 模型的建立与求解7 1.1 模型准备7 1.1.1 最小生成树： 7 1.1.2 Prim 算法： 7 1.1.3 Floyd 算法: 8 1.2 问题1 的两个模型 8 1.2.1 模型Ｉ：最小生成树模型 8 1.2.2 模型II ：0—1 规划模型 13 1.2.3 问题1 的两种模型的比较 15 1.3 问题2 的两个模型 15 1.3.1 模型I ：离散化结点选址模型 15 1.3.2 模型II ：直线简