基于分治的背包问题DNA计算机算法

李润荣

摘要：随着我国科学技术的不断发展，各式各样的计算机网络可谓层出不穷。与此同时，计算机网络的广泛应用，随之在一定的程度上为人们的生活等多方面，也提供了许多的便利。另外，DNA计算机作为一种新兴的生物形式计算机，则更是起到了不容小觑的作用。对此，其主要是应用于处理较为复杂的大型计算机问题。例如，背包问题等多种NP完全问题。而为了能够更好地提高该计算机算法的可靠性与精准性，基于分治的DNA计算机算法便在一定的程度上，引起了相关工作人员对其的重视。基于此，本文将就此现象做出一定的分析与研究。进而，以期对分治法应用于背包问题的DNA计算机算法，而起到一定合理化的保障作用。

关键词：分治、背包问题、DNA计算机算法

在未运用基于分治的DNA计算机算法解决背包问题时，其所采用的传统计算机算法，普遍具备极为复杂化与繁琐化的特点。因而，也就使得无法真正地起到解决问题的目的。是以，有关工作人员则就此而提出了一種新型的计算机算法，即基于分治的背包问题DNA计算机算法。与此同时，自运用这一计算机算法以来，有关于各类复杂的大型计算机问题的解决效率与准确性等等，则均得到了极大的发展和改善。

一、背包问题与DNA计算机的简要概述

DNA计算机，是一种不同于往常传统计算机的新型生物形式计算机。对此，其主要具有存储容量大、运行快、耗能低、以及体积小等多种优势特点。另外，其主要是通过运用分子生物学的运算形式，而来解决相应复杂的计算机数学问题。对此，由于当前我国DNA计算机算法，仍然处于较为落后的发展阶段。因而，这便使得其存在了一定的欠缺之处。例如，在其进行较大范围的计算机操作的过程中，普遍极易出现实际操作困难、不灵活、以及复制错误率大等多方面的问题现象。与此同时，又由于相关计算机问题中的背包问题，具有较强的典范性与复杂性。因此，现阶段有关于如何科学、合理、以及高效地运用DNA计算机算法来解决背包问题，则可谓是刻不容缓。对此，将分治算法而应用于这一问题之中，则在现阶段较大程度上的取得了多数人的认可。

二、基于分治的背包问题DNA计算机算法的提出背景

处于分子生物技术快速发展的背景下，当前背包问题在信息密码学、以及数论研究等大型难解问题领域中，所具有的应用价值与重要意义随之也得到了一定的提升。是以，为了更为有效地解决背包问题，相关科学研究人员则为此提出了一种新型的DNA计算机算法，即分治DNA计算机算法。对此，其运行模式，即主要分为了并行数据搜索器、以及n位并行减法器这两种子算模式。且除此之外，应用该算法的主要优势特点，即是其能够有效地提高计算机算法应用的并行性与准确性。而与此同时，就我国目前的生物技术而言，运用基于分治的DNA计算机算法，一方面能够更为全面、以及具体地减少编码错误现象的产生。另一方面，则更是在一定的程度上，增添了更多不同的解决途径。因此，虽然该计算机算法在其计算方式、以及存储等方面，与传统计算机算法存在着一定的差异。但毋庸置疑的是，这两者所具有的本质仍然是一致的。

三、基于分治的背包问题DNA计算机算法思想的分析

（一）背包问题DNA 计算机算法思想

在应用分析算法来解决背包问题之前，传统计算机算法最为著名、以及最为精准的一种算法，即是二表法计算机算法。对此，运用该算法最主要的一个原因，即是其能够有效地解决与覆盖相应的计算机NP完全问题。因而，也就是由于其具备这一关键的优势。所以，有关工作人员则据此而提出了一种更为便利、以及高效的DNA分子操作形式的计算机算法。继而，通过实际地应用这一算法，我们可以得知的是其在一定的程度上，极大地降低了DNA链数等因素的影响程度与与范围。但需要注意的是，其必然也存在着一定的不足之处。例如，无法实时的进行相关搜索行为、以及无法解决DNA的排序等等。是以，相关工作人员通过不断对其进行实验与实践，随之也便逐渐地摸索出了将分治算法与DNA分子算法结合运用的新型计算模式。此外，就DNA分子操作特点的角度而言，该计算机算法，一方面能够大幅度地减少计算的次数，另一方面也能够有效地减少原需计算的DNA链数。因此，为了更为充分地扩大其具体的应用范围，相关工作人员则有必要采取一定的措施。进而，确保在有效提高该计算机算法可行性的同时，还能够使其真正地发挥出其具体地应用成效。

（二）基于分治的背包问题DNA计算机算法思想分析

简单来说，分治也就是将一个较为复杂的大型问题，合理地分解为多个类似的小问题。然后，通过采取相应的应对措施，而使其能够实现最终的解决目的。而与此同时，现阶段最为普遍、以及最为有效的背包问题解决方法，即为分治DNA计算机算法。对此，目前分治算法在解决背包问题时，即主要是依据1个搜索器、一个减法器、以及4个子算法而进行具体运算的。且除此之外，分治算法不同于其他传统计算机算法的主要优势有：其一，能够有效地解决实际计算过程中的精准问题；其二，能够及时地发现其具体数据信息的错误之处；其三，能够最大可能性地达到DNA计算机算法的需求标准。另外，从理论上来讲，当前这一算法已将所需计算的背包问题中的DNA链数的维数，成功的从原来的60提高到了120。因而，在当前DNA计算机算法的不断发展过程中，如何运用分治DNA计算机算法，来求解计算大型复杂问题中的纯指数增长的DNA链数，便随之成为了当前研究DNA计算机算法最为关键的一重要内容。

结束语：综上所述，将分治算法应用到DNA计算机中来解决背包问题，是目前较为合理、以及较为高效的一种新型计算机算法。是以，为了使该算法能够更好地发挥其计算优势、以及更为有效地提高DNA计算机算法的准确性。因而，相关工作人员还应在现有的条件基础上，对其积极不断地进行分析、研究与实践。进而，有效确保该DNA计算机算法能够得到更好地发展、以及能够应用到更为广泛的领域。

参考文献：

[1]王喻.分治的背包问题DNA计算机算法分析[J].信息系统工程，2017，（03）：150.

[2]王剑波.基于质粒模型的DNA计算机算法求解背包问题[J].湖南人文科技学院学报，2010，（04）：77-79+96.

[3]郭里.若干图论问题的DNA计算机算法研究[D].导师：李仁发；李肯立.湖南大学，2011.

[4]潘果，李肯立，刘完芳.基于分治的子集积问题DNA计算机算法[J].计算机工程与科学，2011，（08）：74-78.