若干图论问题的DNA计算机算法研究

摘要

Ramsey数问题、图同构问题、最小生成树问题等图论问题在当今科学研究的多个领域都有着广泛的应用,随着其应用范围的扩大,这些问题的求解规模日益庞大,但由于求解这些问题算法的复杂度太高,极大地影响了此类问题的深层次应用研究。
　　 上世纪90年代,随着Adelman在DNA计算领域的开拓性工作的展开,DNA计算凭借着其海量的存储空间与可高度并行运算的能力,在理论上克服了传统电子计算机存储与运算速度方面的不足,已成为求解图论中NP完全问题及其它难解问题的潜在解决方案之一。随着生化技术的不断成熟,理论和实验上能够求解的NP完全问题的规模也越来越大。
　　 由于目前的DNA计算机尚不似传统计算机般通用,求解一个问题的DNA计算机算法很难不做修改的应用于其它类似问题,相应的几乎所有基于DNA超级计算的算法均采用完全穷举方式。这种方式的直接后果造成了目前DNA计算中的“指数爆炸”问题,即基于穷举方法的DNA计算算法中所需的DNA链的数目随问题规模的增大而呈指数量级增长,该问题已成为限制DNA超级计算机算法应用和发展的瓶颈。因此,既具有多项式求解时间又可克服DNA链数呈指数爆炸的DNA计算机新算法和模型的研究日显重要,已成为理论计算机科学的重要研究内容之一,具有相当的理论和实践意义。
　　 本文对DNA计算的“指数爆炸”问题展开了一定的探索,通过将传统电子计算机并行算法设计的策略和方法引入到DNA超级计算中,设计了求解Ramsey数问题、图同构问题、最小生成树问题三种图论问题的DNA计算机新算法,并对其DNA生化计算过程进行了仿真模拟验证。
　　 Ramsey理论是图论中一个庞大而又丰富的领域,在集合论、逻辑学、分析、以及代数学上具有极重要的应用。Ramsey数的求解是当前科学极难解决的问题之一。将Adleman—Lipton模型生物操作与粘贴模型解空间相结合的DNA计算模型进行扩展,在许进等提出来的位序列编码方法的基础上,提出了一种用于求解Ramsey数的DNA计算模型与算法。算法从下界开始,直到上界,每次产生问题的解空间,然后根据Ramsey数的定义,删除满足特定条件的解,最后检测最终的试管,以确定当前值是否为所要求的Ramsey数,从而得到具体的Ramsey数值,算法性能的理论分析和模拟实验结果表明了本算法在求解Ramsey数上的理论可能性,同时,由于使用了错误率更低的DNA计算模型,和同类算法相比,新算法具有更低的误解率,生物操作也更为简单。
　　 在上述算法的基础上,利用分治法这一算法设计技术,设计了一种基于分治的求解Ramsey数DNA计算机算法,和前述算法相比,新算法的操作时间基本维持不变,但显著地减少了算法所需的DNA链数,从而扩大了DNA计算理论上所能求解Ramsey数的问题的规模。
　　 图的同构问题属于经典的NP完全问题之一,在Sun基于粘贴模型提出的DNA分子计算算法的基础上,对图同构问题的DNA计算机算法进行进一步研究,提出了一种基于粘贴模型和Adleman—Lipton解空间的图同构问题DNA计算机算法,算法中利用了结点的度序列概念,算法操作简单,在最坏情况下仅需O(2n) DNA链数,其中n是图的顶点数,而且保持了算法的生化操作次数仍为多项式量级。
　　 最小生成树是图论中被广为研究的问题之一,具有重要的应用背景。本文基于Adleman模型的生物操作与粘贴模型的解空间,提出的一种求解最小生成树问题的DNA计算机新算法。新算法由解空间生成器、边导出子图搜索器、生成树搜索器及最小生成树搜索四部分组成,算法求解具有m条边,n个顶点的最小生成树问题所用到的生物操作数为O(n2),测试试管数为O(n),最大链长度为O(m+n),DNA链数为O(2m)。由于使用了具有更低杂交错误率的DNA计算机模型,该算法提高了基于DNA计算解决生成树问题算法的容错性与精确性。

目录

文摘

英文文摘

论文说明:图表目录

第1章 绪论

1.1 本文的研究背景和目的

1.2 DNA计算研究的基本思想,国内外现状与未来发展趋势

1.2.1 DNA计算的基本思想和特性

1.2.2 DNA计算涉及的研究领域

1.2.3 DNA计算的应用

1.2.4 DNA计算模型和算法

1.2.5 DNA计算机算法可扩展性研究

1.3 本文主要工作

1.4 本文组织结构

1.5 小结

第2章 预备知识

2.1 导语

2.2 计算复杂性概念

2.3 图论中的RAMSEY数、图同构和最小生成树问题

2.3.1 Ramsey数问题

2.3.2 图同构问题

2.3.3 最小生成树问题

2.4 DNA计算模型

2.4.1 粘贴模型和粘贴系统

2.4.2 ADLEMAN-LIPTON计算模型

2.4.3 其它模型

2.5 小结

第3章 求解RAMSEY数的DNA计算机算法

3.1 RAMSEY数问题的DNA计算模型

3.1.1 问题描述

3.1.2 DNA计算模型

3.2 RAMSEY数问题的DNA计算机算法

3.2.1 算法思想

3.2.2 Ramsey数R(m,n)的解空间

3.2.3 删除m阶完全子图的DNA计算机算法

3.2.4 删除n阶完全空图的DNA计算机算法

3.2.5 求解Ramsey数R(m,n)的DNA计算机算法

3.2.6 性能分析

3.3 模拟实验结果

3.3.1 图的编码

3.3.2 算法求解过程

3.4 结论

第4章 基于分治的RAMSEY数的DNA计算机算法

4.1 RAMSEY数问题求解新算法

4.1.1 求解Rarnsey数问题新DNA算法思路

4.1.2 分治法

4.1.3 解空间生成器的框架

4.1.4 并行搜索框架

4.1.5 子空间搜索框架

4.1.6 Ramsey数产生器的构造

4.1.7 基于分治的Ramsey数问题的算法

4.2 算法性能分析与比较

4.2.1 算法性能分析

4.2.2 算法性能比较

4.3 仿真实验

4.3.1 DNA编码

4.3.2 Ramsey数问题的新算法的求解过程

4.4 结论

第5章 图同构问题的DNA计算机算法

5.1 粘贴模型和图同构问题

5.2 图同构问题的DNA计算机算法

5.3 算法性能分析与比较

5.3.1 算法性能分析

5.3.2 算法性能比较

5.4 模拟仿真实验

5.4.1 DNA编码

5.4.2 求解图同构问题的改进算法运算进程

5.5 结论

第6章 最小生成树问题的DNA计算机算法

6.1 最小生成树的定义

6.2 最小生成树的DNA计算机算法思想

6.2.1 解空间的建立

6.2.2 生成树可满足解空间搜索器

6.2.3 边导出子图生成器

6.2.4 生成树搜索器

6.3 最小生成树问题DNA计算机算法

6.4 模拟实验结果

6.4.1 DNA编码

6.4.2 算法求解过程

6.5 结论

结论

参考文献

致谢

附录A (攻读博士学位期间发表的论文)