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

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

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

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 O(2~ 3n/8 ) time when O(2~ 3n/8 ) shared memory units and O(2~ n/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 algorithm 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.