基于动态选择启发值的改进TD-FTT算法
来源：计算机应用杂志2018年第1期北京时间：
作者：李佳佳, 刘晓静, 刘向宇, 夏秀峰, 朱睿
单位：沈阳航空航天大学 计算机学院, 沈阳 110136
摘要：针对时间依赖路网中的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近邻的时间，提高了查找效率。
关键词：时间依赖路网,K近邻查询,TD-FTT算法,预处理,网络泰森图
基金资助：国家自然科学基金资助项目（61502317）。
