适用于大规模网络的全源最短路径重优化算法——RASP算法

为提升大规模网络全源最短路径的求解效率,基于重优化理论提出了一种快速的精确全源最短路径求解方法——RASP(reoptimization-based all-pairs shortest path)算法.分析了异源最短路径树间的相关性和差异性;在已知单源最短路径树的基础上,基于重优化理论实现了异源最短路径树间的高效转换,进而得出高效求解全源最短路径的RASP算法;理论证明RASP算法的时间复杂度为O(3n~2+2nm).实验测试表明:无论是在稀疏还是稠密网络上,RASP算法都能有效地超越Floyd算法、n次Dijkstra算法及其改进算法.     

三维地学实体多粒度栅格剖分与布尔运算的并行算法

 三维栅格是空间单元属性插值与实体内部特征精细表达的理想模型,但海量栅格单元的快速剖分与数据压缩成为其应用瓶颈。本文分析了三维地学实体模型三维栅格剖分的研究现状,针对矢栅转换与数据存储的时间效率及空间节约问题,面向多核CPU与计算集群新型硬件架构,采用MPI并行技术,设计了一种基于八叉树的地矿实体多粒度并行三重轴向扫描剖分算法(P-TAS)。并面向矿山及地下工程开挖模拟与动态仿真需求,设计并实现了基于多粒度栅格的三维模型布尔运算算法。测试表明,该剖分算法的并行效率达50%—60%,数据压缩率达80%以上,具有推广和应用价值。