基于質(zhì)粒模型的DNA計(jì)算機(jī)算法求解背包問題

陳改霞 耿瑞煥

(鶴壁汽車工程職業(yè)學(xué)院 河南鶴壁 458030)

基于質(zhì)粒模型的DNA計(jì)算機(jī)算法求解背包問題

陳改霞 耿瑞煥

(鶴壁汽車工程職業(yè)學(xué)院 河南鶴壁 458030)

本研究在窮舉法的背包策略的基礎(chǔ)上借鑒二表算法的思路，應(yīng)用求解最大團(tuán)問題的思路計(jì)算DNA計(jì)算機(jī)的NP完全計(jì)算問題。使用這種算法，能將DNA分子計(jì)算的維數(shù)從60擴(kuò)大至120，這種算法的DNA鏈數(shù)可達(dá)亞指數(shù)的O(1 414n)，這種算法拓展了窮舉法背包策略的限制，使DNA計(jì)算機(jī)NP完全問題算法優(yōu)化。

質(zhì)粒模型；DNA計(jì)算機(jī)算法；背包問題

一、質(zhì)粒模型算法提出的背景

所謂的背包問題，是指一種背包組合的原理。它是在容積一定的前提下，要如何組合才能使包中的價值最大。這個問題研究的核心，是人們要在條件資源已經(jīng)限制的情況下，計(jì)算出收益最大的一種組合方法。背包問題的思想經(jīng)常應(yīng)用在優(yōu)化組合的領(lǐng)域上，而DNA計(jì)算的問題就是非常典型的優(yōu)化組合的問題。

DNA計(jì)算問題的實(shí)質(zhì)就是把需要運(yùn)算的對象當(dāng)作DNA分子鏈，然后通過某種算法讓這些分子鏈優(yōu)化組合，最后形成一個結(jié)果，而這個結(jié)果必須是可控的過程。這種算法過程非常復(fù)雜。要得到滿足人們需求的DNA算法。其算法必須滿足以下幾個要求：要能提出最多的組合方式、該組合方式必須是可控的、組合的結(jié)果必須滿足人們的需求。本次研究以這些算法的需求為方向，提出一種質(zhì)粒模型算法，這種算法的DNA鏈數(shù)可達(dá)亞指數(shù)的O(1 414n)，而 即為背包問題的維數(shù)，這種算法的試管級水平可達(dá)120，使用這種算法是DNA計(jì)算機(jī)算法中極為優(yōu)異的一種算法。

二、質(zhì)粒模型算法應(yīng)用的優(yōu)勢

計(jì)算機(jī)求解NP的完全問題一直是人們認(rèn)為難解的問題，如果沒有一個合理的算法，它的計(jì)算長度、計(jì)算時間、計(jì)算過程都難以控制。于是人們提出把這種計(jì)算問題映射成DNA算法的問題，，利用DNA 鏈的思路進(jìn)行計(jì)算。然而應(yīng)用DNA算法的思路求解也存在一些難題。

控制性的難題——DNA計(jì)算機(jī)求解NP的過程，是一種組合優(yōu)化的問題，這種問題適合用計(jì)算機(jī)模型來解決。隨著科學(xué)技術(shù)的發(fā)展，計(jì)算機(jī)的計(jì)算模型也飛速的進(jìn)步，然而就DNA計(jì)算機(jī)求解NP的問題而言，它依然存在很多問題。其中最大的問題為控制性的問題。目前DNA計(jì)算中應(yīng)用到雜交、退火、探針的算法，都有可能出現(xiàn)計(jì)算的不穩(wěn)定性，然后出現(xiàn)偽解。為了解決這個問題，必須要使計(jì)算機(jī)模型的算法本身具有穩(wěn)定性。目前質(zhì)粒的DNA計(jì)算機(jī)模型是成功的解決了最大權(quán)團(tuán)的算法問題，它在計(jì)算的過程中不易受到其它醇的干擾。雖然這種算法本身還有一定的難度，可是其穩(wěn)定性與準(zhǔn)確性均能得到保證，這就是計(jì)算的控制性能得到保證。

拓展性的難題——DNA計(jì)算機(jī)算法的原理，是人們提出的以DNA計(jì)算模型為基礎(chǔ)的解3色的問題，以這種方式解決給合優(yōu)化的問題。然而最初這種原理只能解O(1 67n) 的鏈數(shù)，且這種算法的偽解較多，可拓展性較差，它難以被廣泛的實(shí)踐應(yīng)用。目前人們也提出了其它的DNA計(jì)算機(jī)算法，然而絕大多數(shù)的計(jì)算方法對時間和長度要求很高，其拓展性也比較差?；谫|(zhì)粒模型的算法是以背包問題為前提進(jìn)行計(jì)算，它的時間與長度都被嚴(yán)格控制，所以它的可拓展性也能得到保證。

準(zhǔn)確性的難題——為了優(yōu)化NDA計(jì)算機(jī)的算法，曾經(jīng)有人提出求解最大團(tuán)的算法，這種思路能夠控制計(jì)算的時間，它是DNA計(jì)算機(jī)算法的一種新突破。然而如何能確保在一定的時間內(nèi)控制最大團(tuán)的最高計(jì)算概率，是人們對這種算法的又一種要求。該次提出的質(zhì)粒模型算法應(yīng)用了背包問題的思路解決了在時間和空間被限制的前提下，提高準(zhǔn)確率的難題。

由于以上質(zhì)粒模型算法的優(yōu)勢，它能在操作次數(shù)不變的前提下，控制最全部的計(jì)算過程，得到極高的亞折數(shù)，這種算法在NDA計(jì)算機(jī)算法中非常具有優(yōu)勢。

三、質(zhì)粒模型算法的基本流程

如果要用背包問題的理論控制質(zhì)粒模型的計(jì)算，就要給定以下的數(shù)值：

正整數(shù)q的集合W=(W1,,W2,W3……,Wn)；

正整數(shù)M的數(shù)值；

以上兩者的數(shù)值決定q元組x的數(shù)值，而q可描述為：(x1,x2,x3,……,xq) 。

這種算法能夠以背包問題的思路來解決質(zhì)粒算法的時間與長度控制的問題，它能提高這類問題的并行度。這種算法的核心是使用窮舉法的算法，然而它的背包數(shù)量被限制為60，為了突破背包數(shù)量的限制，該次算法借鑒了二表算法，即應(yīng)用求解最大團(tuán)問題的思路計(jì)算DNA計(jì)算機(jī)的NP完全計(jì)算問題。

這種計(jì)算思路為將正整數(shù)q的集合W=(W1,,W2,W3……,Wn)拆分為 和 兩個背包，然后求出兩個部分的子集和，而子集合的背包容量為O(1 414n)，使用這種二表算法中二表求和的思路以后，再與M進(jìn)行比較，判可否有解轉(zhuǎn)換成先求M與一個子集所有子集和的差；之后以同樣的方法再用另一個部分的子集進(jìn)行有解決斷。這種計(jì)算方法既能突破背包的限制，又能使DNA計(jì)算的方法更規(guī)范化。在這種計(jì)算方法中，由于要將背包數(shù)限制為1.14n這個鏈數(shù)，所以計(jì)算操作時間與長度都能得到控制。

這種計(jì)算方法的控制，主要從三個方面進(jìn)行控制：編譯的問題，即在做編譯階段時，要將求解的問題映射到DNA鏈上；以質(zhì)粒模型的思路求解，而求解的長度控制、時間控制則由以背包思路控制；使用二表算法優(yōu)化背包思路的算法。該過程為全部的算法思路。這種算法可描述如下：

賦予數(shù)值環(huán)節(jié)——

步驟1：將集合W=(W1,,W2,W3……,Wn)按升序排列，并將其分成兩個元素個數(shù)相等的子集W1和W2。W1取按升序排列好后的W中的前n/2個元素，而W2取按升序排列好后的W的后n/2。以W1,i表示W(wǎng)1中的第i個元素，W2,i表示W(wǎng)2的第i個元素；

輸入數(shù)值環(huán)節(jié)——

步驟2：將實(shí)驗(yàn)杯T0中，給W1,i、W1,i-W1,i、M分量的值進(jìn)行編碼；

步驟3：把T0產(chǎn)生的DNA片段插入到開口的質(zhì)粒中，當(dāng)形成一個閉環(huán)質(zhì)粒以后，將該質(zhì)粒放入到大腸桿菌中擴(kuò)增；

步驟4：將W1和W2視為背包，將之初始化，把T0產(chǎn)生的質(zhì)粒放入等量的杯子里。杯子可描述為T1和T2。

計(jì)算數(shù)值環(huán)節(jié)——

步驟5：W1子集數(shù)值生成，計(jì)算M與W1里所有子集和的差；

步驟6：W2子集數(shù)值生成，計(jì)算W2里所有子集之合；

輸出數(shù)值環(huán)節(jié)——

步驟7：找出鏈長相等的質(zhì)粒，該計(jì)算可用凝膠電泳技術(shù)實(shí)現(xiàn)；

步驟8：步驟7中所有的質(zhì)粒所含的背包分量的并即即為所得結(jié)果；

步驟9：輸出數(shù)值結(jié)果，完成計(jì)算流程。

四、總結(jié)

DNA計(jì)算機(jī)NP完全問題數(shù)值計(jì)算的問題直至現(xiàn)在都被認(rèn)為是難解的數(shù)學(xué)難題。目前人們使用窮舉法解決這個問題，然后用背包思路限制窮舉法數(shù)值計(jì)算的時間和長度，然而窮舉法的背包數(shù)量不能滿足人們的需求，它無法計(jì)算變量數(shù)集多的NP完全問題。本次在窮舉法的背包策略的基礎(chǔ)上借鑒二表算法的思路，應(yīng)用求解最大團(tuán)問題的思路計(jì)算DNA計(jì)算機(jī)的NP完全計(jì)算問題。使用這種算法，能將DNA分子計(jì)算的維數(shù)從60擴(kuò)大至120，，這種算法的DNA鏈數(shù)可達(dá)亞指數(shù)的O(1 414n)，這種算法拓展了窮舉法背包策略的限制，使DNA計(jì)算機(jī)NP完全問題算法優(yōu)化。

[1]唐悅.動態(tài)規(guī)劃的新形式0/1背包問題的兩種解法[J].網(wǎng)絡(luò)科技時代(數(shù)字沖浪),2002(03).

[2]楊曉燕.溫振華.一種求解背包問題的改進(jìn)離散粒子群優(yōu)化算法[J].梧州學(xué)院學(xué)報,2010(03).

[3]王志剛.譚沈陽.求解0-1背包問題的粒子群優(yōu)化算法[J].廊坊師范學(xué)院學(xué)報(自然科學(xué)版),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

［責(zé)任編輯： 劉 乾］

陳改霞（1980-），女，漢族，河南周口人，碩士，鶴壁汽車工程職業(yè)學(xué)院講師，研究方向：計(jì)算機(jī)應(yīng)用和計(jì)算機(jī)網(wǎng)絡(luò)。

耿瑞煥（1986-），女，漢族，河南濮陽人，碩士，鶴壁汽車工程職業(yè)學(xué)院助教，研究方向：模式識別、人工智能。