基于質粒模型的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-），女，漢族，河南濮陽人，碩士，鶴壁汽車工程職業學院助教，研究方向：模式識別、人工智能。