基于分治的子集积问题DNA计算机算法

• 作者: 刘完芳 李肯立 潘果
• 来源期刊: 计算机工程与科学
• 学科: 工学
• 关键词: DNA计算 NP完全问题 子集积问题 分治法
• 年，卷（期）: 2007,（8）
• 所属期刊栏目: 算法研究
• 页码范围: 74-78
• 页数: 5页
• 分类号: TP301.6
• 字数: 6519字
• 语种: 中文
• DOI: 10.3969/j.issn.1007-130X.2007.08.023

摘要

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

作者信息

序号	姓名	单位	发文数	被引次数	H指数	G指数
1	李肯立	湖南大学计算机与通信学院	130	931	16.0	22.0
2	刘完芳	湖南公安高等专科学校计算机系	23	76	6.0	7.0
3	潘果	湖南大学计算机与通信学院	9	51	4.0	6.0