基于采样和MIMD结构的背包问题并行算法

• 作者: 刘晓玲 李肯立 郑光勇
• 来源期刊: 计算机工程与科学
• 学科: 工学
• 关键词: 背包问题 并行算法 采样 MIMD 二表算法
• 年，卷（期）: 2006,（9）
• 所属期刊栏目: 算法研究
• 页码范围: 100-102
• 页数: 3页
• 分类号: TP301.6
• 字数: 2500字
• 语种: 中文
• DOI: 10.3969/j.issn.1007-130X.2006.09.033

摘要

背包问题属于著名的NP完全问题,在信息密码学和数论研究中有着极其重要的应用.在深入分析背包问题现有并行算法的基础上,本文提出了一种基于采样和MIMD结构的背包问题并行求解算法,并给出了算法性能的理论分析和在IBM P690超级计算机上的实验结果.实验结果表明,当背包实例的维数n≥40时,本算法的并行效率可达60%以上.因此,本并行算法具有较好的可扩展性,能应用于各种MIMD结构的并行机上有效地求解背包问题.

作者信息

序号	姓名	单位	发文数	被引次数	H指数	G指数
1	李肯立	湖南大学计算机与通信学院	130	931	16.0	22.0
2	刘晓玲	湖南大学计算机与通信学院	44	895	11.0	29.0
3	郑光勇	湖南大学计算机与通信学院	5	16	3.0	3.0