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

摘要

随着网络时代的来临和城市规模的日益扩大，人们在出行之前，往往会查询出行的路线。现在各种各样的出行路线查询系统很多，但是优质的出行路线查询功能还有待提高，还需要进一步对出行路线的路径搜索算法进行优化。
　　A星算法是目前最广泛使用的城市出行路径搜索算法之一。它是一种启发式搜索算法，其采用的估价函数是：F(n)=G(n)+H(n)，其中G(n)表示从起始顶点到当前顶点的距离的实际值，H(n)表示从当前顶点到目标顶点的距离的估算值。两者相加的结果为估价函数的估价值，选择估价值最小的顶点作为下一步要选择的顶点，如此循环运行估价函数从而生成最优路径。
　　本文结合实际应用，对标准A算法进行了以下两方面改进：
　　?使用最小二叉堆技术优化0PEN表的查找速度，提高寻径效率。
　　?对于A星算法的估价函数，笔者在如下方面进行了改进：
　　1.选择合适的启发函数。
　　2.增加启发函数在估价函数中的比重。
　　3.使用向量内积值改进启发函数在估价函数的比重。
　　4.过滤内积值进一步优化估价函数。
　　从而减少寻径过程中遍历的顶点数，在保证寻径质量整体不变的前提下，较大幅度的提高了寻径效率。
　　本文在Visual Studio2010开发平台上，使用C++语言分别实现了标准A星和改进A星的路径搜索算法，在此基础上统计它们的寻径长度、寻径时间、寻径过程中遍历的顶点数量，以此验证改进后的A星算法的可行性和有效性。
　　经过本篇论文第四章仿真实验验证证明：
　　以最小二叉堆存储OPEN表中的数据，使A星算法的寻径效率提高了10％。
　　以经过过滤的向量内积值作为启发函数在估价函数中的比重值，使算法在寻径质量保持不变的同时，A星算法的寻径效率至少提高了5.2倍,遍历的顶点数至少减少了57%，极大的提高了寻径效率。
　　经过仿真实验证明，优化后的算法达到了预期的效果。

目录

封面

声明

中文摘要

英文摘要

目录

第1章 绪论

1.1 引言

1.2研究背景

1.3研究意义

1.4 路径搜索的研究现状及发展动态

1.5论文的组织结构

第2章 路径搜索技术理论基础

2.1图搜索理论基础

2.2盲目型搜索算法

2.3 启发型搜索算法

2.4 Dijkstra算法

2.5 A星算法

2.6 本章小结

第3章 标准A星算法的优化和改进

3.1 标准A星算法的搜索过程

3.2 标准A星算法的不足

3.3 优化OPEN表

3.4 改进估价函数

3.5本章小结

第4章 仿真实验与结论分析

4.1仿真实验平台简介

4.2 Dijkstra算法与标准A星算法的对比

4.3 标准A星算法与A①星算法的对比

4.4曼哈顿距离、对角线距离、欧几里得距离的对比

4.5 A②星算法与A③星算法的对比

4.6 A③星算法与A④星算法、A⑤星算法的对比

4.7 综合对比:未经优化的标准A星算法与A⑤星算法的对比

第5章 总结和展望

5.1 总结

5.2 展望

参考文献

致谢

在学期间发表的学术论文