背包问题的一种自适应算法

被引：15

作者：

李肯立

李庆华

戴光明

周炎涛

机构：

[1] 华中科技大学计算机科学与技术学院

[2] 湖南大学计算机科学与通讯学院武汉

[3] 湖南大学计算机科学与通讯学院

[4] 长沙

[5] 武汉

来源：

计算机研究与发展 | 2004年 / 07期

关键词：

背包问题; NP-hard; 自适应算法; 密钥系统;

D O I：

暂无

中图分类号：

TP301 [理论、方法];

学科分类号：

081202 ;

摘要：

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

引用

页码：1292 / 1297

页数：6

共 13 条

[1]

AT =O (2 n/2),S =O (2 n/4)algo rithmforcertainNP completeproblems. RSchroeppel,AShamir. SIAM Journal Computers . 1981

[2]

Linearlyshiftknapsackpublic keycryptosystem. C SLaih,J YLee,LHarn,etal. IEEEJournalSelectedAreasinCommunica tions . 1989

[3]

Aknapsack typepublickeycryptosystembasedonarithmeticinfinitefields. BChor,RLRivest. IEEETransonInformationTheory . 1988

[4]

A polynomial timealgorithmforbreakingthebasicMerkleHellmancryptosystem. AShamir. IEEETransonInformationTheo ry . 1984

[5]

Aparalleltime/hardwaretradeoffT H =O (2 n/2)fortheknapsackproblem. AGFerreira. IEEE Transactions on Computers . 1991

[6]

D S Johnson Computers and Intractability:A guide to the theory of NP completeness. M R Garey. . 1979

[7]

Parallel computation[P]. KALANTERY NASSAR.英国专利:GB2276742B,1997-09-10

[8]

Aparallelalgorithmfortheknapsackproblem. EDKarnin. IEEE Transactions on Computers . 1984

[9]

Aparallelalgorithmfortheknapsackproblemusingagenerationandsearchingtechnique. HK CChang,JJ RChen,S JShyu. Par allelComputing . 1994

[10]

Commentsonparallelalgorithmsfortheknapsackproblem. CAAAanches,NYSoma,HHYanasse. Parallel Computation . 2002

← 1 2 →