随着网络时代的来临和城市规模的日益扩大,人们在出行之前,往往会查询出行的路线。现在各种各样的出行路线查询系统很多,但是优质的出行路线查询功能还有待提高,还需要进一步对出行路线的路径搜索算法进行优化。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%,极大的提高了寻径效率。经过仿真实验证明,优化后的算法达到了预期的效果。