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

A Parallel Three-List Algorithm for the Knapsack Problem without Memory Conflicts

作　　者：李肯立[1] 李仁发[1] 李庆华[2] 

机构地区：[1]湖南大学计算机与通信学院 [2]华中科技大学计算机学院国家高性能计算中心,武汉430074

出　　处：《计算机学报》2006年第2期345-352,共8页Chinese Journal of Computers

基　　金：国家自然科学基金(60273075);国家"八六三"高技术研究发展计划项目基金(863-306ZD-11-01-06);教育部重点项目基金(105128)资助

摘　　要：背包问题属于经典的NP难问题,在信息密码学和数论等研究中具有极重要的应用.将求解背包问题著名的二表算法的设计思想应用于三表搜索中,利用分治策略和无存储冲突的最优归并算法,提出一种基于EREW-SI MD共享存储模型的并行三表算法.算法使用O(2n/4)个处理机单元和O(23n/8)的共享存储空间,在O(23n/8)时间内求解n维背包问题.将提出的算法与已有文献结论进行的对比分析表明:文中算法明显改进了现有文献的研究结果,是一种可在小于O(2n/2)的硬件资源上,以小于O(2n/2)的计算时间求解背包问题的无存储冲突并行算法.The knapsack problem is a famous NP-Hard problem, the solution for which usually requires not only exponential time, but also exponential space. It is for this cause that it is very important in cryptosystem and number theory. Based on the two-list algorithm and the parallel three-list algorithm, this paper proposes a new parallel three-list algorithm for the solution of knapsack problem. To avoid the possible memory conflicts, the method of divide and conquer, and parallel merging without memory conflicts are adopted in the new algorithm. The proposed algorithm needs 0（2＇~＂/~） time when O（2a＇/8） shared memory units and O（2~/4） processors are available for the objectivity to find a solution for a n-element knapsack instance. The comparison of the proposed algorithm with the past researches show that it is the first EREW parallel algo rithm that can solve the knapsack instances in less than O（2^n/2 ） time when available hardware resource is also less than O（2^n/2）, and thus it is an improved result over the past researches, and may have some impact on the researches on the knapsack based public-key cryptosystem.

关 键 词：背包问题 NP难问题 并行算法 存储冲突 硬件-时间折衷 

分 类 号：TP301[自动化与计算机技术—计算机系统结构]