原文传递
网络的K最短路分析及其在交通中的应用
| 论文题名： | 网络的K最短路分析及其在交通中的应用 |
| 关键词： | 交通网络;联网收费;多路径分析;K最短路算法 |
| 摘要： | 今天的社会已经成为网络社会，在今天的自然科学中，网络研究也成为重要课题。交通网络分析的重点是路径分析，而路径分析的核心为最优路径算法。最短路径算法是最优路径算法中的一个经典问题,它在实际生产生活中有广泛应用。在许多情况下，不仅仅要考虑最短路也要考虑次短路、次次短路，即K最短路问题。K最短路算法涉及很多领域，如在交通工程、通信、人工智能等方面有重要的实际意义。 本文在系统总结和分析经典最短路算法、动态规划方法的基础上，对联网收费交通网络中的多路径问题进行了深入细致的研究，得出了适用于交通网络多路径分析及模拟的高效、快速的K最短路算法。这一算法按长度递增顺序给出K最短路路径排列。算法的复杂度为O m n n m k++(lg lg)。在给定的网络中，通过添加标识站对两顶点之间K最短路径识别，本文既给出标识站的数目、位置的确定方法，又给出了整个网络中添加标识站的总方案数的计算方法。通过路径伸展系数，采用启发式搜索算法标定高速公路网的路径伸展系数的大小，从而确定高速公路网有效多路径搜索范围，利用基于动态规划法的K最短路算法搜索给定路网上任两站点之间的有效多路径。最后对山东省联网收费高速公路网络的K最短路问题进行具体分析。 |
| 作者： | 张建勇 |
| 专业： | 交通运输规划与管理 |
| 导师： | 刘法胜 |
| 授予学位： | 硕士 |
| 授予学位单位： | 山东科技大学 |
| 学位年度： | 2006 |
| 正文语种： | 中文 |
检索历史
应用推荐
