电子学报

• 学术论文 • 上一篇    下一篇

节点约束型最短路径的几何代数算法

冯琳耀1, 袁林旺1,2, 罗文1, 李润超1, 俞肇元1   

  1. 1. 南京师范大学虚拟地理环境教育部重点实验室, 江苏南京 210023;
    2. 南京师范大学江苏省大规模复杂系统数值模拟重点实验室,江苏南京 210023
  • 收稿日期:2013-04-08 修回日期:2013-05-09 出版日期:2014-05-25 发布日期:2014-05-25
  • 作者简介:冯琳耀 男,1990年生于山西运城.南京师范大学虚拟地理环境教育部重点实验室硕士研究生.研究方向为地理信息系统算法. E-mail:fenglinyao@gmail.com袁林旺(通信作者) 男,1973年生于江苏海安,博士,南京师范大学教授,博士生导师,研究方向为地理信息系统理论与方法. E-mail:yuanlinwang@njnu.edu.cn
  • 基金资助:
    国家自然科学基金重点项目(No.41231173);江苏省自然科学基金(No.BK2012454),教育部新世纪人才培养计划(No.NECT-12-0735)

Geometric Algebra-Based Algorithm for Solving Nodes Constrained Shortest Path

FENG Lin-yao1, YUAN Lin-wang1,2, LUO Wen1, LI Run-chao1, YU Zhao-yuan1   

  1. 1. Key Laboratory of VGE, Ministry of Education, Nanjing Normal University, Nanjing, Jiangsu 210023, China;
    2. Jiangsu Provincial Key Laboratory for NSLSCS, Nanjing Normal University, Nanjing, Jiangsu 210023, China
  • Received:2013-04-08 Revised:2013-05-09 Online:2014-05-25 Published:2014-05-25

摘要: 面向网络分析应用中复杂条件约束下的最短路径求解问题,引入几何代数进行网络分析算法构造.建立了基于几何代数的网络模型和双边搜索算法,以寻找经过指定必经节点且弧段最少的最短路径求解为例,进行了算法实现.基于道路网络数据的分析显示,本算法利用外积运算直接判断约束节点,算法具有更好的通用性和较少的路径遍历次数,且在多对多路径求解及多用户并行求解上具有优势.

关键词: 最短路径, 节点型约束, 几何代数, 矩阵外积

Abstract: Focusing on the solving of the shortest paths in the conditions of complicated constraints for network analysis and application,geometric algebra is used to develop the network analysis algorithms.We built a network model and bilateral search algorithms based on the multivector representation and multidimensional operators of geometric algebra.Then,we implemented the algorithm by taking the example of finding the shortest paths that pass the specified necessary nodes and the least segments.According to the experiment analysis of the road network data,this algorithm can directly estimate the constrained nodes by applying the outer algorithm and has better versatility and less path traversal times.Moreover,this algorithm has an advantage on many-to-many path solution and multi-user parallel solution.

Key words: shortest path, nodes constraint, geometric algebra, outer product of matrices

中图分类号: