一种新型的动态最优路径算法研究

基金项目:

国家科技重大专项课题项目(2008ZX03006)

国家“863”高科技研究发展计划项目(2003AA142060)资助

Research on an Efficient Algorithm about Dynamic Optimal Paths

1.
School of Computer Science and Engineering,Northwestern Polytechnical University,Xi'an 710072;
2.
School of Automation,Northwestern Polytechnical University,Xi'an 710072

摘要: 目前,推移最优路径问题的讨论范围已经逐渐从静态图形转移到动态图形之上,而到现在为止能够有效的应用于动态最优路径的算法却非常少。本文中提出了一种高效的用于动态最优路径的算法—IAPLA算法,通过使用线性强化学习方案和新的更新算法,有效地减少了动态全局最优路径中不必要的更新操作,从而提高算法的收敛速度。该算法还利用阈值的思想,提出了一种可以控制最优路径精确程度的方法。实验结果表明:该算法在图形多次变化的环境下能大幅提高运算效率。
- 强化学习 /
- 动态最优路径 /
- 阈值
Abstract: The scope of the optimal path problem has gradually shift from static to dynamic graphics over time,but up to now those algorithms that can be effectively applied to the dynamic optimal path is scarce.This paper presented an efficient algorithm for dynamic optimal path-IAPLA algorithm,effectively reduced the unnecessary updates and improved the convergence speed,by using the linear reinforcement learning scheme and a new update algorithm.The algorithm also used the threshold idea,propossing a control method of optimal path accuracy.Comparing IAPLA algorithm with Floyd algorithm through simulation experiments,the experimental results show there is a significant improvement in efficiency in some circumstances.
- reinforcement learning /
- dynamic optimal path /
- threshold

[1]	Mohring R H,Schilling H,Schutz B,Wagner D,Willhalm T. Partitioning graphs to speed up Dijkstra's algorithm[A].WEA,2005.189-202.
[2]	Thorup M. Worst-case update times for fully-dynamic all-pairs shortest paths[A].2005.112-119.
[3]	Demetrescu C,Italiano G F. A new approach to dynamic all pairs shortest paths[J].Journal of the ACM,2004,(06):968-992.
[4]	Misra S,John Oommen B. Dynamic algorithms for the shortest path routing problem:learning automata-based solutions[J].IEEE Transactions on Systems Man and Cybernetics,2005,(06):1179-1192.
[5]	Misra S,Oommen J. An efficient dynamic algorithm for maintai-ning all-pairs shortest paths in stochastic networks[J].IEEE Transactions on Computers Society,2006,(06):686-702.
[6]	Berradia T,Mouzna J. Optimal path in dynamic and stochastic networks[A].2009.697-702.