原文传递
基于查询负载频率的最短路径算法研究
| 论文题名： | 基于查询负载频率的最短路径算法研究 |
| 关键词： | 道路交通;最短路径算法;查询负载频率;标签生成 |
| 摘要： | 最短路径问题是路网中一个基本的计算问题，在GPS导航、POI推荐以及路径规划等服务中有着广泛的应用。Dijkstra算法是解决最短路径问题的常用计算算法。给定查询起点????和终点????，它按照到????点距离的远近顺序依次访问其他节点，并在到达终点????时终止搜索。该算法简单精确，但是具有很高的复杂度，无法应用于路网这种大规模网络。因此，研究人员们采用基于索引的方法来解决在线搜索开销大的问题，而标签索引表现出了绝对的优势，通过为每个节点生成一个标签允许在线性时间内计算两节点间的最短距离。 现有的最短路径算法在构建索引时仅考虑了网络的拓扑关系，忽视了最短路径查询的周期性和规律性，存在索引冗余和资源浪费的情况。基于查询负载频率的最短路径算法通过预测未来的查询需求得知节点的查询负载频率，再通过减小高频查询点的标签数量来降低总查询开销。在需求预测阶段，多任务上下文时空网络（MT-CSTN）模型将局部空间特征、时间演化特征和全局相关特征整合到统一的架构，同时引入多任务学习来捕获更强的内在时间模式。在标签生成阶段，首先根据查询负载频率建立节点间的层级关系并提出了一种新颖的基于查询负载频率的最短路径算法（QHP）。最后，在真实的数据集进行了广泛的性能研究，实验表明MT-CSTN模型在准确性上优于其他模型，而QHP算法在性能上也胜过其他的对比算法。 |
| 作者： | 曹娟 |
| 专业： | 计算机技术 |
| 导师： | 郑渤龙 |
| 授予学位： | 硕士 |
| 授予学位单位： | 华中科技大学 |
| 学位年度： | 2021 |
检索历史
应用推荐
