中国科技论文在线

上传时间

2009年12月22日

【期刊论文】Optimal Parallel Algorithm for the Knapsack Problem Without Memory Conflicts

李肯立， Ken-Li Li.， Ren-Fa Li， and Qing-Hua Li

J.Comput.Sci.&Technol.2004,19(6)，-0001，（）：

-1年11月30日

The knapsack problem is well known to be NP-complete. Due to its importance in cryptosystem and in number theory, in the past two decades, much effort has been made in order to find techniques that could lead to practical algorithms with reasonable running time. This paper proposes a new parallel algorithm for the knapsack problem where the optimal merging algorithm is adopted. The proposed algorithm is based on an EREW-SIMD machine with shared memory. It is proved that the proposed algorithm is both optimal and the first without memory conflicts algorithm for the knapsack problem. The comparisons of algorithm performance show that it is an improvement over the past researches.

knapsack problem,， NP-complete,， parallel algorithm,， optimal algorithm,， memory conflict

43浏览
0点赞
0收藏
0分享
54下载
0

引用

上传时间

2009年12月22日

【期刊论文】背包类问题的并行O(25n/6)时间-空间-处理机折衷∗

李肯立，李肯立+，赵欢，李仁发，李庆华

JournalofSoftware，2007，18（6）：1319～1327，-0001，（）：

-1年11月30日

摘要

将串行动态二表算法应用于并行三表算法的设计中,提出一种求解背包、精确的可满足性和集覆盖等背包类NP完全问题的并行三表六子表算法。基于EREW-PRAM模型,该算法可使用O（2n/8）的处理机在O（27n/16）的时间和O（213n/48）的空间求解n维背包类问题,其时间-空间-处理机折衷为O（25n/6）。与现有文献的性能对比分析表明,该算法极大地提高了并行求解背包类问题的时间-空间-处理机折衷性能。由于该算法能够破解更高维数的背包类公钥和数字水印系统,其结论在密钥分析领域具有一定的理论和实际意义。

NP完全问题，并行算法，时间-空间-处理机折衷，背包问题

37浏览
0点赞
0收藏
0分享
89下载
0

引用

上传时间

2009年12月22日

【期刊论文】背包问题的最优并行算法∗

李肯立，李庆华+，蒋盛益，张薇

软件学报，2003，14（5）：891～896，-0001，（）：

-1年11月30日

摘要

利用分治策略,提出一种基于SIMD共享存储计算机模型的并行背包问题求解算法。算法允许使用O（2n/4）1−ε个并行处理机单元,0≤≤ε1,O（2n/2）个存储单元,在O（2n/4（2n/4）ε）时间内求解n维背包问题,算法的成本为O（2n/2）。将提出的算法与已有文献结论进行对比表明,该算法改进了已有文献的相应结果,是求解背包问题的成本最优并行算法。同时还指出了相关文献主要结论的错误。

背包问题， NP完全，并行算法，分治法

61浏览
0点赞
0收藏
0分享
231下载
0

引用

上传时间

2009年12月22日

【期刊论文】背包问题的一种自适应算法

李肯立，李肯立'，李庆华，戴光明，周炎涛

计算机研究与发展，2004，41（7）：1292～1297，-0001，（）：

-1年11月30日

摘要

背包问题是经典的NP- hard组合优化问题之一，由于其难解性，该问题在信息密码学和数论研究中具有极重要的应用，基于求解背包问题著名的二表算法和动态二表算法，利用归并原理和4个非平衡的子表，提出一种求解该问题的自适应算法，算法可根据计算资源和问题实例规模的大小，允许使用O（2N/2-ε）的存储空间（1≤ε≤n/4），在O（ε（2n/2））的时间内求解背包问题，对算法性能的理论分析和数值实验结果表明，自适应算法可显著扩大背包实例的求解规模，从时间和空间上改进背包问题现有算法的性能．

背包问题， NP-hard，目适应算法，密钥系统

59浏览
0点赞
0收藏
0分享
73下载
0

引用

上传时间

2009年12月22日

【期刊论文】背包问题无存储冲突的并行三表算法

李肯立，李肯），），李仁发），李庆华）

计算机学报，2006，29(2)：345～352，-0001，（）：

-1年11月30日

摘要

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

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

38浏览
0点赞
0收藏
0分享
100下载
0

引用