旅行售货员问题的DNA分子算法

论文摘要

目前在大规模并行计算模式方面主要存在两种新模式:量子计算模式和DNA计算模式。本文就DNA计算模式做一些研究。作为一种新型的计算技术,DNA计算利用DNA分子进行计算,具有传统计算机所不可比拟的优点,引起了人们极大的兴趣。随着计算机技术和分子生物技术的迅速发展,DNA计算作为一种新兴的交叉学科正逐渐发展起来,在解决大规模并行计算问题上,特别是在解决NP-完全问题上有其不可估量的优势。本文首先介绍了DNA计算的发展现状、DNA计算的数学理论、生物学基础及DNA计算的机理;分析讨论了DNA计算在解决NP-完全问题上的应用实例模型;在总结以往编码的基础上,提出了基于DNA序列表示权值大小的编码方法和基于熔点温度控制编码方法,并应用两种编码方法来解决旅行售货员问题（TSP问题）;最后给出了基于粘贴系统模型的TSP问题的DNA分子算法和应用实例。

论文目录

• 摘要
• Abstract
• 第一章 绪论
• 1.1 选题意义
• 1.2 DNA 计算的发展
• 1.3 DNA 计算的应用与研究现状
• 1.4 目前存在的问题
• 1.5 本论文主要内容
• 第二章 DNA 计算的数学理论
• 2.1 DNA 的四元代数结构
• 2.2 粘贴系统
• 2.2.1 粘贴系统的几个基本概念
• 2.2.2 粘贴运算
• 2.2.3 粘贴系统
• 2.3 插入-删除系统
• 2.3.1 DNA 结构中的插入-删除
• 2.3.2 插入-删除系统
• 2.4 剪接系统
• 2.4.1 剪接系统的概况
• 2.4.2 剪接系统
• 2.5 本章小结
• 第三章 DNA 计算的生物学基础
• 3.1 DNA 的分子结构
• 3.1.1 DNA 组成
• 3.1.2 Watson-Crick 互补
• 3.2 DNA 计算常用的酶
• 3.3 DNA 计算的生物操作
• 3.4 相关生物技术
• 3.4.1 PCR 技术
• 3.4.2 变性梯度凝胶电泳技术
• 3.5 本章小结
• 第四章 DNA 计算的机理与模型
• 4.1 Adleman 实验
• 4.2 DNA 的计算机理
• 4.2.1 基本思想
• 4.2.2 DNA 计算的实现方式
• 4.3 DNA 计算的应用模型
• 4.3.1 Hamilton 路问题
• 4.3.2 可满足性问题
• 4.3.3 TSP 问题
• 4.3.4 图的顶点着色问题
• 4.3.5 最小顶点覆盖问题
• 4.3.6 其他方面的应用
• 4.4 DNA 计算的希望与挑战
• 4.5 DNA 计算尚待解决的问题
• 4.6 本章小结
• 第五章 DNA 编码
• 5.1 编码描述
• 5.2 影响编码的因素
• 5.2.1 化学自由能
• 5.2.2 解链温度
• 5.2.3 DNA 分子的组成
• 5.2.4 编码距离
• 5.3 编码方法
• 5.3.1 模板一映射方法
• 5.3.2 最小长度子串方法
• 5.3.3 遗传算法
• 5.4 本章小结
• 第六章 旅行售货员问题的 DNA 分子算法
• 6.1 TSP 问题
• 6.2 基于用 DNA 序列表示权值大小的 TSP 问题
• 6.2.1 问题描述
• 6.2.2 算法步骤
• 6.2.3 算法的实现
• 6.3 基于用熔点温度控制编码求解 TSP 问题
• 6.3.1 问题描述
• 6.3.2 编码
• 6.3.3 旅行售货员问题的 DNA 分子算法
• 6.4 基于粘贴系统求解 TSP 问题
• 6.4.1 粘贴运算
• 6.4.2 粘贴系统
• 6.4.3 用粘贴系统求解 TSP 问题的计算模型
• 6.4.4 用粘贴系统求解 TSP 问题的算法实现
• 6.5 算法分析与讨论
• 6.6 本章小结
• 第七章 结论
• 参考文献
• 攻读硕士学位期间发表的论文
• 致谢
• 学位论文独创性声明
• 学位论文知识产权权属声明