背包问题无存储冲突的并行三表算法

• 作者: 李仁发 李庆华 李肯立
• 来源期刊: 计算机学报
• 学科: 工学
• 关键词: 背包问题 NP难问题 并行算法 存储冲突 硬件-时间折衷
• 年，卷（期）: 2006,（2）
• 所属期刊栏目: 短文
• 页码范围: 345-352
• 页数: 8页
• 分类号: TP301
• 字数: 8088字
• 语种: 中文
• DOI: 10.3321/j.issn:0254-4164.2006.02.021

摘要

背包问题属于经典的NP难问题,在信息密码学和数论等研究中具有极重要的应用.将求解背包问题著名的二表算法的设计思想应用于三表搜索中,利用分治策略和无存储冲突的最优归并算法,提出一种基于EREW-SIMD共享存储模型的并行三表算法.算法使用O(2 n/4)个处理机单元和O(23n/8)的共享存储空间,在O(22n/8)时间内求解n维背包问题.将提出的算法与已有文献结论进行的对比分析表明:文中算法明显改进了现有文献的研究结果,是一种可在小于O(2n/2)的硬件资源上,以小于O(2n/2)的计算时间求解背包问题的无存储冲突并行算法.

作者信息

序号	姓名	单位	发文数	被引次数	H指数	G指数
1	李仁发	湖南大学计算机与通信学院	468	4582	30.0	44.0
2	李庆华	华中科技大学计算机学院国家高性能计算中心	113	1366	21.0	30.0