基于MPI的最小费用流网络单纯形并行算法设计与实验

编号 zgly0001606921

文献类型 期刊论文

文献题名 基于MPI的最小费用流网络单纯形并行算法设计与实验

作者 吴立新  刘纪平  江锦成 

作者单位 东北大学测绘遥感与数字矿山研究所  中国矿业大学环境与测绘学院  中国测绘科学研究院  北京师范大学减灾与应急管理研究院 

母体文献 地理与地理信息科学 

年卷期 2016年01期

年份 2016 

分类号 TP338.6 

关键词 网络最小费用流  并行计算  资源分配  网络单纯形算法(NSA)  MPI 

文摘内容 网络最小费用流算法常用来解决资源流最优分配问题,传统的串行算法因时间复杂度高而不能满足大规模网络对计算效率的要求。该文用时间复杂度低的网络单纯形算法(NSA)的并行化求解大规模网络的最小费用流问题。通过分析NSA的可并行性,使用MPI分布式并行技术,设计了NSA并行算法;分析了3种常用流网络的拓扑结构特征及其与地理网络的关系;在并行环境下对计算效率进行实验测试,结果表明该算法具有显著的加速效果,峰值可达5.4。NSA并行算法应用面宽,可为区域及全国性大规模网络流资源分配方案的快速制定与政务决策提供有力支持。