dna計(jì)算在整數(shù)規(guī)劃問(wèn)題中的應(yīng)用

《dna計(jì)算在整數(shù)規(guī)劃問(wèn)題中的應(yīng)用》由會(huì)員上傳分享，免費(fèi)在線閱讀，更多相關(guān)內(nèi)容在教育資源-天天文庫(kù)。

1、275,..第卷第期電子與信息學(xué)報(bào)、七127No52005年5月JoalofElectronies&InformationTeehnologyMay2005urn計(jì)算在整數(shù)規(guī)劃問(wèn)題中的應(yīng)用王雷林亞平(湖南大學(xué)計(jì)算機(jī)與通信學(xué)院長(zhǎng)沙41082):,一摘要基于生化反應(yīng)原理的DNA計(jì)算由于在解決一類困難問(wèn)題特別是NP完全問(wèn)題上具有硅計(jì)算機(jī)無(wú)法比擬,因此對(duì)。DNA,的優(yōu)勢(shì)DNA計(jì)算的研究具有重要意義利用在基于表面的計(jì)算中采用熒光標(biāo)記的策略提出了一,,種基于DNA計(jì)算的一類特殊整數(shù)規(guī)劃問(wèn)題最優(yōu)解的求解算法新算法利用熒光碎滅

2、技術(shù)通過(guò)觀察DNA分子表。,。面的熒光來(lái)排除非解算法分析表明新提出的基于DNA計(jì)算的求解算法具有編碼簡(jiǎn)單和錯(cuò)誤率低等特點(diǎn):,,,關(guān)鍵詞DNA計(jì)算整數(shù)規(guī)劃問(wèn)題熒光標(biāo)記最優(yōu)解::^:一一一中圖分類號(hào)TP301文獻(xiàn)標(biāo)識(shí)碼文章編號(hào)10095896(2005)05081405DNAComPutationforaCategoryofSPeeialIntegerPlanningProblem.認(rèn)恤ngLeiLinYaPing,,,(COllegeofCOmPutera刀dCOm腳unjcattonnanUnive咫i粉Cha

3、ngsha410082China)HuAbstetBioeealreactiontorybasedDNAeomPutation15ofmuchbereeinsolviaelassofrahemiheteperformanng一,.Intr朗tableeomPutatlonalProblemssuchasNPeomPleteProblemsit15importanttostu勿theDNAeomPutationAnovel,algorithmbasedonDNAeomPutaion15ProPosedwhiehs

4、olvestheProblemofaeategoryofsPeeialintegerPlanningProblemusingthemethodoffluoreseeelangintsurebasedaPProeomPutaon.utiliznebyncbelihefacachtoDNAtiByigth,teehniquesoffluoreseeneedistinguishingthenewalgorithmeaneliminateallofthosefalsesolutionsthroughobservingt

5、hefluoreseeneeonthesurfaeeofDNAmoleeules.AlgorithmanalysesshowthatthenewProposedalgorithlnbasedonDNAeomPutatlonhassuehgoodeharaceresseeneonourate.tistiasimPldigandlwfaltetc,,,KeywordsDNAeomPutationIgerPlanningProblemF!uoreseencelabelingtimalsolutionnteOP。引言分

6、子計(jì)算是可行的文獻(xiàn)[6]給出了一種DNA計(jì)算的矩陣乘法運(yùn)算模型,解決了布爾矩陣和正實(shí)矩陣的乘法問(wèn)題。文獻(xiàn)隨著計(jì)算機(jī)技術(shù)的不斷發(fā)展,各種復(fù)雜的非線性問(wèn)題和,一,〔7]應(yīng)用DNA計(jì)算方法開(kāi)拓性地解決了一個(gè)給定有向圖的NP完全問(wèn)題在新工程領(lǐng)域不斷出現(xiàn)而現(xiàn)在的電子計(jì)算機(jī)。,有向Hilton路問(wèn)題仿效文獻(xiàn)〔7]中的方法文獻(xiàn)[8]給出了由于運(yùn)算速度太慢,存儲(chǔ)容量太小,無(wú)法解決這類困難問(wèn)題。am一種對(duì)于可滿足性問(wèn)題(s問(wèn)題。)的DNA計(jì)算模型文而NA,,,ATD處理器使用廉價(jià)干凈易于獲得的生物材料可以DNA“”,一。獻(xiàn)191

7、利用單鏈分子的發(fā)夾結(jié)構(gòu)解決了一個(gè)3sAT處理繁重的并行運(yùn)算在摩爾定律的末日即將到來(lái)的新世紀(jì)。,問(wèn)題1998年Liu給出了一種基于表面的S問(wèn)題的算,AT里計(jì)算機(jī)科學(xué)家們正在尋找一種帶領(lǐng)處理器速度突破硅質(zhì)。。一法110隨后文獻(xiàn)[ll]對(duì)其進(jìn)行了改進(jìn)o1規(guī)劃問(wèn)題是運(yùn)籌學(xué)。微電子線路的速度和尺寸極限的出路DNA計(jì)算技術(shù)恰好,中的一個(gè)重要問(wèn)題其應(yīng)用非常廣泛。關(guān)于它的算法很多,如。,滿足了他們的需要因此對(duì)DNA計(jì)算技術(shù)進(jìn)行深入研究,具有重要意義日一3]。枚舉法等但到目前為止還沒(méi)有一個(gè)很好的算法完全解決該。1,,,,問(wèn)題文獻(xiàn)

8、〔2]給出了一種基于熒光標(biāo)記的策略將DNA計(jì)目前人們己對(duì)DNA計(jì)算機(jī)展開(kāi)了研究在DNA計(jì)算中一l,一,,算應(yīng)用于O規(guī)劃問(wèn)題解決了一類特殊O1規(guī)劃問(wèn)題即指派首先取得突破性進(jìn)展的是Frank等人I’]其開(kāi)創(chuàng)性地給出了問(wèn)題的推廣。,,二進(jìn)制數(shù)01的DNA表示方法然后在此基礎(chǔ)上建立了1,D。e在文獻(xiàn)t2]的基礎(chǔ)上本文提出了約束方程組的秩以及NA計(jì)算的加法運(yùn)算模型199年,Bmard提出了一種新