论文部分内容阅读
经典Ramsey数问题是一个NP完全问题,使用传统的电子计算机求解该问题,面临着计算时间复杂度指数爆炸问题。既然传统的电子计算机求解NP完全问题显得无能为力,那么就有必要提出新的计算方法。DNA计算具有高度并行性、高密度存储空间的显著优点。所以,DNA计算用于求解NP完全问题具有理论上的可行性。论文对经典Ramsey数的DNA计算模型进行了研究和探讨。全文主要研究工作如下: 1)给出了求解经典Ramsey数问题的一种新思路,它是建立经典Ramsey数DNA计算机模型的基础。首先,建立了表示一个图序列的编码方法,并指出该编码方法所存在的问题,即存在大量图的同构问题;其次,讨论了标定与非标定子图的集合问题,重点是序列表示方法;再次,给出了删除非解的思想、方法与步骤,目的是将非解消灭在萌芽状态,并且给出了算法实例。 2)求解经典Ramsey数问题的一个关键的问题是计算图的最大团与最大独立集,图的最大团问题与最大独立集问题是两个经典的NP完全问题。论文建立了求解图的最大团与最大独立集问题两种DNA计算模型。首先,详细地介绍了求解图的最大团与最大独立集算法研究概况,重点介绍了求解经典Ramsey数问题的DNA计算模型;其次,建立了基于粘贴模型求解图的最大团与最大独立集问题的DNA计算模型。该模型是一种理论模型,实验操作具有一定的难度,可行性很大程度上受到生物技术的影响;最后,建立了一种所谓并行型最大团与最大独立集 DNA计算模型,这是一种已经可以实用的DNA计算模型,论文详细地给出了该模型的具体方法、步骤,并给出了实现每个步骤的生化操作方法。 3)建立了所谓的基于加位序列的经典Ramsey数DNA计算模型。该模型由存储子系统、运算子系统和解的检测子系统构成,应该是一个新颖的求解经典Ramsey数问题DNA计算模型。首先,给出了存储中的编码方法、步骤,诸如约束条件问题、编码算法、探针设置等;其次,建立了运算子系统,重点是以PCR技术进行生化操作的方法、步骤;最后,描述了该模型解的检测子系统。 4)建立了并行型经典Ramsey数DNA计算模型。该模型的基本思想是将一个给定图所转换的位序列进行分段,然后分别按照各个小段删除非解,再逐步逐位进行合并。具体地说,首先介绍了模型的基本思想、算法步骤;然后,给出了分段方法及相应的编码技术;接着,介绍了每个初始解空间建立的方法、步骤以及非解的删除;最后,给出了子段间的合成方法与生物实现,并且给出了一个具体的算法实例。 简言之,论文建立了求解经典Ramsey数的DNA计算模型,给出了加位序列Ramsey数DNA计算模型和并行型Ramsey数DNA计算模型。