浅析分治基于分治背包理由DNA计算机算法

论文导读：时，还发现一个重要的问题就是运用这种方法并不一定可以解决亚指数链数和多项式操作时间的DNA计算机算法。由于DNA计算机的操作方式完全不同于图灵机的操作特性，对于分治背包算法的简单尝试和实验只能得不出满意的结果。对12下一页
摘 要：DNA计算机研究的重要内容是关于如何减少DNA计算机在求解大型难解问题中以问题输入纯指数增长的DNA链数。本文将分治策略应用于背包问题的DNA分子计算中，提出了一种新的DNA计算机求解背包问题的算法。背包问题的算法由咒位并行减法器、咒位数据搜索器和其他的4个子算法组成。
关键词：背包问题；DNA计算；计算机
1007-9599 （2013） 04-0000-02
1 引言
背包问题可描述如下：给定q个正整数的集合W=（w1，w2，……，wn）和正整数M，要求决定二值q元组X=（x1，x2，……，xq）的值，使得式：被满足。文献[5]设计了基于粘贴模型的n位并行DNA比较器和n位并行加法器来求解背包问题。该算法证明可通过DNA计算来完成复杂的数学运算，而且极大提高了运算的并行度[5]。背包问题属于经典的NP完全问题。信息学和数论研究中都经常具有NP问题。Perez-Jimenez等人针对背包问题提出了基于粘贴模型的DNA计算机算法。在2004年的时候，Chang等人针对背包问题设计一种编码错误更少的DNA计算机算法。但是上述DNA计算机算法都属于简单的穷举算法。并不能真正有效的解决背包问题。由于本分需要分析的就是关于分治的背包问题DNA计算机算法，因此建这种方法代入到背包问题DNA计算机算法设计中，运用一种全新的背包问题DNA计算机算法。经过运算发现代入分治背包方法可以有效的对这类问题进行运算，并提高运算的准确率。
2 分治法的背包问题的DNA计算机算法

2.1 DNA计算机算法思想

在出现和使用分治解决背包问题的BNA计算机算法之前，Horowitz和Sahni提出的著名二表法是最精确的计算方法。这种算法可以求解出准备的SAT和最大图案的问题以及覆盖背包来的NP完全问题。也正是因为二表法拥有这些优点，所有有人设想将二表算法用DNA分子操作来实现，根据计算可以发现，这种算法可以显著的减少DNA算法之中的数目呈纯之术增长的DNA链数。但是经过一系列的尝试计算之后发现，运用二表法有着相当大的欠缺，那就是那无法解决排序并且不能实行解搜索过程。但是同时也是发现了，二表法并不是一无是处，通过二表法对DNA计算机的运算产生的灵感，有些计算机工作者还是在DNA分子算法之中设计引入分治策略。并且运用分治背包的方法，从而根DNA分子操作的特性，发现这种计算方法既能够减少算法之中的DNA链数，又不会增加计算的次数。
当然运用分治背包的方法进行DNA计算机的运算，不仅仅需要解决二表法所不能解决的问题，还要能使这种方法在实际应用中，确实可行，能真正使得这种分治方法在关于类似问题的处理的时候得到充分的推广，这不仅需要计算机专业人员的不断思考，还需要在运用分治背包的时候能不断改进自己的运算方法，使得这种方法能真正的在计算机处理此类问题的时候发挥到他的作用。
3 模拟实验结果
为了确保验证分治算法的有效性，这里特以M={1，2}，W=3作为待求解的背包实例。只有经过实验检验，确定了这种方法的有效性，才能应用到实际的运算中。在模拟实验的过程中，充分了解分治背包这种方法的特点及运算模式。

3.1 对DNA进行编码

采用适合模拟条件的DNA计算模型，根据正确的编码规则。在Windows2007操作系统下进行DNA的编码工作。

3.2 算法求解过程

4 结论
在计算机的计算中，关于背包的问题有非常多，特别是常见于计算机的计算中，由于传统的计算机处理技术无法突理机数或求解时间呈指数增长的限制，因此需要发展新的处理方法，而分治背包的处理方法将分治策略应用于DNA分子计算中，可以有效的解决DNA计算机算法。通过对分治背包的理解提出的一种求解背包问题的DNA计算机算法可以将基于DNA分子计算求解背包问题的维数在试管级水平上从60扩大到120[3]。从而大大提高DNA计算机算法的准确率。
就目前关于分治的背包问题DNA计算机算法，经过大量计算机学者的努力，就计算机中关于亚指数时间的图灵机算法已经得到完美的解决。在解决这个问题的同时，还发现一个重要的问题就是运用这种方法并不一定可以解决亚指数链数和多项式操作时间的DNA计算机算法。由于DNA计算机的操作方式完全不同于图灵机的操作特性，对于分治背包算法的简单尝试和实验只能得不出满意的结果。对论文导读：上一页12
于DNA计算机的前景，虽然还不能有准确的预测，但是从文中运用分治背包的算法解决DNA计算机存在的问题可以看出这种方法还是十分有效的。对于这种方法的进一步发展，需要后面人的继续努力。
参考文献：
李肯立，姚凤娟，李仁发，等.基于分治的背包问题DNA计算机算法[J].计算机研究与发展，2007（05）：11-19.
车玮.DNA计算机中队列数据结构的设计及实现[J].科协论坛，2011（08）：66-70.
[3]朱雅莉，李浪，邹超君.DNA计算机的研究现状[J].电子设计工程，2011（04）：33-39.
[4]周旭，李肯立，乐光学，等.一种最大匹配问题DNA计算算法[J].计算机研究与发展，2011（01）：114-118.
[5]LIPTONRJ摘自：本科毕业论文范文www.7ctime.com
.DNAsolutionofhardcomputationalproblems[J].Science，1995，268（28）：542-545.
[作者简介]王旖旎（1981-），女，汉族，重庆市人，工学硕士，重庆商务职业学院电子商务系，讲师，研究方向：软件技术、计算机网络技术、计算机应用技术。