论文部分内容阅读
DNA计算是一种新的计算模式，它以DNA(deoxyribonucleic acid，脱氧核糖核酸)为“原料”，以生化实验为工具进行计算。DNA分子具有庞大的存储容量，DNA计算具有其它计算方法无法比拟的巨大的并行性。自1994年美国南加州大学的Adleman教授用生化实验解决了七个顶点的有向哈密尔顿路径问题(Directed Hamilton Path Problem，DHPP)以来，有关DNA计算的科研工作迅速在许多国家展开。虽然已取得了可喜的成果，但目前的研究还是理论研究居多，有关实验操作、实验装置的研究则很少；再者，有许多经典的图论问题、数学问题等还未有DNA算法；有些问题虽有DNA计算方法，但仍有可改进之处。粘贴模型和剪接模型是DNA计算中的两种最主要的模型。粘贴模型和剪接模型有着同等的计算能力，粘贴模型所使用的DNA链具有固定的长度，操作时不需要扩展DNA链，也无需酶的参与，而且它的材料在理论上可以重复使用。因此，有关粘贴模型的研究开展得比较快，许多问题的粘贴DNA算法也被相继提出。但是，由于粘贴模型仅采用原有的四种基本操作，实验操作步骤较多，耗费了大量时间，鉴于此，本文提出了多级分离的概念，设计了一个多级分离装置的模型。利用多级分离装置可以实现DNA计算中的多种基本操作，并能实现“多级分离”操作，大大减少实验步骤，成倍提高解题效率。本文应用多级分离技术解决了以下三个问题：(1)马步遍历问题。文中给出了基于Adleman模型解决扩展棋盘上马步遍历问题的DNA算法。使用基本的“分离”操作即可解决该问题，本文使用了多级分离，旨在说明多级分离装置也可以完成基本的分离操作。(2)图顶点着色问题。该问题是一个典型的NP-完全问题，目前，已有人提出了解决该问题的DNA算法，但存在着编码方式复杂、将问题复杂化、效率不高等问题。本文利用Lipton解决可满足性(Satisfiability，SAT)问题的思想，给出了解决该问题的一种粘贴DNA算法；并引入多级分离技术加以改进，减少了操作步骤，提高了解题效率。(3)地图k-着色问题。四色定理告诉我们，任意地图都可以用四种颜色正常着色。但有些地图或许需要更少的颜色。本文将地图k-着色问题转化为顶点着色问题进行解决。在解决以上三个问题时，文中都给出了具体的实例，并通过模拟实验得到了具体的解决方案，说明了算法的可行性和有效性。