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

《节点约束型最短路径的几何代数算法.pdf》由会员上传分享，免费在线阅读，更多相关内容在行业资料-天天文库。

1、第5期电子学报V01．42No．52014年5月ACTA眦CⅡ10NICASINICAMav2014节点约束型最短路径的几何代数算法冯琳耀，袁林旺，一，罗文，李润超，俞肇元(1．南京师范大学虚拟地理环境教育部重点实验室，江苏南京210023；2．南京师范大学江苏省大规模复杂系统数值模拟重点实验室，江苏南京210023)摘要：面向网络分析应用中复杂条件约束下的最短路径求解问题，引入几何代数进行网络分析算法构造．建立了基于几何代数的网络模型和双边搜索算法，以寻找经过指定必经节点且弧段最少的最短路径求解为

2、例，进行了算法实现．基于道路网络数据的分析显示，本算法利用外积运算直接判断约束节点，算法具有更好的通用性和较少的路径遍历次数，且在多对多路径求解及多用户并行求解上具有优势．关键词：最短路径；节点型约束；几何代数；矩阵外积中图分类号：P208，TP301．6文献标识码：A文章编号：0372．2112(2014)05．0846．06电子学报URL：http：／／www．~jouma1．org．caDOI：10．3969／j．issn．0372—2112．2014．05．003GeometricAlgeb

3、ra-BasedAlgorithmforSolvingNodesConstrainedShortestPathFENGLin．yao，YUANLin．wang’，LUOWen，LIRun．chao，YUZhao—yuan(1．研LaboratoryofVGE，MinistryofEducatwn，NanjingNormalUniversity，Nanjing，Jiangsu210023，China2．JiangsuProvincialKeyLaboratoryforNSLSCS，NanjingNor

4、malUniversity，Nan]ing，~angsu210023，Ch／na)Abstract：FocusingOilthesolvingoftheshortestpathsintheconditionsofcomplicatedconstraintsfornetworkanalysisandappfication，geometricalgebraisusedtodevelopthenetworkanaly~salgorithms．Webuiltanetworkmodelandbfla~rats

5、earchal—gorithmsbasedonthemultivectorrepresentationandmultidimensionaloperatorsofgeometricalgebra．Then，weimplementedtheal—gorithmbytakingtheexampleoffindingtheshortestpathsthatpassthespecifiednecessarynodesandtheleastsegments．Accordingtotheexperimentan

6、alyfisoftheroadnetworkdata，thisalgorithmcarldirectlyestimatethecons~ainednodesbyapplyingtheouteralgorithmandhasbetterversatilityandlesspathIraversaltimes．Moreover，thisalgorithmhasanadvantageonmany-to-manypathsolutionandmulti—usefparallelsolution．Keywor

7、ds：shortestpath；nodesconstraint；geometricalgebra；outerproductofmail'ices利用邻接表进行层次遍历，不仅难以兼顾必经节点，而1引言且难以解决回路问题，导致算法复杂度的大幅增加．且给定约束的最优路径选择是路径规划的核心．基于现有研究多考虑带权网络，对不带权网络的研究较少，传统的Dijkstra算法、Floyd算法及A算法等，发展了一但当考虑到运输中转，数据路由调度代价时，经过节点系列面向地理网络或特定路径规划的优化算法L1J．随最少的

8、不带权路径问题的求解则至关重要．着应用领域的不断拓展，网络规模与复杂度不断增大，几何代数可直接支撑高维分析，基于几何代数的网用户需求也日趋复杂化，现有算法难以应对这一需求，络分析算法具有结构清晰、算法简单等特点l7J．其优主要表现为：①节点与弧段数大幅增加，导致路径搜索越的几何构造和分析能力可为多维道路网络表达与分算法复杂度增加较快；②多只考虑距离权重，缺乏节点析计算提供有效的支撑．其空间自定义，运算的对象无和弧段的多属性集成；③对节点数目和经过特定节点的关与维度无关