| 时间依赖代价函数下的最优路径查询问题研究 |
| |
| 引用本文： | 杨雅君,高宏,李建中.时间依赖代价函数下的最优路径查询问题研究[J].计算机学报,2012,35(11):2247-2264. |
| |
| 作者姓名： | 杨雅君 高宏 李建中 |
| |
| 作者单位： | 哈尔滨工业大学计算机科学与技术学院 哈尔滨 150001 |
| |
| 基金项目： | 国家"九七三"重点基础研究发展规划项目基金，国家自然科学基金，黑龙江省自然科学基金，中国博士后科学基金，黑龙江省博士后基金，哈尔滨工业大学科研创新基金"中央高校基本科研业务费专项基金" |
| |
| 摘 要： | 作者研究了时间依赖图下,具有时间限制的费用代价最优路径的查询问题.目前有关时间依赖图上的最短路径查询的研究工作解决的是最短旅行时间问题(TDSP),这些工作都利用了以下性质:到达某个顶点的最早时刻可以通过到达其邻居的最早时刻计算得出.然而,在计算具有时间限制的费用代价最优路径时,该性质并不成立.因此,目前解决TDSP问题的方法均不能解决文中面对的问题.对此作者提出一个新的算法用于计算时间依赖图模型上的满足时间限制的费用代价最优路径.该算法适用于有向图和无向图.作者证明了算法的时间复杂度和空间复杂度分别为O(knlogn+mk2logk)和O((n+m)k).最后,作者通过真实数据集上的实验,验证了该算法的有效性.
|
| 关 键 词： | 时间依赖图 代价函数 最优路径 |
Finding the Optimal Path under Time-Dependent Cost Function on Graphs |
| |
| YANG Ya-Jun
,
GAO Hong
,
LI Jian-Zhong.Finding the Optimal Path under Time-Dependent Cost Function on Graphs[J].Chinese Journal of Computers,2012,35(11):2247-2264. |
| |
| Authors: | YANG Ya-Jun GAO Hong LI Jian-Zhong |
| |
| Affiliation: | (School of Computer Science and Technology,Harbin Institute of Technology,Harbin 150001) |
| |
| Abstract: | |
| |
| Keywords: | |
| 本文献已被 CNKI 万方数据 等数据库收录！ |
|
