dna计算在整数规划问题中的应用

《dna计算在整数规划问题中的应用》由会员上传分享，免费在线阅读，更多相关内容在教育资源-天天文库。

1、275,..第卷第期电子与信息学报、七127No52005年5月JoalofElectronies&InformationTeehnologyMay2005urn计算在整数规划问题中的应用王雷林亚平(湖南大学计算机与通信学院长沙41082):,一摘要基于生化反应原理的DNA计算由于在解决一类困难问题特别是NP完全问题上具有硅计算机无法比拟,因此对。DNA,的优势DNA计算的研究具有重要意义利用在基于表面的计算中采用荧光标记的策略提出了一,,种基于DNA计算的一类特殊整数规划问题最优解的求解算法新算法利用荧光碎灭

2、技术通过观察DNA分子表。,。面的荧光来排除非解算法分析表明新提出的基于DNA计算的求解算法具有编码简单和错误率低等特点:,,,关键词DNA计算整数规划问题荧光标记最优解::^:一一一中图分类号TP301文献标识码文章编号10095896(2005)05081405DNAComPutationforaCategoryofSPeeialIntegerPlanningProblem.认恤ngLeiLinYaPing,,,(COllegeofCOmPutera刀dCOm脚unjcattonnanUnive咫i粉Cha

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

4、olvestheProblemofaeategoryofsPeeialintegerPlanningProblemusingthemethodoffluoreseeelangintsurebasedaPProeomPutaon.utiliznebyncbelihefacachtoDNAtiByigth,teehniquesoffluoreseeneedistinguishingthenewalgorithmeaneliminateallofthosefalsesolutionsthroughobservingt

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

6、子计算是可行的文献[6]给出了一种DNA计算的矩阵乘法运算模型,解决了布尔矩阵和正实矩阵的乘法问题。文献随着计算机技术的不断发展,各种复杂的非线性问题和,一,〔7]应用DNA计算方法开拓性地解决了一个给定有向图的NP完全问题在新工程领域不断出现而现在的电子计算机。,有向Hilton路问题仿效文献〔7]中的方法文献[8]给出了由于运算速度太慢,存储容量太小,无法解决这类困难问题。am一种对于可满足性问题(s问题。)的DNA计算模型文而NA,,,ATD处理器使用廉价干净易于获得的生物材料可以DNA“”,一。献191

7、利用单链分子的发夹结构解决了一个3sAT处理繁重的并行运算在摩尔定律的末日即将到来的新世纪。,问题1998年Liu给出了一种基于表面的S问题的算,AT里计算机科学家们正在寻找一种带领处理器速度突破硅质。。一法110随后文献[ll]对其进行了改进o1规划问题是运筹学。微电子线路的速度和尺寸极限的出路DNA计算技术恰好,中的一个重要问题其应用非常广泛。关于它的算法很多,如。,满足了他们的需要因此对DNA计算技术进行深入研究,具有重要意义日一3]。枚举法等但到目前为止还没有一个很好的算法完全解决该。1,,,,问题文献

8、〔2]给出了一种基于荧光标记的策略将DNA计目前人们己对DNA计算机展开了研究在DNA计算中一l,一,,算应用于O规划问题解决了一类特殊O1规划问题即指派首先取得突破性进展的是Frank等人I’]其开创性地给出了问题的推广。,,二进制数01的DNA表示方法然后在此基础上建立了1,D。e在文献t2]的基础上本文提出了约束方程组的秩以及NA计算的加法运算模型199年,Bmard提出了一种新