DNA计算,又称为生物分子计算,是基于生化反应的一种全新的计算模式。对于复杂的NP完全问题,DNA计算机与传统晶体管计算机相比,具有其无可比拟的优势,如:高度并行性、巨大的存储容量、超低的能耗和快的运行速度。因此,DNA计算方法及计算理论的研究对分子计算机的实现具有重要意义,近期的研究也表明,DNA计算在特定的复杂问题或领域里已显示出极大的潜力,并具有光明的应用前景。1994年,美国南加州大学的Adleman教授用生化实验开创性地解决了七个顶点的有向哈密尔顿路径问题(Directed Hamilton Path Problem,DHPP)。之后,DNA计算迅速成为活跃的科学研究领域,有关DNA计算的科研工作也迅速在许多国家展开。研究的内容涉及DNA计算模型、一些NP问题的DNA算法、数据加密、智能控制、DNA数据存储、DNA计算的复杂性、分子高级语言、DNA计算方法与各种软科学的结合或集成等等。不但受跨学科研究所限,而且由于生物实验过程的复杂性,实验环境难以搭建,因此,虽然众多研究中已取得较为丰硕的成果,但目前的研究还是以理论研究居多。但仅在DNA计算的理论研究领域,就有许多经典的图论问题、组合优化问题、数学问题等可以用DNA计算方法来解决,即便有些问题已有DNA计算方法,但仍有可改进之处。但是,研究DNA计算方法最终是为了研制出有应用价值的DNA计算机。所以,DNA计算中生物实验操作、实验装置、实验环境、理论与实践的联接与融合就显得尤为重要,这也应该是DNA计算领域里众多专家、学者进一步努力的方向。粘贴模型和剪接模型是DNA计算中的两种最主要的模型。粘贴模型是一种通用计算机系统,该模型有着与剪接模型同样的计算能力,而且具有不需要延伸DNA链、不需要酶的参与以及材料可以重复利用等优点。因此,有关粘贴模型的研究开展得比较快,许多问题的粘贴DNA算法也相继被提出。本文就是以DNA计算的粘贴模型为基础,解决了一些困难的NP完全问题,并对这些问题的算法进行了实验仿真。(1)基于Adleman解决Hamilton问题的思路详细求解顶点的最小覆盖(Minimun Vertex Cover Problem,MVCP)问题。该算法首先生成了满足顶点覆盖的所有可满足解,然后在可满足解中直接分离出最小顶点覆盖的解,这样大大提高了实验的效率与分离解的准确性。(2)基于DNA计算的粘贴模型,通过把逻辑演算问题转化为对应的开关网络图和Lipton模型的接触网络图,借鉴Lipton模型求解可满足性问题的方法解决了一个经典的逻辑演算问题,进一步开阔了DNA计算解决离散数学中各种问题的思路。(3)粘贴系统是将Watson-Crick互补原理用于DNA计算的抽象的计算模型,是一种基于粘贴运算的语言生成器。基于粘贴系统将旅行商(TravalSalesman Problem,TSP)问题转化为求赋权图中权值最小的Hamilton圈问题,按照这一思路详细求解了此NP完全问题。同时,对问题编码进行了进一步完善。在解决以上三个问题时,文中都给出了具体问题的实例模型、编码、算法的详细描述,并对TSP问题进行仿真试验得出问题的正确解,从而,说明了算法的可行性和有效性。声明:由于DNA计算涉及生物实验,受实验环境所限,本文偏向理论研究,请诸位能予以谅解。