DNA计算机算法中应用分治背包问题的分析

DNA计算机的研究内容主要是有关怎么减少DNA计算机在进行比较大型采用问题求解的输入，所进行纯指数增长的DNA链数，并且在DNA分子计算中将分治的策略应用于其中。由此来提出一种DNA计算机的新算法用来进行求解背包问题。这种算法是主要由咒位的并行减法器和数据的搜索器还有其他的4个子算法共同组成。

   分子生物学在不断的进行着发展，在一个测试试管中会产生1018个DNA链，这些分析链可以表示和他们数量相等的数据，而且在基本生物学的操作之后能够同时将1018位的信息进行处理，也就是说能将1018位数据进行并行的执行。所以说，生物计算在进行比较大型而且比较难以解决的数据时能够给其提供比较大并行性。早在1994年的时候，就有相关的研究学者比较有开创性的将DNA生化反应进行比较有效利用，并将七个顶点路径问题加以行之有效的解决。在此之后，DNA计算机以及其计算模型和相关的计算方法这些方面研究也是愈加引起世界学者的广泛重视。之后也有学者也对之前的研究方法进行了效仿，并将一个比较经典的多项式复杂程度非确定性问题进行了解决，这个问题就是可满足性的问题。随后在这个学者的相关思想也在实验中利用生物技术得以最大程度上实现。在此之后，也有很多学者就类型不同的图和组合优化问题给出了DNA计算机算法以及实验结果。

一、背包问题

背包问题是属于一种典型的多项式复杂程度的非确定性问题，这个问题无论在信息密码学的相关领域还是在数论的研究中都有着极其重要地位，并获得了比较广泛的应用。对于背包问题，有相关研究学者曾经提出了基于粘贴模型的DNA计算机的算法。在2004年的时候，还有学者提出了一种将编码中的错误控制到最小的DNA计算机算法。

二、分治法的背包问题的DNA计算机算法

   在分治解决背包问题的DNA计算机算法出现并加以使用之前，有一种比较著名的二表法，是当时最为精确的一种计算方法。这种算法能够将那些覆盖背包来的多项式复杂程度非确定性问题以及准备的可满足问题加以解决。正是因为二表法有着这些优势，有人想用DNA分子操作来加以实现。而且依据数据的计算可以发现，这种计算方法可以使DNA算法中纯指数增长的DNA链数得到显著的减少。但是在一系列的计算以及尝试之后我们可以发现，这种计算方法是存在很大程度上的欠缺，这种欠缺体现在不能将排序的问题解决，而且不能实行解搜索的过程。但是任何事物都是有其两面性存在，这种计算方法当然不是毫无优势，二表法在DNA计算机的运算中产生的灵感，也被很多的计算机工作者在DNA分子算法中引入分治策略。在此同时将分治背包的方法进行运用，依据DNA分子操作的相关特性，能够发现这种计算的方法不仅能够减少算法之中的DNA链数，还不会使计算次数增加。

在DNA计算机运算时运用分治背包方法，光是利用二表法是不能将问题进行最好的解决，要将这种方法在实践中进行更好的应用，并使这种办法能够比较切实可行，在类似问题处理上将这种办法进行最大程度上的推广，这样不仅要求计算机专业人员要不断的进行思考，在运用分治背包的时候还要不断改进本身的计算方法，这样这种方法才能在类似问题的处理上发挥最作用。

三、有关结论

前文提到，背包问题是属于比较经典的多项式复杂程度的非确定性问题，一般情况下传统的并行处理技术是无法对机数或者是求解时间成指数增长进行一种比较突破性的处理，而背包公钥系统的安全性也正是建立在这种特性的基础之上。DNA计算机是这种类型问题的潜在的解决方式之中一种。在DNA计算中运用分治策略，本文笔者提出了一种有关背包问题求解的一种相关算法，这种算法能使DNA计算机的背包求解问题中的分子链数大大减少，这样就可以将那些在DNA分子计算基础上的背包问题维数在试管级水平上进行一定程度上的扩大。

到目前为止，在众多研究学者的不断努力下，集合的覆盖问题以及精确的可满足问题甚至是图的定点覆盖的问题都是能够通过亚指数时间图灵计算法得到解决。这样也出现了一个问题，就是以上的问题是不是都存在有亚指数链数以及多项式的操作时间DNA计算机算法呢，因为DNA计算机是与图灵机操作特性完全不同，所以简单的尝试得出的也只是否定结论。现在虽然对DNA计算机的前景还是不能够完全确定，但是这种计算方法是在DNA计算机的比较大型并难以进行解决的问题上是十分重要的，并在有关问题的深入研究中是有着不容小觑的作用存在。

结 语：

计算机的计算中，有关背包的相关问题还是比较多，尤其是在比较常见与计算机的计算工作中。因为那些传统的计算机的处理技术没有办法将处理机数以及求解的时间呈指数增长的趋势进行有效限制，所以说要研究一种行之有效的解决计算机算法，将DNA计算机算法的准确程度进行最大程度上提升。

投稿要求：

1.内容要求：坚持正确的舆论导向，遵循新闻传媒规律。有自己独到的理论见解，或独特的实践做法。

2.摘要：用第三人称写法，不以“本文”、“作者”等作主语，应是一篇能客观反映文章核心观点和创新观点的表意明确、实在的小短文，切忌写成背景交代或“中心思想”，100－200字为宜。

3.正文标题：内容应简洁、明了，层次不宜过多，层次序号为一、（一）、1、（1），层次少时可依次选序号。

4.正文文字：一般以4000字符为宜，正文用小4号宋体，通栏排版，每版平均2000字符。

5．基金项目： 获得国家基金资助和省部级科研项目的文章请注明基金项目名称及编号，按项目证明文字材料标示清楚。

6．作者简介：姓名（出生年- ），性别，民族（汉族可省略），籍贯，现供职单位全称及职称、学位，研究方向。

7. 来稿请注明作者电话、E-mail，收刊人及详细地址、邮编。

8．其他：请勿一稿两发，并请自留原稿，本刊概不退稿。

投稿邮箱：1911365536@qq.com;       2191974423@qq.com（注明投稿刊物名称）

咨询QQ：1911365536;         2191974423

咨询电话：0571-28069909（咨询时间：周一至周六 9:00--17:00）

网址：www.shjbjb.com

欢迎咨询供稿，并诚招各大高校代理约稿人！

注：本杂志社会根据版面安排适当编辑文章内容，作者如不同意论文被修改，请来搞注明。如有基金项目支持，请注明基金项目编号。