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

曾毅

摘要：在DNA计算机研究领域，将降低DNA计算机在大型难解问题求解中问题输入纯指数增长的DNA链数问题作为研究重要内容，于背包问题的DNA分子计算中引入分治策略，提出一种进行背包问题求解的DNA计算机算。重点对其算法组成及应用进行分析。通过模拟实验发现，新算法其能够提高破解背包公钥维数，解决背包问题所需DNA链数增长问题，切实提高DNA计算机算法操作的准确性。

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

中图分类号：TP311 文献标识码：A 文章编号：1009-3044（2015）05-0213-03

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

伴随着分子生物技术发展，单个测试试管可产生1018个DNA链，1018个DNA分子链用数学方式表示即代表1018位数据。当前，基本生物学支持同时进行1018位数据处理。在大型难解问题领域，生物计算其能够提供并行性。早在1994年，Adleman在DNA分子生物反应的基础上进行了有向Hamilton路径问题解决。在此之后，DNA计算机及DNA计算模型等研究获得高度重视，Lipton通过DNA生物技术实现了NP完全问题的可满足性问题解决。

NP完全问题中的背包问题其具体描述为：设定q个正整数集合W与正整数M并要求决定W、M二值的q元祖X参数能够满足公式[i=1qwixi=M]要求。背包问题在数论研究与信息密码学研究领域存在着重要作用及应用价值。为解决背包问题，有学者提出构建粘贴模型DNA计算机算法，2004年，Chang等学者提出一种DNA计算机算法，其算法优势在于编码错误较少。

然而以上算法多属于简单穷举算法类型，如设定其方法解决背包密钥维数为q，则其算法在解决背包问题时所面临的DNA链数量则为O（2q）。以当前的生物技术水平而言，其在处理DNA浓度问题上仅为微摩尔量级，采取以上DNA计算机算法在理论上能够进行背包密钥破解的维数只为60。依据最新DNA算法，其能够实现背包密钥破解维度结果为80。李源等在研究此问题时在DNA计算中引入了进步算法，提出DNA计算机概率算法，这种算法方式其在降低DNA分子数目上存在一定效果。

虽然DNA计算机算法与传统计算机计算其在存储及计算方式上存在差异，但从本质上而言，DNA算法其属于一种并行超级算法。在本文研究背包问题DNA计算机算法过程中，引入分治策略，提出一种新型的建立于分治策略基础之上的背包问题DNA计算机算法。这种算法具体包括n位并行减法器与并行数据搜索器两种关键子算。模拟计算结果表明，这种算法在进行背包问题DNA链数维数求解时达到了O（2q/2）。

2 Adleman-Lipton模型认知

1995年，在Adleman研究的基础上，Lipton在解决可满足性问题的过程中提出了一种NDA计算模型即Adleman-Lipton模型。在Adleman-Lipton模型条件下，一个试管可以视为由有限字母构成的字母表{A ， C ， T， G }相互组合形成的串集合，具体DNA操作可以通过如下进行描述：

第一，抽取。设定具体试管P与短DNA单链S，具体抽取操作为：+（P，S）、-（P，S）。其中+（P，S）代表P试管中含有S的所有集合作为子链的DNA分子链，-（P，S）则代表P试管中不存在S作为子链的DNA分子链。第二，合并。将试管设定为P1，P2，采取合并操作，具体公式表达为U（P1，P2） =P1UP2 ，其合并操作的具体含义为将P1及P2试管合并到同一根试管环境之中却不改变其各个试管之中的任何DNA分子链。第三，检测，设定试管为P，检测设定条件如试管中至少存在1个DNA链，在检测条件基础上运行，满足条件则返回“yes”，不满足条件则执行“no”。第四，复制，设定试管为P，通过操作之后产生P的复制结果，即P1、P2，在复制之后P试管不存在任何分子链，为空。第五，添加。设定试管P，明确短DNA链为Z，通过添加操作方法在P试管中每个链的末尾位置增加链Z。第六，读取。设定试管为P，通过读取操作，能够获取试管P中任何一个NDA分子链信息。

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

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

Horowitz与Sahni在NP完全问题算法研究过程中，引入了分治策略并提出了二表算法，这种算法在进行SAT精确求解、最大团问题及集覆盖问题求解等背包类NP完全问题解决中应用十分广泛。通过NDA分子方式进行二表算法应用发现，采取二表算法无法解决DNA算法中数目呈纯指数增加的链数问题，这是因为二表算法中的排序问题及解搜索无法实现并行操作。在二表算法设计理念的基础上，在DNA算法中引入分治策略，依据DNA分子操作特性进行背包问题解决。这种新型算法的核心思想为：通过分治策略方式将所有背包分量进行部分划分，将分量w1 ， w2 ，…wn划分为两部分，对划分后部分所有的O（2q/2）子集进行求和，设定背包容量为M，通过应用减法方式将M与其中一个子集所包含的所有子集和进行减法运算，这种算法要求先获取M，然后求解出一个子集中所包含的所有子集和，并计算两者之间的差值，将其差值与另一部分子集和进行对比，判断是否有解。采取这种计算方式不仅解决了二表算法中存在的排序及解搜索DNA操作串行局限问题，还能够有效降低NDA操作的实际难度，这种算法方式其DNA链只需保存2q/2个，并非2q/所有子集和。基于分治的背包问题DNA计算机算法实现过程描述如下：

明确需要求解的背包问题DNA计算机算法框架，其算法实现步骤为：第一，通过DNA链进行背包分量集合W1、W2的所有子集在试管T01与T02中表示，其中W1={w1，w2，…wq/2}，W2={wq/2+1，wq/2+2，…wq}；第二，在试管T01与T02中通过DNA链进行背包分量集合W1、W2所有子集对应元素表示，TM代表M的DNA分子链形式；第三，对试管中DNA链相对应子集执行DNA并行加法器运算并获得背包分量所有子集的子集和；第四，通过并行减法器对T01试管减法操作，获得M与T01试管中各子集和之差的DNA链；第五，通过执行n位并行数据搜索器运行，对试管T01与T02中进行比对，找出试管T01差与T02中和参数相同的DNA链，其结果即背包问题解。

（2）DNA计算机子算法中的n位并行减法器

在DNA计算机算法应用中，如TM试管中其DNA链通过M来表示，如其M的第j位数值属于1，则采取[y1q2×n+j]进行标记，其中j值大于0小于n+1，如其第j位树值不为1，则通过[y0q2×n+j]进行标记。试管T01中[yq/2×n+j]代表子集和第j位，以lj表示T01试管运行减法所获得的借位，l1属于借位初始参数，其参数值为0。通过减法运算所获得的差值第j位则通过uj进行表示。n位并行减法器实现描述如下图所示：

图1 基于分治的背包问题DNA计算机算法n位并行减法器运行程序

通过这种算法能够求解出M与T01试管中各DNA链子集和差值。

（3）DNA计算机子算法中的n位并行数据搜索器

完成并行减法计算后，T01试管NDA链对M及各背包分量w1，w2，…wq/2所产生子集的子集和差值进行描述，而背包分量wq/2+1，wq/2+2，…wq所产生子集和参数则保存在T02试管中。要求对其背包分量子集和参数进行对比。如T01试管之中所存在的某个或某些DNA链差值信息与T02试管中存在的DNA链和值参数信息一致，则说明此背包问题有解，如不存在相同参数信息，则说明此背包问题无解。为判断背包问题是否有解，需要读其差值信息及子集和信息进行对比，在本算法中为避免出现穷举对比问题，将比较划分为两个步骤来实现，即前五位与后n-5位比较方法。针对n-5位信息对比，要求在完成n-5位差信息最大值求解后查找是否存在后与之相同信息，如有则对前5位数据采取分离操作或穷举，循环求解。通过并行数据搜索器，能够对T01试管中差值与T02试管子集和值是否存在相等进行搜索对比。通过算法对比可以实现信息前5位是否存在相等DNA链进行分析，如存在相等链则说明背包问题有解，通过算法循环搜索出背包问题最终解。采取这种方式，其能够在相对短的时间内实现T01试管中差值与T02试管子集和值相等状况搜索，其链长不变。

4 基于分治的背包问题DNA计算机算法模拟实验分析

为验证基于分治的背包问题DNA计算机算法应用有效性，选择待求解背包实例进行模拟实验。设定W={1，2}，M=3，采取分治背包问题DNA计算机算法进行求解过程模拟：

（1）DNA编码操作

选择应用Braich变量SAT问题解决中所采取的DNA计算模型对背包中的每一个变量进行长度设计，具体设计为长度均为15的碱基并作为“值序列”。综合考虑BraichDNA计算模型之中的编码规则，在Windows XP环境下选择Visual C++6.0编码器进行DNA序列产生。试管T01与T02中产生的DNA序列具体如表1所示：

（2）算法求解过程分析

将背包集合划分为W1、W2，应用试管进行T01与T02集合表示。集合W1={1}中子集[Φ]所对应DNA分子链具体表示为[x01s01，1s01，2]，{1}所对应DNA分子链则为[x11s11，1s01，2]，同理，集合W2={2}中子集[Φ]所对应DNA分子链具体表示为[x01s01，1s01，2]，{2}所对应的DNA分子链为[x11s01，1s11，2]。[xi]代表的是子集标号，通过子集标号进行集合标示，对第i个元素是否在该子集中出现进行描述。Si，j代表子集集中元素标号，该标号作为第i个元素进行二进制转换后所获得的第j位值，通过DNA并行加法器执行并行加法运算。集合w1={1}其子集对应DNA分子链为[x01s01，1s01，2y01y02z01y03z02y04z03]表示和为0，{1}对应DNA分子链为[x11s11，1s01，2y01y02z01y13z02y04z03]表示和值为1，同理，也可以获取集合w2={2}子集所对应的DNA分子链和值为0，{2}所对应的DNA分子链和值为2。应用DNA计算机算法能够获取M与试管T01各子集之间差值，获得对应DNA分子链，求解出差值信息与试管T02中某些DNA链和值的信息，其结果即背包问题的解。计算结果显示试管T01子集{1}的DNA分子链与试管T02子集{2}的DNA分子链，两条链并集部分即背包问题的解。

5 结语

研究背包问题其在数论研究与信息密码学研究领域存在着极为重要的现实意义，然而在DNA计算研究中，针对大型难解问题其存在着纯指数增长的DNA链数问题，为解决指数增长现值问题，提高DNA计算效率及质量，在DNA计算机算法中引入分治策略，并提出一种新型的背包问题DNA计算机算法。在分析该算法实现步骤的基础上，对其n位并行减法器及并行数据搜索器进行分析，通过对T01试管中差值与T02试管子集和值相等状况搜索进行背包问题求解。结合模拟实验，结果表明，采取这种DNA计算机算法，其能够提高破解背包公钥维数，降低背包问题所面临的DNA链数增长问题，能够为提高DNA计算机算法准确性提供一种新的路径。然而这种算法在大型难解问题中的应用还有待进一步深入研究，以充分发挥其计算优势。

参考文献：

[1] 陈改霞，耿瑞焕.基于质粒模型的DNA计算机算法求解背包问题[J].佳木斯职业学院学报，2014，（10）：159-159，162.

[2] 王旖旎.基于分治的背包问题DNA计算机算法[J].计算机光盘软件与应用，2013（4）：159.

[3] 张晓蕾.DNA计算机算法中应用分治背包问题的分析[J].山海经（故事），2015（2）：159-159.

[4] 张艳宾.分析 DNA 计算机中队列数据结构的设计与实现[J].计算机光盘软件与应用，2012（7）：198-199.

[5] 孙守霞，刘伟，郭迎，等.DNA计算机算术运算的自装配模型（Ⅲ）—减法[J].计算机工程与应用，2012，48（32）：39-42.

[6] 张凡.基于求解Ramsey数的DNA计算机算法研究[J].湖南工业职业技术学院学报，2015（2）：24-25，28.

[7] 张巍琼，郑智捷.基于不同产生机制的伪随机序列和DNA序列的随机性测量[J].成都信息工程学院学报，2012，27（6）：548-555.

[8] 郭锋.关于DNA计算机中二叉树存储结构的探讨[J].中国科技博览，2012（4）：82-82.

[9] 王树斌.因子分解问题的DNA计算机算法探究[J].电脑编程技巧与维护，2013（16）：75-76.

[10] 徐光宪，郭晓娟.基于混沌系统和DNA序列运算的新型图像加密[J].计算机应用研究，2015，32（6）：1766-1769.