基于安卓Android的城市道路交通最优路径算法研究

基于安卓Android的城市道路交通最优路径算法研究(任务书,开题报告,论文14000字,程序代码)
摘要
当今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章：简要概述了本文研究的背景及意义，分析了最优路径问题的研究现状及其在交通网络环境下的特点。
    第2章：介绍一下Android技术的相关知识及百度地图API的相关介绍，介绍一下图的基本知识与城市道路网络模型的建立。
    第3章：介绍算法的评价标准，分析最优路径算法Dijkstra算法，Floyd算法，A*算法等的优劣性及适用性。
    第4章：介绍在Android平台下实现最优路径查找的过程。
    第5章：总结和展望，总结自己完成的工作。
 

目 录
第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