欢迎来到天天文库
浏览记录
ID:32473594
大小:2.07 MB
页数:50页
时间:2019-02-06
《离散数学中np完全问题的dna计算》由会员上传分享,免费在线阅读,更多相关内容在学术论文-天天文库。
1、摘要从1994年至今,DNA计算已成为数学、生物学、化学、计算机科学等领域的一个研究热点,并解决了很多NP一完全问题。如何减少编码量大的问题,即解决“指数爆炸”问题,是DNA计算面临诸多困难和主要技术问题之一。这就需要我们对已有的算法进行改进或寻找新的算法。目前,DNA计算在计算原理可行性的论证上比较成熟,对于表面技术的研究还处在探索阶段,随着表面技术的日益成熟,DNA计算将会从理论走向实践。离散数学是数学的一个分支,离散数学中有诸多的NP一完全问题,如:求主范式问题,图着色问题,求传递闭包问题,最大匹配问题,旅行商问题等等。目前,DNA计算是解决NP一一完全问题最有效的方法,本
2、文采用DNA计算解决了离散数学中具有代表性的三个难计算问题:命题逻辑中“求主范式问题”;图论中“图着色问题";集合论中“求传递闭包问题"。本文首先介绍了DNA计算背景、现状、原理与基本模型。然后,解决了离散数学中上述的三个问题。第一,根据DNA发夹结构的突出优点,即不需要特殊的生物操作,这样从很大程度上减少了生物反应时间,并且根据主范式的定义与DNA发夹结构的定义知,完全可利用DNA发夹结构模型,求解离散数学中命题公式的主范式;第二,利用DNA计算机模型,采取合理编码使得解空间的生成基于三进制,并采取逐步产生满足定义的DNA链的方法,将离散数学中图3一着色问题的DNA分子链数由0
3、(3”)减少到了0(2”),这样很好地解决了图3—着色问题中的“指数爆炸’’问题,并给出了其应用;第三,利用Adleman试管模型,借鉴Hamilton路径问题的思想,求解了难计算的传递闭包问题。最后,总结了全文,讨论DNA计算与数学的密切关系及其在数学领域内的应用,并讨论了进一步的研究方向。关键词:DNA计算;可满足性问题;主范式;图着色;传递闭包摘要AbstractDNAcomputinghasbeenatouchypointforresearchinmathematics,biology,chemisty,andcomputersciencefrom1994topresen
4、tdays.IthassolvedmanyproblemssuchasNPcompleteproblem.OneofmanydifficultiesandmaintechnologythatDNAcomputingfacesishowtoreducethelargecodingquantity,namely,toslove‘'indexexplosion'’problem.Asaresult,weshouldimprovetheexistingcomputingmethodsorfindoutnewcomputingways.Atpresent,DNAcomputingisdem
5、enstratedrelativelymuturelyincomputingtheoryfeasibilityandisstillexploringsurfacetechnology.Asthesurfacethnologycomestomature,DNAcomputingsurelytendstotransferfromlaborotarytomarket.DiscretemathematicsconsistsofSOmanyNPcompleteproblems.Theyareprincipalnormalformproblem,graphcoloringproblem,tr
6、ansitiveclosureproblem,maximummatchingproblem,andtravelquotient.Nowadays,DNAcomputingisthemosteffetivemethodforsolvingNPcompleteproblems.ThispapersolvesthreetypicalproblemsindiscretemathematicsbymeansofDNAcomputing.Theyareprincipalnormalformprobleminpropositionallogic,graphcoloringproblemingr
7、aphtheory,andtransitiveclosureprobleminsettheory.ThisarticleintroducesthebackgroundofDNAcomputering,currentsituation,principleandbasicmodelatfirst.Andthen,itsolvesthreecorrespondingproblems.Firstly,astypicaladvantageofDNAhairpinstructureistha
此文档下载收益归作者所有