求解多段图问题的并行动态规划算法  

PARALLEL DYNAMIC PROGRAMMING ALGORITHM FOR MULTISTAGE GRAPH PROBLEM

作　　者：崔焕庆[1,2,3] 王英龙[2,3] 

机构地区：[1]山东科技大学信息科学与工程学院,山东青岛266510 [2]山东省计算机网络重点实验室,山东济南250014 [3]山东省计算中心,山东济南250014

出　　处：《计算机应用与软件》2011年第12期32-34,共3页Computer Applications and Software

基　　金：国家自然科学基金(60773034);山东省科技攻关项目(2007GG2QT01007);山东省自然科学基金(ZR2009GQ002;ZR2010FQ014)

摘　　要：多段图问题是一类特殊的单源最短路径问题。在串行动态规划算法的两种实现方法的基础上,根据图中顶点的编号,提出两种在集群环境下进行任务分割的并行化求解方法,并使用MPI进行实现。实验结果表明,所提出的算法具有较高的加速比和较低的通信复杂度、时间复杂度。算法不限于某种结构的集群,通用性强。Multistage graph problem is a special single-source shortest path problem.Based on two kinds of implementations of sequential dynamic programming method,two parallel algorithms with vertex-number-based task partition in cluster are given.Both of them are implemented by MPI.Experimental results indicated that these algorithms have lower time and communication complexity and higher speedup ratio.The algorithms can also be used in any structure of cluster and is of high universality.

关 键 词：并行算法 多段图问题 最短路径 动态规划 集群 

分 类 号：TP30[自动化与计算机技术—计算机系统结构]