全部 标题 作者
关键词 摘要

OALib Journal期刊
ISSN: 2333-9721
费用:99美元

查看量下载量

相关文章

更多...
电子学报  2014 

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

DOI: 10.3969/j.issn.0372-2112.2014.05.003, PP. 846-851

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

Full-Text   Cite this paper   Add to My Lib

Abstract:

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

References

[1]  林澜,闫春钢,等.基于稳定分支的变权网络最优路径算法[J].电子学报,2006,34(7):1222-1225. Lin Lan,Yan Chungang,et al.Optimal path algorithm in varying-weight networks based on stable branch[J].Acta Electronica Sinica,2006,34(7):1222-1225.(in Chinese)
[2]  曹政才,等.面向城市交通网络的一种新型动态路径寻优方法[J].电子学报,2012,40(10):2043-2067. Cao Zhengcai,et al.A novel dynamic path optimization method for urban traffic networks[J].Acta Electronica Sinica,2012,40(10):2043-2067.(in Chinese)
[3]  郑年波,陆峰,李清泉,等.顾及转向延误的时间依赖A*最短路径算法[J].测绘学报,2010,39(5):534-539. Zheng Nianbo,Lu Feng,Li Qingquan,et al.The adaption of A* algorithm for least-time paths in time-dependent transportation networks with turn delays[J].Acta Geodaeticaet Cartographica Sinica,2010,39(5):534-539.(in Chinese)
[4]  王晟,李乐民.一种改进的多约束最佳路径算法研究[J].电子学报,2004,32(4):529-535. Wang Sheng,Li Lemin.An enhanced algorithm for multiple constraints optimal path calculation[J].Acta Electronica Sinica,2004,32(4):529-535.(in Chinese)
[5]  杨雅君,高宏,李建中.多维代价图模型上最优路径查询问题的研究[J].计算机学报,2012,35(10):2147-2158. Yang Yajun,Gao Hong,LI Jianzhong.Optimal path query based on cost function over muti-cost graphs[J].Chinese Journal of Computers,2012,35(10):2147-2158.(in Chinese)
[6]  于德新,等.重大灾害条件下基于GIS的最短路径改进算法[J].交通运输工程学报,2011,11(4):123-126. Yu De-xin,et al.Shortest path improved algorithm based on GIS under large-scale disaster[J].Journal of Traffic and Transportation Engineering,2011,11(4):123-126.(in Chinese)
[7]  Staples G S,Schott R.Dynamic geometric graph processes:Adjacency operator approach[J].Advances in Applied Clifford Algebras,2010,20:893-921.
[8]  Yu Zhaoyuan,Yuan Linwang,Luo Wen.Clifford algebra and GIS spatial analysis algorithms the case study of geographical network and voronoi analysis[A].Procedings of GraVisMa[C].Brno:EUROGRAPHICS,2010.155-158.
[9]  Dorst L,Fontijne D,Mann S.Geometric Algebra for Computer Science:An Object-Oriented Approach to Geometry[M].San Fransisco:Morgan Kaufmann Publishers,2007.
[10]  Yuan L W,Yu Z Y,Chen S F,et al.CAUSTA:Clifford algebra based unfied spatio-temporal analysis[J].Transactions in GIS,2010,14(s1):59-83.
[11]  孙全.满足指定节点约束的路由算法[J].计算机工程与应用,2005,(16):3-5. Sun Quan.Routing algorithm satisfying explicit node constraint[J].Computer Engineering and Applications,2005,(16):3-5.(in Chinese)
[12]  Yuan Linwang,Yu Zhaoyuan,Luo Wen,et al.A 3D GIS spatial data model based on conformal geometric algebra[J].Sci China Earth Sci.,2011,54(1):101-112.
[13]  Yuan L W,Lü G N,Luo W,et al.Geometric algebra method for multidimensionally-unified GIS computation[J].Chinese Science Bulletin,2012,57(7):802-811.
[14]  谢维信,等.基于 Clifford 代数的混合型传感器网络覆盖理论分析[J].中国科学(E),2007,37(8):1018-1031. Xie Weixin,et al.Coverage analysis for sensor networks based on Clifford algebra[J].Science in China (Series F:Information Sciences),2008,51(5):460-475.(in Chinese)
[15]  Zhang Jiyi,Yuan Linwang,et al.Shortest path algorithm in GIS network analysis based on Clifford algebra[A].Procedings of 2nd ICFCC[C].Wuhan:IEEE,2010.432-436.
[16]  陆峰.最短路径算法:分类体系与研究进展[J].测绘学报,2001,30(3):269-275. Lu Feng.Shortest path algorithms:Taxonomy and advance in research[J].Acta Geodaetica Cartographica Snica,2001,30(3):269-275.(in Chinese)
[17]  卢锡城,白建军,等.一种基于分时的LEO卫星网络无环路由算法[J].通讯学报,2005,26(5):9-16. Lu Xicheng,Bai Jianjun,et al.Discrete time based loop-free routing algorithm for LEO satellite networks[J].Journal on Communications,2005,26(5):9-16.(in Chinese)

Full-Text

Contact Us

service@oalib.com

QQ:3279437679

WhatsApp +8615387084133