计算机应用与软件
計算機應用與軟件
계산궤응용여연건
COMPUTER APPLICATIONS AND SOFTWARE
2011年
12期
32-34
,共3页
并行算法%多段图问题%最短路径%动态规划%集群
併行算法%多段圖問題%最短路徑%動態規劃%集群
병행산법%다단도문제%최단로경%동태규화%집군
多段图问题是一类特殊的单源最短路径问题.在串行动态规划算法的两种实现方法的基础上,根据图中顶点的编号,提出两种在集群环境下进行任务分割的并行化求解方法,并使用MPI进行实现.实验结果表明,所提出的算法具有较高的加速比和较低的通信复杂度、时间复杂度.算法不限于某种结构的集群,通用性强.
多段圖問題是一類特殊的單源最短路徑問題.在串行動態規劃算法的兩種實現方法的基礎上,根據圖中頂點的編號,提齣兩種在集群環境下進行任務分割的併行化求解方法,併使用MPI進行實現.實驗結果錶明,所提齣的算法具有較高的加速比和較低的通信複雜度、時間複雜度.算法不限于某種結構的集群,通用性彊.
다단도문제시일류특수적단원최단로경문제.재천행동태규화산법적량충실현방법적기출상,근거도중정점적편호,제출량충재집군배경하진행임무분할적병행화구해방법,병사용MPI진행실현.실험결과표명,소제출적산법구유교고적가속비화교저적통신복잡도、시간복잡도.산법불한우모충결구적집군,통용성강.
