| 求解多段图问题的并行动态规划算法 |
| |
| 引用本文： | 崔焕庆,王英龙.求解多段图问题的并行动态规划算法[J].计算机应用与软件,2011,28(12). |
| |
| 作者姓名： | 崔焕庆 王英龙 |
| |
| 作者单位： | 1. 山东科技大学信息科学与工程学院 山东青岛266510;山东省计算机网络重点实验室 山东济南250014;山东省计算中心 山东济南250014
2. 山东省计算机网络重点实验室 山东济南250014;山东省计算中心 山东济南250014 |
| |
| 基金项目： | 国家自然科学基金(60773034); 山东省科技攻关项目(2007GG2QT01007); 山东省自然科学基金(ZR2009GQ002,ZR2010FQ014) |
| |
| 摘 要： | 多段图问题是一类特殊的单源最短路径问题。在串行动态规划算法的两种实现方法的基础上,根据图中顶点的编号,提出两种在集群环境下进行任务分割的并行化求解方法,并使用MPI进行实现。实验结果表明,所提出的算法具有较高的加速比和较低的通信复杂度、时间复杂度。算法不限于某种结构的集群,通用性强。
|
| 关 键 词： | 并行算法 多段图问题 最短路径 动态规划 集群 |
PARALLEL DYNAMIC PROGRAMMING ALGORITHM FOR MULTISTAGE GRAPH PROBLEM |
| |
| Cui Huanqing,Wang Yinglong.PARALLEL DYNAMIC PROGRAMMING ALGORITHM FOR MULTISTAGE GRAPH PROBLEM[J].Computer Applications and Software,2011,28(12). |
| |
| Authors: | Cui Huanqing Wang Yinglong |
| |
| Affiliation: | Cui Huanqing1,2,3 Wang Yinglong2,3 1(College of Information Science and Engineering,Shandong University of Science and Technology,Qingdao 266510,Shandong,China) 2(Shandong Provincial Key Laboratory of Computer Network,Jinan 250014,China) 3(Shandong Computer Science Center,China) |
| |
| Abstract: | 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. |
| |
| Keywords: | Parallel algorithm Multistage graph problem Shortest path Dynamic programming Cluster |
| 本文献已被 CNKI 万方数据 等数据库收录！ |
|
