公交查询算法的研究与实现(论文12000字)

公交查询算法的研究与实现(论文12000字)
【摘要】随着中国经济的快速发展，城市人口越来越多，许多城市交通拥挤已成为不争得事实。为缓解交通拥挤带来的问题，各个城市大力发展公共交通事业，这使得提高网络公交查询系统的效率显得尤为重要[1]。城市公交是体现城市文明与现代化建设的一个重要窗口，对于广大市民，如果能够快捷的查询到前往目的地的乘车方案，将为他们的出行提供极大的方便。搭建城市网络公交查询系统关键的算法是最短路径算法和换乘算法。最短路径算法在现实生活中运用非常多，其中最典型的最短路径算法是Dijkstra算法。该算法是目前公认的较好的最短路径算法，可为任一源节点找出与其他所有节点的最短径路，是计算机科学与地理信息科学领域研究的热点[2]。本文根据现实城市公交线路搭建路网模型，提出一种普通的查询算法，该算法使用嵌套思想以实现最短路程及最少换乘次数的查询要求，并通过测试验证该算法的可行性。此外，本文还尝试运用Dijkstra思想，提出了一种基于最小换乘次数和最短路程的公交网络最优路径算法，并验证该算法相较普通算法的可行性与高效性。
【关键字】公交网络；普通算法；Dijkstra算法；算法测试

Research and Implementation
 of the Public Bus Inquiry Algorithm
Abstract:With the rapid economic development of China, the urban population is increasing and urban traffic congestion has become a terrible problem. To overcome this defect, someone focus on the development of public transport. In this case, it is important to improve the efficiency of the network bus inquiry system. Public transport is an important fact to reflect the urban civilization and modernization. For the general citizens, the quick inquery for finding how to arrive their destinations will provide great convenience for them. The key algorithms for building such inquery system are the shortest path algorithm and transfer algorithm. The shortest path algorithm is applied in real life and the most typical shortest path algorithm is Dijkstra algorithm. As well known, this algorithm is an effective algorithm. It can be used to find the shortest path from the starting node to other nodes.. It is widely applied in the field of computer science and geographic information sciences. Based on the road network model, this paper proposes an ordinary algorithm, which uses the idea of nest to implement the inquiry about the shortest distance and least transfer, and verifies the feasibility of the algorithm by test. In addition, inspired by Dijkstra algorithm, this thesis also proposes the shortest distance optimal path algorithm based on the minimal transfer times. We, verify the feasibility and efficiency of the algorithm and compared it with the former algorithm.
Key word: transport network  nest algorithm  Dijkstra algorithm  inquiry systems
 
目  录
摘要    I
Abstract    II
引言    - 1 -
1.需求分析    - 2 -
1.1系统需求分析    - 2 -
1.2公交线路的形式分析    - 2 -
1.3最少换乘    - 4 -
2.实验平台架构    - 5 -
2.1开发环境介绍    - 5 -
2.2数据库设计    - 5 -
2.3界面设计    - 10 -
3.普通算法设计    - 13 -
3.1算法思想    - 13 -
3.2算法描述    - 13 -
3.3 例子    - 13 -
4.Dijkstra算法设计    - 14 -
4.1算法思想    - 14 -
4.2算法描述    - 15 -
5.算法测试    - 17 -
5.1 测试目的    - 17 -
5.2 测试意义    - 18 -
5.3 测试方法    - 18 -
5.4 测试实施…………………………………………………………………….………- 18 -
5.4.1 普通算法测试    - 19 -
5.4.2 Dijkstra算法测试    - 21 -
5.4.3 测试结果分析    - 22 -
6.结束语    - 23 -
参考文献    - 24 -
致  谢    - 25 -