《本科毕业设计论文-公交线路查询算法研究与实现》由会员分享，可在线阅读，更多相关《本科毕业设计论文-公交线路查询算法研究与实现（66页珍藏版）》请在金锄头文库上搜索。
1、 摘要摘 要随着中国经济的发展与社会信息化水平的推进，以计算机技术为代表的信息技术的应用已经深入到各行各业中了。公交作为国家的经济大动脉是城市的重要组成部分，在国家经济和人民生活中发挥着重要作用并与人们的生活息息相关。以西安市为例，全市现有线路 200 余条，站点几千个，覆盖了西安市的绝大部分区域，公交已成为市民最重要的出行方式。在关于公交的众多问题当中，公交换乘是人们最关心的问题。每一个市民所熟悉的公交线路是有限的，当去一个不熟悉的地方，如何乘坐公交车前往是市民常常遇到的问题，因此我们需要构建一个城市公交换乘系统，当市民输入出发站点与目的站点后，该系统能够根据一定的规则，例如，换乘次数最少，
2、路程最短，票价最低等，给出一些乘车的方案，市民按照乘车方案的文字描述或电子地图(GIS)的直观显示，可以准确快捷的从出发点到目的地。本文首先分析了图论及相关的背景知识，这其中包含了对公交网络进行数学建模及对其求解平均换乘次数等。在此基础上针对市民乘车的实际问题提出了多种不同的换乘算法，包括改进的 Dijkstra 算法，利用数据库在集合运算方面的优秀性能而提出的扩展集合算法(广度优先搜索算法)及其改进，用邻接矩阵构造换乘矩阵实现的换乘算法；人工智能方面的算法(启发式搜索算法)A*算法在换乘方面的应用及其改进算法A*！算法，基于蚂蚁算法实现的公交换乘算法，基于 Web GIS 的算法。最后，在分
3、析完上述算法并比较其优劣势后，在 Microsoft Visual C+编程环境下实现了一种算法并对其进行分析与测试。各种测试表明，作者所开发的公交线路查询系统完全符合理论假设并有一定实用价值。关 键 词：公交换乘 数学建模 Dijkstra 算法 扩展集合算法 换乘矩阵算法 A*算法 A*！算法 蚂蚁算法 Web GISABSTRACT ABSTRACTWith the development of chinas economic and the improvement of social information level, the application of information t
4、echnology including computer technology have been deeply rooted in every kinds of business. Bus, as the big artery of national economic, is one of the most important parts of a city. It exerts a great important function in national economic and individuals life and has a strong relation with peoples
5、 activity.Take XIAN as an example, there are more than 200 bus lines and thousands of sites there. They cover almost every region of XIAN and become the most important travel method. Bus transfer is the most concerned problem in all these problems.The bus-lines which every citizen are familiar with
6、are limited. When we come to a place that we never come to before, how to get there with bus is the most frequent problem. So we need to build a city bus transfer system. When the users input the start site and the destination site, according to some rules, for example, the least transfer, the short
7、est path, and the lowest price, etc, the system can give us some suggestions on bus transfer, we can get to our destinations in the light of these suggestions with a written descriptions or map description using GIS accurately and conveniently.In this essay, the author first introduced some knowledg
8、e about graph theory and some other backgrounds, including building up a math model about bus network, resolving average transfer times based on this, etc. Based on this model, the author propose lots of different transfer algorithms, including Dijkstra algorithm and its improvement; expanding set a
9、lgorithm (breath first search about graph) and its improvement which depending on the databases excellent performance on set mathematic operations, using adjacency matrix to construct transfer matrix algorithm, artificial intelligence algorithm (inspiring algorithm)A* algorithm used on bus transferr
10、ing and its improvementA*! algorithm , bus transfer algorithm based on ant algorithm, WEB GIS algorithm.At last, after analysised the algorithms mentioned above and compared the superiorities and inferiors of these algorithms, the author implement one of these algorithms in the visual C+ environment
11、, then do some analysis and tests. The tests manifest the bus ABSTRACT transfer system the author developed fits the theories very well and has some practical values. Keywords: bus transfer math module Dijkstra algorithm expanding set algorithm transfer matrix algorithm A* algorithm A*! algorithm an
12、t algorithm WEB GIS 目录 i目 录第一章 绪 论 .11.1 城市公交问题提出的背景与意义 .11.2 我国城市公交及国内外研究现状 .21.3 研究的目的，内容及方法 .31.4 公交换乘问题及公交网络建模的概况 .4第二章 公交网络的拓扑建模 .72.1 图的相关概念 .72.2 城市公交网络模型的建立 .92.2.1 公交乘车模型 .92.2.2 公交网络的有向图结构 .102.2.3 公交网络拓扑图中的权值的设定 .132.3 公交网络性能与平均换乘次数 .142.3.1 公共交通网的技术指标 .142.3.2 公共交通线路网平均换乘次数的研究 .162.3.3 平均公交换乘次数的实例分析 .19第三章 求解公交换乘问题的各类算法设计 .223.1DIJKSTRA算法及其改进 .223.1.1Dijkstra 算法简介 .223.1.2 将 Dijkstra 算法直接运用在公交换乘方面所存在的问题 .223.1.3 改进的 Dijkstra 算法 .233.1.4 Dijkstra 算法的应用范围 .233.2 扩展集合算法 .233.2.1 算法概要 .243.2.2 算法的不足 .243.2.3 算法的改进 .
