一种改进的DNA计算模型研究

论文摘要

DNA计算以其海量存储和并行运算能力,从理论上可克服电子计算机存储量与运算速度上的不足,成为NP完全问题和其它难解问题的潜在解决方案之一,并且在理论上已成功的在多项式时间下解决了许多著名的NP完全问题。然而,由于DNA计算模型尚不似传统计算机中的通用,求解一个问题的DNA计算模型或算法通常很难不作修改地用于其它类似问题的求解,因此,不管基于DNA计算的何种模型,目前几乎所有的基于DNA超级计算的算法均使用完全穷举方式。这种方法的直接后果是DNA计算算法中呈纯指数量级增长的DNA链数。随着DNA计算研究的逐渐深入,现有的基于穷举方法的DNA计算算法中存在的解空间指数爆炸问题日益突出,已成为限制DNA超级计算应用的瓶颈。因此考虑将传统电子计算机并行处理的策略、方法和技术引入DNA超级计算是降低DNA链数的重要途径之一。本文通过对现有DNA计算模型中的生物操作特性进行深入分析,采用理论分析和生物实践相结合的方法,对现有的Chang等提出的DNA计算模型的基础上对其不可扩展部分进行改进。同时从电子计算机中传统并行计算和并行处理的模型出发,将传统并行处理的策略和DNA计算的特点相结合,将电子计算机并行计算中的具有普适性的分治算法设计技术应用于求解子集和问题及可满足性问题的DNA计算中,提出一种具有良好可扩展性的子集和问题及可满足性问题的基于DNA计算新模型的算法,理论分析表明:新算法在不提高算法的时间复杂度的前提下,可将求解子集和问题及可满足性问题所需的DNA链数从穷举算法的O(2n)减少至O(2n/2)。

论文目录

• 摘要
• Abstract
• 第1章 绪论
• 1.1 本文的研究目的与意义
• 1.2 DNA 计算研究的国内外现状、水平与发展趋势
• 1.2.1 DNA 计算模型和算法
• 1.2.2 DNA 计算的可扩展性的相关研究进展
• 1.3 本文主要工作
• 1.4 本文组织结构
• 1.5 小结
• 第2章 预备知识
• 2.1 子集和问题和SAT 问题
• 2.2 计算复杂性概念
• 2.3 DNA 计算模型
• 2.3.1 粘贴DNA 计算模型
• 2.3.2 Adleman-Lipton 计算模型
• 2.3.3 Chang et al.模型
• 2.4 小结
• 第3章 基于分治的子集和问题DNA 计算算法
• 3.1 子集和问题的DNA 计算算法
• 3.1.1 基于分治法的子集和问题DNA 计算算法思想
• 3.1.2 n 位并行减法器
• 3.1.3 n 位并行数据搜索器
• 3.1.4 子集和问题的DNA 计算算法
• 3.2 模拟实验结果
• 3.2.1 DNA 编码
• 3.2.2 算法求解过程
• 3.3 小结
• 第4章 基于改进DNA 计算模型的子集和问题算法
• 4.1 引言
• 4.2 二表算法及DNA 计算模型
• 4.2.1 二表算法
• 4.2.2 子集和问题DNA 计算模型
• 4.3 子集和问题的DNA 计算算法
• 4.3.1 并行搜索器
• n）链数的DNA 计算算法'>4.3.2 子集和问题O（1.414ⁿ）链数的DNA 计算算法
• 4.3.3 性能分析与比较
• 4.4 算法实现
• 4.4.1 DNA 编码
• 4.4.2 算法求解过程
• 4.5 小结
• 第5章 基于改进模型的 SAT 问题DNA 计算算法
• 5.1 基于DNA 计算的求解SAT 问题算法
• 5.1.1 基于DNA 计算的SAT 问题的二表算法
• 5.1.2 基于改进模型的逻辑加算法
• 5.1.3 基于改进模型的逻辑乘算法
• 5.1.4 基于改进模型的SAT 问题DNA 计算算法
• 5.2 算法实现
• 5.3 小结
• 结论
• 1.本文工作总结
• 2.下一步工作展望
• 参考文献
• 附录 A （攻读硕士期间发表论文目录）