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