动态网络最短路问题的复杂性与近似算法

被引：18

作者：

林澜 ^{[1
]}

闫春钢 ^{[1
]}

蒋昌俊 ^{[1
]}

周向东 ^{[2
]}

机构：

[1] 同济大学电子与信息工程学院

[2] 复旦大学计算机与信息技术系

来源：

计算机学报 | 2007年 / 04期

关键词：

动态网络; 最短路; 算法; NP-困难; 稳定性;

D O I：

暂无

中图分类号：

TP18 [人工智能理论];

学科分类号：

081104 ; 0812 ; 0835 ; 1405 ;

摘要：

有向网络的最短路问题在交通、通信系统的最优路径计算以及多阶段决策过程的最优轨线设计等实际问题中有着重要应用.经典模型及算法解决固定弧权条件下的最短路问题,而实际中,网络往往是动态的,即弧权依赖于时间变化,例如在交通拥堵时运行时间会变长,这时经典的最短路算法不再适用.文中证明了动态网络的最短路问题是NP-困难的;给出了最短路稳定性的充要条件,并在此基础上提出一种基于稳定区间的近似算法,通过模拟实验验证了该算法的有效性.

引用

页码：608 / 614

页数：7