基于时序图的多约束路径查询

论文摘要

近年来,随着大数据时代的到来以及在线社交网络的兴起,图上的算法研究越来越受到人们的重视,因为无论是社交网络还是交通道路网都可以被抽象为一张图。迄今为止,许多优秀的图算法已经被运用到实际应用中,并且给人们的生活带来了极大的便利。但是现有的图算法大都基于静态图并且只考虑单个属性,而忽略了实际生活中的时序性以及多属性特征。比如在路网中,不同时刻下两点间是否存在汽车班次;又比如出行时,除了考虑时间因素,人们往往还会考虑道路拥挤程度,汽车油耗等多个属性因素。综合以上情况,本文研究了基于时序图的多约束路径查询问题,在传统的路径查询算法基础上进行扩展和创新,将时序信息和多属性信息嵌入到对图的建模和处理当中,更加真实地模拟了实际情况,也为用户提供了更加准确和细致的结果。本文致力于在时序图上找到满足用户提出的多个属性上的约束的目标路径,这里的目标路径包括最快到达路径以及运行时间最短路径。为了有效并且高效地解决上述问题,本文分别提出了基于Skyline路径的算法以及基于双向搜索的算法。它们充分考虑了图上的时序特征和多属性特征,并在查询的过程中不断剪枝和优化,极大地减少了搜索空间。基于Skyline路径的算法首先通过将时序图转静态图来解决时序性的问题,随后通过计算Skyline路径来解决多属性的问题,最后根据前面两步的结果挑选目标路径;双向搜索算法基于两次遍历思想,先反向搜索判断路径是否满足属性上的约束要求,再正向搜索求解最终的目标路径。本文在真实数据集上进行的对比实验证明了这两个算法的高效性和有效性。最后,本文实现了基于时序图的多约束路径查询系统。

论文目录

摘要

Abstract

第一章绪论

1.1 研究背景及意义

1.2 课题研究现状

1.3 课题研究内容

1.4 文章组织结构

第二章基于时序图的多约束路径查询定义

2.1 多属性时序图

2.2 多约束时序路径

2.3 目标路径

2.4 本章小结

第三章基于Skyline路径的多约束时序路径查询方法

3.1 时序图转静态图

3.2 Skyline路径

3.2.1 Skyline简介

3.2.2 路径支配策略

3.2.3 Skyline路径查询算法

3.3 目标路径求解

3.3.1 最快到达路径查询

3.3.2 运行时间最短路径查询

3.4 本章小结

第四章基于双向搜索的多约束时序路径查询方法

4.1 双向搜索简介

4.2 反向搜索

4.2.1 多属性判断标准

4.2.2 反向搜索算法

4.3 正向求解目标路径

4.3.1 最快到达路径查询

4.3.2 运行时间最短路径查询

4.4 本章小结

第五章实验分析

5.1 实验设置

5.1.1 数据集

5.1.2 参数值设定

5.2 算法性能比较

5.2.1 算法高效性

5.2.2 算法有效性

5.3 本章小结

第六章时序图上多约束路径查询系统设计与实现

6.1 系统实现环境

6.1.1 系统架构

6.1.2 开发环境

6.2 系统具体实现

6.2.1 用户查询模块

6.2.2 请求处理模块

6.2.3 结果展示模块

6.3 系统展示

6.4 本章小结

第七章总结与展望

7.1 全文总结

7.2 工作展望

参考文献

攻读硕士学位期间发表的论文

致谢

文章来源

类型: 硕士论文

作者: 时久超

导师: 刘冠峰

关键词: 时序图,多约束,搜索算法

来源: 苏州大学

年度: 2019

分类: 基础科学,信息科技

专业: 数学,计算机软件及计算机应用

单位: 苏州大学

分类号: O157.5;TP301.6

DOI: 10.27351/d.cnki.gszhu.2019.000684

总页数: 65

文件大小: 3821K

下载量: 20

基于时序图的多约束路径查询

论文摘要

论文目录

文章来源

相关论文文献

猜你喜欢