一类标准矩形网络节点间最短路径的求解方法
CSTR:
作者:
作者单位:

1. 东北大学信息科学与工程学院,沈阳110004;
2. 辽宁工程技术大学电气与控制工程学院,辽宁葫芦岛125105.

作者简介:

刘宏志

通讯作者:

中图分类号:

TP391

基金项目:

国家自然科学基金项目(61403174).


A kind of solving method for the shortest path between standard rectangular network nodes
Author:
Affiliation:

1. College of Information Science and Engineering,Northeastern University,Shenyang 110004,China;
2. Faculty of Electrical and Control Engineering,Liaoning Technical University,Huludao 125105,China.

Fund Project:

  • 摘要
  • |
  • 图/表
  • |
  • 访问统计
  • |
  • 参考文献
  • |
  • 相似文献
  • |
  • 引证文献
  • |
  • 资源附件
  • |
  • 文章评论
    摘要:

    针对常见的交通道路最短路径问题, 提出标准矩形网络的概念, 分析其节点间最短路径的性质, 并在此基础上给出一种新颖的最短路径求解算法. 该算法利用标准矩形网络的几何性质, 简化了搜索方向和步长的判断, 同时指出常见的交通道路网络一般均可以整体或部分化为标准矩形网络. 与常见的求取最短路径的Dijkstra、Floyd、ACO、A* 等算法进行仿真实验比较, 实验结果表明, 对于大规模标准矩形道路网络, 所提出算法具有更好的寻优精度、稳定性和寻优速度.

    Abstract:

    In view of the shortest path problem of the common traffic road, the standard rectangular network concept is proposed, the properties of the shortest path between nodes are analyzed, and a novel shortest path algorithm based on the standard rectangular network(SRNSP) is presented. By using the geometric properties of the standard rectangular network, the search direction and step judgment are simplified. Meanwhile, it is pointed out that some or even all of the common traffic road networks can be converted into standard rectangular networks. Compared with the common Dijkstra, Floyd, ACO and A* algorithms for solving the shortest path problem, the experiment results show that the proposed algorithm has better optimization accuracy, stability and searching speed for the large-scale standard rectangular road network.

    参考文献
    相似文献
    引证文献
引用本文

刘宏志 高立群 欧阳海滨.一类标准矩形网络节点间最短路径的求解方法[J].控制与决策,2016,31(4):623-628

复制
分享
文章指标
  • 点击次数:
  • 下载次数:
  • HTML阅读次数:
  • 引用次数:
历史
  • 收稿日期:2015-01-26
  • 最后修改日期:2015-07-25
  • 录用日期:
  • 在线发布日期: 2016-04-20
  • 出版日期:
文章二维码