基于android的成市道路交道最优路径方法研究毕业论文
2021-06-30 20:39:10
摘 要
当今21世纪，信息技术迅猛发展，并被不断地应用到了生活的方方面面中，给我们的生活方式，生活质量带来了日新月异的变化。在城市中，道路交道错综复杂。如果走错了路，既浪费了时间，又增加了出行成本。而一个基于Android的路径规划系统可以有效解决这个问题，你只需输入你的起始位置和目的地，就可以轻松地得到正确的路线。为了实现这样方便的功能，就需要找出一种合适的算法来计算出最优路径。然而传统的最优路径算法Dijkstra算法，Floyd算法等都是在静态网络下求解最短路径的算法。但城市交通网络是复杂的、时刻变化的，结点数目比较多而且结点之间包含的信息不再是单一的、确定的，并且无法提前预知。另一方面，距离并不再是唯一的约束条件，时间，红绿灯数，拥堵程度等都会对用户的选择造成影响。用户想要的是综合考虑多种交通信息后得到的最优路径。所以，要想得到一条最优路径，合适的算法至关重要。
本文的研究工作主要包括以下几个方面：
（1）介绍Android技术与百度地图API的相关知识，介绍图的基本知识与城市道路网络模型的建立。
（2）通过分析比较几种现有优秀算法，包括启发式算法中的A*算法，Dijkstra算法等，来分析现有算法的优劣及适用性，为未来的算法研究提供参考。
（3）在熟练掌握百度地图的API的使用的前提下，调用它在Andrid平台实现路径规划,定位等功能，加深对国内市场上路径规划方面的发展现状的理解。
关键词：路径规划；Dijkstra算法；A*算法；Android平台；百度地图API
Abstract
Today In the 21st centery, the information technoly develops rapidly and is constantly applied to every aspects of our life,making great changes to our lifestyle and quality of life.In the city,the road is a complex network.If you went into the wrong way,you not only wasted your time,but also increased the cost of travel.But a path planing system based on Android can solve the problem effectively. What you need to do is just entering your starting position and destination, you can easily get the correct line.In order to achieve such a convenient function,it is needed to find a suitable algorithm to calculate the optimal path.However, the traditional optimal path algorithm, such as Dijkstra , Floyd and so on are only suitable to solve the shortest path algorithmin the static network.But the urban traffic network is complex and time changing, the number of nodes is much more and the information contained in the nodes is no longer single, determined, and can not predict in advance.Besides,distance is not the only constraint conditions, the time, the number of traffic lights, traffic congestion and so on will also have an impact on the user's choice.What users want is the way that intergrate a variety of information.So, in order to get an optimal path, a suitable algorithm is very important.
The main contents of my paper are as follows:
(1) I will introduce the knowledge of Android technology and BaiduMap API,and then introduce some basic concept of graphs.After this,I will use those knowledge to build the urban road network model
(2) I will analyze and compare several existing excellent algorithms, including the A* algorithm, Dijkstra algorithm and so on,and analyze there advantages,disadvantages,and applicability to provide reference to future research.
(3) In mastering of the use of Baidu Map API premise,I will call it to achieve path,planning,location and other fuctions in the platform of Android, to deepen the understanding of the development of the domestic market on the path planning.
Key Words: path planing;Dijkstra algorithm;A* algorithm;Android platform;Baidu Map API
目 录
第1章 绪论 1
1.1 研究背景及意义 1
1.2 最优路径问题研究现状 1
1.3 论文的研究内容 2
第2章 相关技术及理论知识的分析 3
2.1 Android平台简介 3
2.2 百度地图API简介 5
2.3图论的基本定义及术语 5
2.4城市道路交通网络模型建立 6
2.4.1基本要素的确定 6
2.4.2道路网络中权值的选择 7
2.4.3道路网络的存储结构 8
第3章 最优路径算法分析 10
3.1 算法的评价标准 10
3.1.1 时间复杂度 10
3.1.2 空间复杂度 10
3.2 Dijkstra算法 10
3.2.1 Dijkstra算法概述 10
3.2.2 Dijkstra算法基本思想 10
3.2.3 Dijsktra算法步骤与例子 11
3.2.4 Dijkstra算法分析 12
3.3 Floyd算法 13
3.3.1 Floyd算法概述 13
3.3.2 Floyd算法基本思想 13
3.3.3 Floyd算法例子 14
3.3.4 Floyd算法分析 14
3.4 A*算法 15
3.4.1 A*算法概述 15
3.4.2 A*算法基本思想 15
3.4.3 A*算法步骤 16
3.4.4 A*算法分析 16
3.5 几种算法的比较 16
第4章 最优路径算法的实现 18
4.1 使用百度地图API实现最优路径搜索的原因 18
4.2 需求分析 18
4.3 环境搭建 19
4.4 界面设计 21
4.5 功能实现 22
4.5.1 基本地图的实现 23
4.5.2 定位功能的实现 23
4.5.3 路径规划功能的实现 25
4.5.4 AutoCompleteTextView的使用 26
4.6 系统测试 27
第5章 总结与展望 31
5.1总结 31
5.2 展望 31
参考文献 32
致谢 33
第1章 绪论
1.1 研究背景及意义
随着城市道路交通网络的日趋复杂，人们单凭记忆来实现路径规划越来越困难，也难以保证准确率和最优性。所以越来越多的人选择了使用具有路径规划功能的软件来得到路径。用户只需要输入起始地点与目的地，就能够轻松得到一条最优路径。然而，随着用户需求的不断改变，距离已经不在是用户所考虑的唯一因素，红绿灯数，拥堵情况，收费情况等等都会影响用户对路径的选择。因此，探寻最优路径的算法也需要根据用户需求的变化而时时更新。传统的最优路径算法以Dijkstra算法为代表，属于贪心算法，存在局部最小的问题，是一种静态的局部最优算法。现在的交通网络数据规模庞大且有许多实时变化的数据，这些传统算法完全无法满足其要求。目前被广泛使用的A*算法虽然相较传统算法大幅提高了效率，但也无法解决这些问题。交通路径的最优选择问题一直是各国投资研究的重要问题。
本文将通过分析比较几种现有算法，包括A*算法，Dijkstra算法等，来分析现有算法的优劣及适用性，为未来的算法研究提供参考。同时在熟练掌握百度地图的API的使用的前提下，调用它在Andrid平台实现路径规划,定位等功能，加深对国内市场上路径规划方面的发展现状的理解。
1.2 最优路径问题研究现状
1959年，著名的荷兰数学家E.W.Dijkstra提出了Dijkstra算法，也是最早的最优路径算法。该算法被提出后受到了很多学者以及兴趣爱好者的喜爱，他们也对算法进行了修改和改进，提高了算法的效率。Bellman等学者对单源节点的最优路径问题提出了解决算法，即动态规划算法。Hart.Etal则提出了著名的启发式算法——A*算法。近年来，随着人工智能的发展，其思想为最优路径算法开启了另一扇窗。Masutti等学者通过研究组织神经网络，模仿免疫系统进行最优路径的求解。Dong G等人模仿蚂蚁觅食的行为方式，研究出了蚁群算法，来实现旅行商问题[1]。
