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

作者：崔焕庆; 王英龙

来源：计算机应用与软件, 2011, (12): 32-34.

• 并行算法
• 多段图问题
• 最短路径
• 动态规划
• 集群 Parallel algorithm Multistage graph problem Shortest path Dynamic programming Cluster

多段图问题是一类特殊的单源最短路径问题。在串行动态规划算法的两种实现方法的基础上,根据图中顶点的编号,提出两种在集群环境下进行任务分割的并行化求解方法,并使用MPI进行实现。实验结果表明,所提出的算法具有较高的加速比和较低的通信复杂度、时间复杂度。算法不限于某种结构的集群,通用性强。

• 单位
  山东科技大学; 山东省计算中心