离散数学中np完全问题的dna计算

《离散数学中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