时间依赖图下的最小费用路径搜索

• 作者: 傅瑜 易锋 汤庸 马慧
• 来源期刊: 电子科技大学学报
• 学科: 工学
• 关键词: 双向搜索 分段常量函数 最短路径 时间依赖费用
• 年，卷（期）: 2020,（3）
• 所属期刊栏目: 计算机工程与应用
• 页码范围: 458-466
• 页数: 9页
• 分类号: TP311
• 字数: 9076字
• 语种: 中文
• DOI: 10.12178/1001-0548.2019002

摘要

该文提出了一种时间依赖图下最小费用路径的高效搜索算法.已有的算法从起点开始向四周扩展以发现到达终点的路径,搜索空间较大,查询耗时.本文从以下两方面减少搜索空间:首先缩小顶点的有效时间区间避免无用的计算,并且在顶点的相应的时间区间的最小费用正确计算出来之后,再计算扩展路径的费用;然后提出一种双向搜索方法,从起点和终点同时出发向四周扩展路径直到两个搜索相遇,从而控制搜索空间在以起点、终点为圆心的两个小圆内.针对路径的时变依赖性设计了双向搜索的停止条件和路径生成方法,理论上证明了方法的正确性.最后,在大规模数据集上测试验证了方法的有效性.

作者信息

序号	姓名	单位	发文数	被引次数	H指数	G指数
1	汤庸	华南师范大学计算机学院	92	593	13.0	19.0
2	马慧	电子科技大学中山学院	14	32	4.0	5.0
3	傅瑜	电子科技大学中山学院	24	107	7.0	9.0
4	易锋	电子科技大学中山学院	1	0	0.0	0.0