本科毕业设计论文-公交线路查算法研究与实现.docVIP

PAGE ABSTRACT 摘要摘 要随着中国经济的发展与社会信息化水平的推进，以计算机技术为代表的信息技术的应用已经深入到各行各业中了。公交作为国家的经济大动脉是城市的重要组成部分，在国家经济和人民生活中发挥着重要作用并与人们的生活息息相关。以西安市为例，全市现有线路200余条，站点几千个，覆盖了西安市的绝大部分区域，公交已成为市民最重要的出行方式。在关于公交的众多问题当中，公交换乘是人们最关心的问题。每一个市民所熟悉的公交线路是有限的，当去一个不熟悉的地方，如何乘坐公交车前往是市民常常遇到的问题，因此我们需要构建一个城市公交换乘系统，当市民输入出发站点与目的站点后，该系统能够根据一定的规则，例如，换乘次数最少，路程最短，票价最低等，给出一些乘车的方案，市民按照乘车方案的文字描述或电子地图(GIS)的直观显示，可以准确快捷的从出发点到目的地。本文首先分析了图论及相关的背景知识，这其中包含了对公交网络进行数学建模及对其求解平均换乘次数等。在此基础上针对市民乘车的实际问题提出了多种不同的换乘算法，包括改进的Dijkstra算法，利用数据库在集合运算方面的优秀性能而提出的扩展集合算法(广度优先有哪些信誉好的足球投注网站算法)及其改进，用邻接矩阵构造换乘矩阵实现的换乘算法；人工智能方面的算法(启发式有哪些信誉好的足球投注网站算法)—A*算法在换乘方面的应用及其改进算法—A*！算法，基于蚂蚁算法实现的公交换乘算法，基于Web GIS的算法。最后，在分析完上述算法并比较其优劣势后，在Microsoft Visual C++编程环境下实现了一种算法并对其进行分析与测试。各种测试表明，作者所开发的公交线路查询系统完全符合理论假设并有一定实用价值。关 键 词：公交换乘 数学建模 Dijkstra算法 扩展集合算法 换乘矩阵算法 A*算法 A*！算法 蚂蚁算法 Web GIS ABSTRACT With the development of china’s economic and the improvement of social information level, the application of information technology 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 individual’s life and has a strong relation with people’s activity. Take XI’AN as an example, there are more than 200 bus lines and thousands of sites there. They cover almost every region of XI’AN and become the most important travel method. The bus-lines which every citizen are familiar with 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 shortest 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 descriptio