中国科技论文在线

上传时间

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日

【期刊论文】A GENETIC ALGORITHM FOR THE UNBOUNDED KNAPSACK PROBLEM

李肯立， KEN-LI LI， GUANG-MING DAI， QING-HUA LI

，-0001，（）：

-1年11月30日

摘要

In this paper a new evolutionary algorithm is presented for the unbounded knapsack problem, which is a famous NP complete Combinatorialoptimizationproblem. The proposed genetic algorithm is based on two techniques. One is a heuristic operator, which utilizes problem-speciflc knowledge, and the other is a preprocessing technique.Computational results show that the proposed algorithm is capable of obtaining highquality solutions for problems of standard randomly generated knapsack instances, while requiring only a modest amount of computational effort.

Genetic Algorithm， Unbounded Knapsack Problem， Combinatorial Optimization

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

引用

上传时间

2009年12月22日

【期刊论文】基于分治的背包问题DNA计算机算法

李肯立，，姚凤娟，李仁发，许进

计算机研究与发展，2007，44（6）：1063～1070，-0001，（）：

-1年11月30日

摘要

如何减少DNA计算机在求解大型难解问题中以问题输入纯指数增长的DNA链数，已成为DNA计算机研究的重要内容，将分治策略应用于背包问题的DNA分子计算中，提出一种求解背包问题的新的DNA计算机算法，算法由咒位并行减法器、咒位数据搜索器和其他4个子算法组成，算法的DNA链数可达到亚指数的O（2q/2），其中q为背包问题的维数．与最近文献结论进行的对比分析表明：算法将求解背包问题所需的DNA链数从O（2q）减少至O（2q/2），最大鲢长度减少为原来的1/2，因此，理论上新算法在试管级水平上能将可破解的背包公钥的维数从60提高到120，

DNA计算， NP完全问题，背包问题，分治法

62浏览
0点赞
0收藏
0分享
101下载
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

引用

上传时间

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

引用