科研之友
微信
新浪微博
Facebook
分享链接
摘要
目前DNA计算机研究中遇到的最大瓶颈是解空间指数爆炸问题,即随着问题规模的增大,所需要作为信息处理"数据"的DNA分子呈指数级增大。本文提出了一种新颖的图顶点着色DNA计算模型,该模型正是围绕着如何克服解空间指数爆炸问题以及如何提高运行速度而设计的。其主要贡献有:(1)通过如下三种方法来克服解空间指数爆炸问题:顶点颜色集的确定方法;子图分解方法以及子图中的顶点优化排序方法;(2)设计了一种并行型聚合酶链反应(PCR)操作技术,应用这种技术一次可以对图中多条边来删除非解,使得生物操作次数大大减少,极大地提高了运行速度。本文以一个3-着色的61个顶点的图为例,实验表明,99%的非可行解在构建初始解空间时就被删除,并利用DNA自组装和并行PCR方法,通过识别、拼接以及组装等技术得到解。由于该模型对任意61个顶点的图是同样的操作方法,这就意味着,该模型的搜索能力可以达到O(3~(59))。
- 单位
