面向电子地图的启发式搜索技术研究(硕士)(论文40000字)
摘 要
求解最短路径是大多数路径算法的基础，在实际的生产和生活中具有广泛的应用需求，这正是本文的研究重点之一。启发式搜索在求解电子地图最短路径的应用过程中具有不可替代的作用，而启发式搜索算法的完善程度则是直接影响了电子地图路径搜寻功能的效果。
本文除了介绍电子地图的应用现状和路径规划功能的实现情况外，还介绍了A*算法，主要涉及它电子地图导航中搜索路径的工作状况，并借用A*算法在电子地图中寻径的检验结果，并在电子地图导航中得到具体使用。在静态路网中，A*算法是求解最短路径最有效的一种直接搜索方法，其求解最短路径的特点及针对最短路径问题常用的解决方法已经拥有较为广泛的研究。而本文的主要工作在于分析使用A*算法求解最短路径的优势及其实用技巧，并对其做出一定改进，同时给出实现的例子。此外，本文还深入研究了动态规划问题，分析了动态规划的特点和最短路径之间的关系，从动态规划的的实际应用角度出发，分析动态规划的多变性、规律性以及灵活性等特点。文章在分析动态规划特点的同时，还研究了动态规划的应用，利用动态规划的方法来解决在求解最短路径的实际运用中遇到的问题，同时将其中的动态规划求解过程和最短路径算法综合起来，进而使最优路径的求解过程更加具体。
本文阐述了最短路径的一般算法及其应用问题，利用动态规划的思想进一步扩展A*算法，将A*算法与动态规划相结合，使电子地图的大场景远距离搜索得以分段进行，大幅提高搜索效率，并在实际应用中对算法进行运用，侧重于模型的建立思考和证明的过程，并最终做出总结。
关键词：启发式搜索，电子地图，A*算法，动态规划
Abstract
In this paper, we study the shortest shortp search algorithm, the A* algorithm, which is mainly involved in two kinds of search shortps in game map and navigation electronic map. Discusses the theory of artificial intelligence to elbow Zhao A* algorithm is only limited to the algorithm, in the present situation of efficiency and practicality of wanting. The empirical results of the A* algorithm in the map of the virtual game are used to find the navigation map of the geographic information system.
The shortest shortp problem is one of the core problems in graph theory, which is the basis of many deeper algorithms. At the same time, the problem has a large number of practical background. Many problems on the surface of the problem with the shortest shortp, but it can be attributed to the shortest shortp problem. This paper introduces the basic concepts, the common algorithms and their application in detail, and gives an example of its application. It focuses on the process of building, thinking and proof of the model.
The essence of dynamic programming is explored, because the characteristics of dynamic programming are determined by its nature. The second part analyzes the three characteristics of the dynamic programming from two perspectives: the dynamic programming, the diversity, the pattern and the skill. In the third part, the dynamic programming and recursion, search and network flow are compared, and some of the three algorithms are compared. In this paper, we analyze the characteristics of dynamic programming, and analyze how to use these features in the problem solving. This has certain guiding significance to our problem solving practice.
Firstly, the status quo of the application of the electronic map and the realization of the shortp planning are introduced. Then, the A* algorithm is introduced, which is a kind of heuristic search method for state space representation. Subsequently, the characteristics of the shortest shortp problem and the solution methods are discussed. It focuses on the advantages of using A* algorithm to solve the shortest shortp and its practical skills, and gives some improvement to it. At the same time, it gives the examples of the realization. This is the main work of this paper. At last, the idea of dynamic programming in A* algorithm is put forward, and the A* algorithm is combined with dynamic programming, so that the long range searching in large scene is performed, and the search efficiency is greatly improved.
Keywords：heuristic search; electronic map; A* algorithm; dynamic programming
目 录
摘 要 I
Abstract II
第一章 绪论 1
1.1 研究背景和意义 1
1.2 国内外研究现状 2
1.3 论文研究内容与组织结构 5
1.4 本章小结 5
第二章 相关技术 7
2.1 电子地图技术 7
2.2 Google地图 9
2.3 Google地图API 10
2.4 开发技术基础 11
2.5 本章小结 12
第三章 算法研究与改进 13
3.1 启发式算法研究 13
3.1.1 贪心算法 13
3.1.2 Dijkstra算法 15
3.1.3 Floyd算法 17
3.1.4 Bellman-Ford算法 18
3.2 A*算法 19
3.3 改进的A*算法 21
3.3.1 A*算法改进思考 22
3.3.2 A*算法改进设计 23
3.3.3 改进算法的数据基础 24
3.3.4 改进A*算法的搜索步骤 25
3.3.6 改进A*算法的应用 27
3.4 本章小结 29
第四章 最优路径 30
4.1 最优路径的定义 30
4.2 最优路径问题算法的基本思想及基本步骤 30
4.3 动态规划 32
4.4 动态寻径 35
4.5 用于动态搜索的A*算法 36
4.6 最优路径的应用 39
4.7 本章小结 41
第五章 算法实现与分析 42
5.1 地图显示 42
5.2 算法实现 44
5.2.1 Dijkstra算法 44
5.2.2 Bellman-Ford算法 46
5.2.3 Floyd-Warshall算法 46
5.2.4 改进的A*算法 47
5.3 实验分析 49
5.4 改进的A*算法与其它算法性能的比较 52
5.5 本章小结 54
第六章 总结与展望 55
6.1 工作总结 55
6.2 工作展望 55
参考文献 57
致 谢 60 |
