基于质粒模型的DNA计算机算法求解背包问题

陈改霞 耿瑞焕

(鹤壁汽车工程职业学院 河南鹤壁 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计算机算法中极为优异的一种算法。

二、质粒模型算法应用的优势

计算机求解NP的完全问题一直是人们认为难解的问题，如果没有一个合理的算法，它的计算长度、计算时间、计算过程都难以控制。于是人们提出把这种计算问题映射成DNA算法的问题，，利用DNA 链的思路进行计算。然而应用DNA算法的思路求解也存在一些难题。

控制性的难题——DNA计算机求解NP的过程，是一种组合优化的问题，这种问题适合用计算机模型来解决。随着科学技术的发展，计算机的计算模型也飞速的进步，然而就DNA计算机求解NP的问题而言，它依然存在很多问题。其中最大的问题为控制性的问题。目前DNA计算中应用到杂交、退火、探针的算法，都有可能出现计算的不稳定性，然后出现伪解。为了解决这个问题，必须要使计算机模型的算法本身具有稳定性。目前质粒的DNA计算机模型是成功的解决了最大权团的算法问题，它在计算的过程中不易受到其它醇的干扰。虽然这种算法本身还有一定的难度，可是其稳定性与准确性均能得到保证，这就是计算的控制性能得到保证。

拓展性的难题——DNA计算机算法的原理，是人们提出的以DNA计算模型为基础的解3色的问题，以这种方式解决给合优化的问题。然而最初这种原理只能解O(1 67n) 的链数，且这种算法的伪解较多，可拓展性较差，它难以被广泛的实践应用。目前人们也提出了其它的DNA计算机算法，然而绝大多数的计算方法对时间和长度要求很高，其拓展性也比较差。基于质粒模型的算法是以背包问题为前提进行计算，它的时间与长度都被严格控制，所以它的可拓展性也能得到保证。

准确性的难题——为了优化NDA计算机的算法，曾经有人提出求解最大团的算法，这种思路能够控制计算的时间，它是DNA计算机算法的一种新突破。然而如何能确保在一定的时间内控制最大团的最高计算概率，是人们对这种算法的又一种要求。该次提出的质粒模型算法应用了背包问题的思路解决了在时间和空间被限制的前提下，提高准确率的难题。

由于以上质粒模型算法的优势，它能在操作次数不变的前提下，控制最全部的计算过程，得到极高的亚折数，这种算法在NDA计算机算法中非常具有优势。

三、质粒模型算法的基本流程

如果要用背包问题的理论控制质粒模型的计算，就要给定以下的数值：

正整数q的集合W=(W1,,W2,W3……,Wn)；

正整数M的数值；

以上两者的数值决定q元组x的数值，而q可描述为：(x1,x2,x3,……,xq) 。

这种算法能够以背包问题的思路来解决质粒算法的时间与长度控制的问题，它能提高这类问题的并行度。这种算法的核心是使用穷举法的算法，然而它的背包数量被限制为60，为了突破背包数量的限制，该次算法借鉴了二表算法，即应用求解最大团问题的思路计算DNA计算机的NP完全计算问题。

这种计算思路为将正整数q的集合W=(W1,,W2,W3……,Wn)拆分为 和 两个背包，然后求出两个部分的子集和，而子集合的背包容量为O(1 414n)，使用这种二表算法中二表求和的思路以后，再与M进行比较，判可否有解转换成先求M与一个子集所有子集和的差；之后以同样的方法再用另一个部分的子集进行有解决断。这种计算方法既能突破背包的限制，又能使DNA计算的方法更规范化。在这种计算方法中，由于要将背包数限制为1.14n这个链数，所以计算操作时间与长度都能得到控制。

这种计算方法的控制，主要从三个方面进行控制：编译的问题，即在做编译阶段时，要将求解的问题映射到DNA链上；以质粒模型的思路求解，而求解的长度控制、时间控制则由以背包思路控制；使用二表算法优化背包思路的算法。该过程为全部的算法思路。这种算法可描述如下：

赋予数值环节——

步骤1：将集合W=(W1,,W2,W3……,Wn)按升序排列，并将其分成两个元素个数相等的子集W1和W2。W1取按升序排列好后的W中的前n/2个元素，而W2取按升序排列好后的W的后n/2。以W1,i表示W1中的第i个元素，W2,i表示W2的第i个元素；

输入数值环节——

步骤2：将实验杯T0中，给W1,i、W1,i-W1,i、M分量的值进行编码；

步骤3：把T0产生的DNA片段插入到开口的质粒中，当形成一个闭环质粒以后，将该质粒放入到大肠杆菌中扩增；

步骤4：将W1和W2视为背包，将之初始化，把T0产生的质粒放入等量的杯子里。杯子可描述为T1和T2。

计算数值环节——

步骤5：W1子集数值生成，计算M与W1里所有子集和的差；

步骤6：W2子集数值生成，计算W2里所有子集之合；

输出数值环节——

步骤7：找出链长相等的质粒，该计算可用凝胶电泳技术实现；

步骤8：步骤7中所有的质粒所含的背包分量的并即即为所得结果；

步骤9：输出数值结果，完成计算流程。

四、总结

DNA计算机NP完全问题数值计算的问题直至现在都被认为是难解的数学难题。目前人们使用穷举法解决这个问题，然后用背包思路限制穷举法数值计算的时间和长度，然而穷举法的背包数量不能满足人们的需求，它无法计算变量数集多的NP完全问题。本次在穷举法的背包策略的基础上借鉴二表算法的思路，应用求解最大团问题的思路计算DNA计算机的NP完全计算问题。使用这种算法，能将DNA分子计算的维数从60扩大至120，，这种算法的DNA链数可达亚指数的O(1 414n)，这种算法拓展了穷举法背包策略的限制，使DNA计算机NP完全问题算法优化。

[1]唐悦.动态规划的新形式0/1背包问题的两种解法[J].网络科技时代(数字冲浪),2002(03).

[2]杨晓燕.温振华.一种求解背包问题的改进离散粒子群优化算法[J].梧州学院学报,2010(03).

[3]王志刚.谭沈阳.求解0-1背包问题的粒子群优化算法[J].廊坊师范学院学报(自然科学版),2010(05).

Solving knapsack problem based on plasmid Model DNA computer algorithm

Chen Gai-xia, Geng Rui-huan
(Hebi Automobile Engineering Vocational College, Hebi Henan, 458030, China)

Draw lessons from the thinking of two table algorithm, this study applied thinking in solving the largest group of DNA computer npcomplete calculation problem. Using this algorithm, the dimensions of the DNA molecular computation can be expanded from 60 to 120, the number of DNA strands of this algorithm can reach the index , expand the exhaustive method backpack strategy, make the algorithm to optimize DNA computer NP complete problem.

plasmid model; DNA computer algorithms; knapsack problem

TP301.6

A

1000-9795（2014）010-000159-02

［责任编辑： 刘 乾］

陈改霞（1980-），女，汉族，河南周口人，硕士，鹤壁汽车工程职业学院讲师，研究方向：计算机应用和计算机网络。

耿瑞焕（1986-），女，汉族，河南濮阳人，硕士，鹤壁汽车工程职业学院助教，研究方向：模式识别、人工智能。