基于质粒模型的DNA计算机算法求解背包问题
2014-05-25陈改霞耿瑞焕
佳木斯职业学院学报 2014年10期
陈改霞 耿瑞焕
(鹤壁汽车工程职业学院 河南鹤壁 458030)
基于质粒模型的DNA计算机算法求解背包问题
陈改霞 耿瑞焕
(鹤壁汽车工程职业学院 河南鹤壁 458030)
本研究在穷举法的背包策略的基础上借鉴二表算法的思路,应用求解最大团问题的思路计算DNA计算机的NP完全计算问题。使用这种算法,能将DNA分子计算的维数从60扩大至120,这种算法的DNA链数可达亚指数的O(1 414n),这种算法拓展了穷举法背包策略的限制,使DNA计算机NP完全问题算法优化。
质粒模型;DNA计算机算法;背包问题
一、质粒模型算法提出的背景
所谓的背包问题,是指一种背包组合的原理。它是在容积一定的前提下,要如何组合才能使包中的价值最大。这个问题研究的核心,是人们要在条件资源已经限制的情况下,计算出收益最大的一种组合方法。背包问题的思想经常应用在优化组合的领域上,而DNA计算的问题就是非常典型的优化组合的问题。
DNA计算问题的实质就是把需要运算的对象当作DNA分子链,然后通过某种算法让这些分子链优化组合,最后形成一个结果,而这个结果必须是可控的过程。这种算法过程非常复杂。要得到满足人们需求的DNA算法。其算法必须满足以下几个要求:要能提出最多的组合方式、该组合方式必须是可控的、组合的结果必须满足人们的需求。本次研究以这些算法的需求为方向,提出一种质粒模型算法,这种算法的DNA链数可达亚指数的O(1 414n),而 即为背包问题的维数,这种算法的试管级水平可达120,使用这种算法是DNA计算机算法中极为优异的一种算法。……
登录APP查看全文
