基于动态选择启发值的改进TD-FTT算法

• 作者: 刘向宇 刘晓静 夏秀峰 朱睿 李佳佳
• 来源期刊: 计算机应用
• 学科: 工学
• 关键词: 时间依赖路网 K近邻查询 TD-FTT算法 预处理 网络泰森图
• 年，卷（期）: 2018,（1）
• 所属期刊栏目: 人工智能
• 页码范围: 120-125
• 页数: 6页
• 分类号: TP311|TP181
• 字数: 7427字
• 语种: 中文
• DOI: 10.11772/j.issn.1001-9081.2017071670

摘要

针对时间依赖路网中的K近邻(KNN)查询TD-FTT算法查询点发起时间与到达时间在同一时段的限制和预处理阶段计算时间代价大的问题,提出基于动态选择启发值改进的TD-FTT(ITD-FTT)算法.首先,在预处理阶段,根据各时段各边时间函数的最小值构建最小路网Gmin;然后,在路网Gmin中利用网络泰森图(NVD)并行计算节点最近邻来减少预处理阶段的计算时间;最后,在查找阶段通过计算节点到达时间所在时段,动态选择启发值来解除时间段的限制.实验结果显示,在预处理阶段ITD-FTT算法比TD-FTT算法计算时间减少了70.12％;在查询阶段ITD-FTT比TD-INE算法和TD-A算法在遍历节点个数上分别减少了46.52％和16.63％,响应时间比TD-INE算法和TD-A算法分别降低47.46％和18.24％.实验结果表明,ITD-FTT算法减少了查询扩展的节点数,降低了查找K近邻的时间,提高了查找效率.

作者信息

序号	姓名	单位	发文数	被引次数	H指数	G指数
1	夏秀峰	沈阳航空航天大学计算机学院	103	517	11.0	17.0
2	刘向宇	沈阳航空航天大学计算机学院	11	19	1.0	4.0
3	李佳佳	沈阳航空航天大学计算机学院	10	31	3.0	5.0
4	朱睿	沈阳航空航天大学计算机学院	5	1	1.0	1.0
5	刘晓静	沈阳航空航天大学计算机学院	2	8	1.0	2.0