利用DNA链的相对浓度求解背包问题 |
| |
引用本文: | 崔建中,殷志祥,杨静.利用DNA链的相对浓度求解背包问题[J].安徽理工大学学报(自然科学版),2018(4). |
| |
作者姓名: | 崔建中 殷志祥 杨静 |
| |
作者单位: | 安徽理工大学电气与信息工程学院;淮南联合大学计算机系;安徽理工大学数学与大数据学院 |
| |
摘 要: | 对于含有n个变量的0-1背包问题,提出了利用DNA链的浓度来判断某种0-1组合是否为可行解的计算模型。该计算模型编码了3n-3种寡聚核苷酸片断,并利用这些编码合成对应于约束条件的、不同浓度的2n-3种DNA链,作为数据池。随后,表示该0-1组合的DNA链被加入到数据池诱发链置换,根据可行解不会产生荧光来并行地搜索所有可行解。最后将可行解对应的目标函数加以比较,最终得到背包问题的最优解。结果表明,该模型的空间复杂度为O(n),时间复杂度为O(1)。模型的优点是计算过程可自动进行,中间结果无需分离,无需人工干预,可靠性高。因此DNA计算求解问题的规模得以大大增加。
|
本文献已被 CNKI 等数据库收录! |
|