基于改进A星算法的城市交通寻径的研究

发布时间：2018-06-24 03:52

本文选题：A星算法 + 二叉堆　；参考：《华侨大学》2015年硕士论文

【摘要】：随着网络时代的来临和城市规模的日益扩大,人们在出行之前,往往会查询出行的路线。现在各种各样的出行路线查询系统很多,但是优质的出行路线查询功能还有待提高,还需要进一步对出行路线的路径搜索算法进行优化。A星算法是目前最广泛使用的城市出行路径搜索算法之一。它是一种启发式搜索算法,其采用的估价函数是:F(n)=G(n)+H(n),其中G(n)表示从起始顶点到当前顶点的距离的实际值,H(n)表示从当前顶点到目标顶点的距离的估算值。两者相加的结果为估价函数的估价值,选择估价值最小的顶点作为下一步要选择的顶点,如此循环运行估价函数从而生成最优路径。本文结合实际应用,对标准A算法进行了以下两方面改进:使用最小二叉堆技术优化0PEN表的查找速度,提高寻径效率。对于A星算法的估价函数,笔者在如下方面进行了改进:1.选择合适的启发函数。2.增加启发函数在估价函数中的比重。3.使用向量内积值改进启发函数在估价函数的比重。4.过滤内积值进一步优化估价函数。从而减少寻径过程中遍历的顶点数,在保证寻径质量整体不变的前提下,较大幅度的提高了寻径效率。本文在Visual Studio 2010开发平台上,使用C++语言分别实现了标准A星和改进A星的路径搜索算法,在此基础上统计它们的寻径长度、寻径时间、寻径过程中遍历的顶点数量,以此验证改进后的A星算法的可行性和有效性。经过本篇论文第四章仿真实验验证证明:以最小二叉堆存储OPEN表中的数据,使A星算法的寻径效率提高了10%。以经过过滤的向量内积值作为启发函数在估价函数中的比重值,使算法在寻径质量保持不变的同时,A星算法的寻径效率至少提高了5.2倍,遍历的顶点数至少减少了57%,极大的提高了寻径效率。经过仿真实验证明,优化后的算法达到了预期的效果。
[Abstract]:With the advent of the network era and the increasing expansion of the city scale, people often query the route of travel before they travel. At present, there are many kinds of travel route query systems, but the high quality trip route query function still needs to be improved. It is also necessary to optimize the path search algorithm of the trip route. A star algorithm is one of the most widely used urban trip path search algorithms. It is a heuristic search algorithm, and its evaluation function is: F (n) G (n) H (n), where G (n) denotes the actual value of the distance from the starting vertex to the current vertex and H (n) denotes the estimate of the distance from the current vertex to the target vertex. The result of the sum of the two is the estimated value of the valuation function, and the lowest vertex is chosen as the next selected vertex, so that the evaluation function is cycled and the optimal path is generated. Combined with practical application, this paper improves the standard A algorithm in two aspects as follows: using least square stack technology to optimize the search speed of 0PEN table and improve the efficiency of path finding. For the valuation function of the A-star algorithm, the author improves the function in the following aspects: 1. Select the appropriate heuristic function. 2. Increase the proportion of the heuristic function in the valuation function. The value of vector inner product is used to improve the proportion of heuristic function in valuation function. The filter inner product value further optimizes the evaluation function. Thus reducing the number of vertices traversing in the process of tracing, while ensuring that the overall quality of the path searching remains unchanged, the efficiency of tracing is greatly improved. In this paper, the path search algorithms of standard A star and improved A star are implemented in C language on the Visual Studio 2010 development platform. On this basis, their path searching length, seeking time and the number of vertices traversing in the path searching process are counted. The feasibility and effectiveness of the improved A-star algorithm are verified. In the fourth chapter of this paper, the simulation results show that using the least square stack to store the data in open table can improve the path finding efficiency of the A-star algorithm by 10%. Taking the filtered inner product of vector as the specific gravity value of the heuristic function in the evaluation function, the algorithm improves at least 5.2 times the searching efficiency of the A star algorithm while keeping the quality of the path finding constant, and using the value of the filtered inner product of the vector as the value of the specific gravity in the evaluation function. The number of ergodic vertices is reduced by at least 57 points, which greatly improves the path finding efficiency. The simulation results show that the optimized algorithm achieves the desired results.
【学位授予单位】：华侨大学
【学位级别】：硕士
【学位授予年份】：2015
【分类号】：U495

【参考文献】