文献类型：期刊文章

作　　者：李肯立[1] 姚凤娟[1] 李仁发[1] 许进[2]

机构地区：[1]湖南大学计算机与通信学院,长沙410082 [2]华中科技大学分子生物计算机研究所,武汉430074

出　　处：《计算机研究与发展》

基　　金：国家自然科学基金项目(60603053;60274026;60373089;60403002);教育部科学技术研究重点基金项目(05128)~~

年　　份：2007

卷　　号：44

期　　号：6

起止页码：1063-1070

语　　种：中文

收录情况：AJ、BDHX、BDHX2004、CSA-PROQEUST、CSCD、CSCD2011_2012、EI、IC、JST、RCCSE、SCOPUS、ZGKJHX、核心刊

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

关 键 词：DNA计算 NP完全问题 背包问题 分治法

分 类 号：TP301.6]