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

冯琳耀; 袁林旺; 罗文; 李润超; 俞肇元

doi:10.3969/j.issn.0372-2112.2014.05.003

您当前的位置：

首页 >

文章列表页 >

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

学术论文 | 更新时间：2025-07-16

- 节点约束型最短路径的几何代数算法
- Geometric Algebra-Based Algorithm for Solving Nodes Constrained Shortest Path
- 电子学报 2014年42卷第5期页码：846-851
- 作者机构：
  
  1. 南京师范大学虚拟地理环境教育部重点实验室,江苏,南京,210023
  2. 南京师范大学江苏省大规模复杂系统数值模拟重点实验室,江苏,南京,210023
  3. 南京师范大学虚拟地理环境教育部重点实验室,江苏,南京,210023
  4. 南京师范大学江苏省大规模复杂系统数值模拟重点实验室江苏南京,210023
- 作者简介：
- 基金信息：
  
  国家自然科学基金重点项目 (No.41231173);江苏省自然科学基金 (No.BK2012454)，教育部新世纪人才培养计划 (No.NECT-12-0735)
- DOI：10.3969/j.issn.0372-2112.2014.05.003
  中图分类号： P208TP301.6
- 纸质出版：2014
- 稿件说明：
移动端阅览
冯琳耀, 袁林旺, 罗文, 等. 节点约束型最短路径的几何代数算法[J]. 电子学报, 2014,42(5):846-851.

FENG Lin-yao, YUAN Lin-wang, LUO Wen, et al. Geometric Algebra-Based Algorithm for Solving Nodes Constrained Shortest Path[J]. Acta Electronica Sinica, 2014, 42(5): 846-851.
冯琳耀, 袁林旺, 罗文, 等. 节点约束型最短路径的几何代数算法[J]. 电子学报, 2014,42(5):846-851. DOI： 10.3969/j.issn.0372-2112.2014.05.003.

FENG Lin-yao, YUAN Lin-wang, LUO Wen, et al. Geometric Algebra-Based Algorithm for Solving Nodes Constrained Shortest Path[J]. Acta Electronica Sinica, 2014, 42(5): 846-851. DOI： 10.3969/j.issn.0372-2112.2014.05.003.

摘要

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

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.

关键词

Keywords

references

浏览量

2979

下载量

CSCD

文章被引用时，请邮件提醒。

提交

工具集

关联资源

基于几何代数的电磁矢量传感器阵列抗强干扰参数估计算法

时延PCNN及其用于求解最短路径

PIR传感器网络中行为轨迹重构的几何代数方法