APP下载

基于质粒模型的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查看全文

猜你喜欢

思路计算机模型
一半模型
计算机操作系统
不同思路解答
重尾非线性自回归模型自加权M-估计的渐近分布
基于计算机自然语言处理的机器翻译技术应用与简介
拓展思路 一词多造
信息系统审计中计算机审计的应用
换个思路巧填数
3D打印中的模型分割与打包
Fresnel衍射的计算机模拟演示