留言板

尊敬的读者、作者、审稿人, 关于本刊的投稿、审稿、编辑和出版的任何问题, 您可以本页添加留言。我们将尽快给您答复。谢谢您的支持!

姓名
邮箱
手机号码
标题
留言内容
验证码

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

汪芳 戴冠中 慕德俊

汪芳, 戴冠中, 慕德俊. 一种新型的动态最优路径算法研究[J]. 机械科学与技术, 2012, 31(11): 1885-1887,1892.
引用本文: 汪芳, 戴冠中, 慕德俊. 一种新型的动态最优路径算法研究[J]. 机械科学与技术, 2012, 31(11): 1885-1887,1892.
Wang Fang, Dai Guanzhong, Mu Dejun. Research on an Efficient Algorithm about Dynamic Optimal Paths[J]. Mechanical Science and Technology for Aerospace Engineering, 2012, 31(11): 1885-1887,1892.
Citation: Wang Fang, Dai Guanzhong, Mu Dejun. Research on an Efficient Algorithm about Dynamic Optimal Paths[J]. Mechanical Science and Technology for Aerospace Engineering, 2012, 31(11): 1885-1887,1892.

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

基金项目: 

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

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

详细信息
    作者简介:

    汪芳(1977-),讲师,博士研究生,研究方向为计算机软件及网络安全,wangf@nwpu.edu.cn

Research on an Efficient Algorithm about Dynamic Optimal Paths

  • 摘要: 目前,推移最优路径问题的讨论范围已经逐渐从静态图形转移到动态图形之上,而到现在为止能够有效的应用于动态最优路径的算法却非常少。本文中提出了一种高效的用于动态最优路径的算法—IAPLA算法,通过使用线性强化学习方案和新的更新算法,有效地减少了动态全局最优路径中不必要的更新操作,从而提高算法的收敛速度。该算法还利用阈值的思想,提出了一种可以控制最优路径精确程度的方法。实验结果表明:该算法在图形多次变化的环境下能大幅提高运算效率。
  • [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.
  • 加载中
计量
  • 文章访问数:  134
  • HTML全文浏览量:  25
  • PDF下载量:  3
  • 被引次数: 0
出版历程
  • 收稿日期:  2011-10-20
  • 刊出日期:  2015-06-10

目录

    /

    返回文章
    返回