检索结果-南通市图书馆

检索条件"主题词=内积值过滤"

共 1 条记录，以下是1-10 订阅

全选清除本页清除全部题录导出标记到"检索档案"

详细简洁

排序：

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

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

引用

作者：潘长安华侨大学

学位级别：硕士

随着网络时代的来临和城市规模的日益扩大,人们在出行之前,往往会查询出行的路线。现在各种各样的出行路线查询系统很多,但是优质的出行路线查询功能还有待提高,还需要进一步对出行路线的路径搜索算法进行优化。A星算法是目前最广泛使... 详细信息

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

关键词： A星算法二叉堆估价函数向量内积内积值过滤

来源：

同方学位论文库评论

在线全文

同方学位论文库

学校读者我要写书评

暂无评论

全选清除本页清除全部题录导出标记到“检索档案”

共1页 << < 1 > >>

回到顶部

执行限定条件

欢迎您,

建议与咨询留下您的常用邮箱和电话号码，以便我们向您反馈解决方案和替代方法

时间限定

文献类型

馆藏选择

核心期刊

语言

文献类型

帮助

文字说明：

检索规则说明：

检索范例：

分类表

所选分类

限定检索结果

文献类型

馆藏范围

日期分布

学科分类号

主题

机构

作者

语言

在线全文

请选择保存的检索档案：

请选择收藏分类：

通借通还

欢迎您,

建议与咨询 留下您的常用邮箱和电话号码，以便我们向您反馈解决方案和替代方法

时间限定

文献类型

馆藏选择

核心期刊

语言

文献类型

帮助

文字说明：

检索规则说明：

检索范例：

分类表

所选分类

限定检索结果

文献类型

馆藏范围

日期分布

学科分类号

主题

机构

作者

语言

在线全文

请选择保存的检索档案： 新增检索档案 确定 取消

请选择收藏分类： 新增自定义分类 确定 取消

通借通还

建议与咨询留下您的常用邮箱和电话号码，以便我们向您反馈解决方案和替代方法

请选择保存的检索档案：

请选择收藏分类：