DNA计算原理在NP-完全问题中的应用

DNA计算是一种利用生物分子间的相互作用来实现并行计算的新的计算模式,具有高度的并行性、巨大的信息存储能力和极低的能耗等优点。该文对DNA计算的一般原理进行了介绍,且介绍了DNA计算原理在解决NP问题方面所取得的进展,并指出了DNA计算中存在的问题。

一类NP-完全问题在阈图上的解

本文给出了判定阈图是否为哈密顿图的多项式时间算法,并证明了阈图上STEINER树问题是NP-完全的,给出解答它的多项式时间近似算法。

DNA计算在求解NP-完全问题的应用

基于生化反应的DNA计算模型越来越受到关注。DNA计算的研究已经成为一个热点。本文主要介绍了DNA计算在一些NP-完全问题中的应用。并分析了DNA模型存在的问题。指出未来国内DNA计算研究的重点可以在三个方面:解的检测,降低空间复杂度,生化实验研究。

3-正则图的分割问题是NP-完全问题

证明了3-正则图的最小平分问题和最小α-分割问题都是NP-完全问题.

遗传算法用于NP完全问题的求解

讨论了如何利用遗传算法求解布尔表达式的可满足性问题 ,并给出该结果对求解其他NP完全问题时的应用 .

布局问题的模拟退火算法

布局问题属于ＮＰ－完全问题已被研究多年．模拟退火法是一种新的通用启发式优化算法，现已广泛用于解决大规模集成电路逻辑布线设计、图象处理等组合优化问题．本文通过对布局问题及模拟退火算法的分析，将它们综合起来构成了求解布局问题的模拟退火算法．计算结果表明，本文算法得到的解优于传统优化方法所得到的解；文章还通过实验对算法中各参数所起作用进行了论述．

基于质粒DNA匹配问题的分子算法

给定无向图 ,图的最小极大匹配问题是寻找每条边都不相邻的最大集中的最小者 ,这个问题是著名的NP 完全问题 .1994年Adleman博士首次提出用DNA计算解决NP 完全问题 ,以编码的DNA序列为运算对象 ,通过分子生物学的运算操作解决复杂的数学难题 ,使得NP 完全问题的求解可能得到解决 .提出了基于质粒DNA的无向图的最大匹配问题的DNA分子生物算法 ,通过限制性内切酶的酶切和凝胶电泳完成解的产生和最终接的分离 ,依据分子生物学的实验手段 。

图的顶点着色问题的DNA算法

图的顶点着色问题是指无向图中任意两个相邻顶点都分配到不同的颜色 ,这个问题是著名的NP 完全问题 ,没有非常有效的算法 .但在 1994年Adleman[1] 首次提出用DNA计算解决NP 完全问题 ,设计出一种全新的计算模式—模拟生物分子DNA的结构并借助于分子生物技术进行计算 ,使得NP 完全问题的求解可能得到解决 .本文首先提出了基于分子生物技术的图的顶点着色问题的DNA算法 ,算法的关键是对图中的顶点和顶点的颜色进行恰当的编码 ,以便于使用常规的生物操作及生物酶完成解的产生及最终解的分离 ,依据分子生物学的实验方法 ,本文提出的算法是有效和可行的 ;其次指出了该算法的优点。

基于“DNA折纸术”设计图着色问题的解决方案

色数是图论中的一个重要的参数,其属于著名NP(Non-deterministic Polynomial)-完全问题范畴.巨量的着色方案使验证变得相当困难,以至于在传统计算机上无法实现.目前已经有多种算法用于研究图定点着色问题,比如遗传算法,粒子群算法,神经网络算法和模拟退火算法等.随着DNA自组装技术与DNA计算机研究的展开,一些NP-完全问题以及NP-难问题的计算模型被相继提出.除了传统的DNA分子结构被用作计算材料外,其他的DNA分子结构也被用于分子生物计算,比如质粒DNA分子、分子信标结构以及DNA Tile等.采用DNA纳米折纸结构编码信息,借助于纳米结构之间的粘性末端进行自组装,给出了一种非确定性的图着色模型.通过创建数以亿计的参与计算的DNA纳米折纸结构,该算法可以并行的测试每种可能的着色方案.

求解接点网络问题的DNA算法

利用DNA的二级结构———发卡构形 ,给出了求解接点网络问题的DNA算法 .首先用DNA分子编码接点网络问题 ,然后利用DNA分子的自组装和形成二级结构的能力来求解问题 .算法具有自动化实现计算的特点 ,计算所需的实验操作比Lipton提出的算法少 ,同时计算所需的DNA量也比Lipton提出的算法少 .

有向最短哈密尔顿路问题的DNA算法

首次提出了基于分子生物技术的有向最短哈密尔顿路问题的DNA (deoxyribonucleicacid)算法 ,将顶点、权值用DNA片段编码 ,边的方向通过顶点的编码获得。将这些DNA片段放入溶液中进行生化反应 ,通过基本的生物操作及生物酶完成解的产生及最终解的分离。该算法的创新之处在于权值的设计 ,合理有效地用DNA序列表示权值的大小 ,以便于使用常规的生物分离方法进行最优路径的选择。依据分子生物学的实验方法 ,说明了所提算法是有效和可行的。

基于粘贴模型的图顶点着色问题的DNA算法

为了用生化实验的方法解决图的顶点着色问题,基于粘贴模型的巨大并行性,将着色问题转化为可满足性问题,提出一个基于粘贴模型的DNA算法。通过一个实例给出了操作步骤,并对生化反应过程进行了模拟,得出具体的着色方案,证明了该算法的可行性。

最小顶点覆盖问题的DNA分子算法

最小顶点覆盖问题是找给定图G中覆盖每条边的最小顶点子集,这个问题即是一个著名的NP 完全问题。给出了基于分子生物技术的图的顶点覆盖问题的DNA算法。算法的关键是数学问题到DNA链的映射,对图中的顶点进行恰当的编码,以便于使用常规的生物操作及生物酶完成解的产生及最终解的分离。依据分子生物学的实验方法,提出的算法是有效和可行的。最后指出了该算法的优点、存在问题及下一步的研究方向。

最大匹配问题的分子信标计算模型

目前利用DNA计算求解图与组合优化中探索和开发新的分子结构是研究的一个热点,而分子信标具有结构简单、灵敏度高、易于检测及反应迅速等优点。最大匹配问题是一个著名的NP-完全问题,文章利用分子信标给出最大匹配问题的DNA计算模型。该模型具有编码简单、耗材低、空间利用率高、操作时间短及易于检测等特点,同时拓展了DNA计算解决问题的方法和应用领域。

货物尺寸相同的2维装箱问题的等价类(英文)

在生产与储运领域,把小长方体货物（盒子）装入大长方体箱子是一项重要的工作.本文涉及的问题是:把相同尺寸（a×b×c）的盒子装到一个箱子X×Y×Z中,使所装入箱子的盒子数量为最大.由于某些条件的限止,有时要求货物只能按一个重力方向进行装箱,从而使装箱问题变为把尺寸相同的2维盒子（a×b）填装到一个2维箱子X×Y中.本文讨论当盒子尺寸（a×b包括 b×a）给定,箱子尺寸充分大时,在本文所给的等价意义下,共有多少种互不等价的箱子X×Y.

图着色问题的混合遗传算法

针对图着色对顶点划分的本质特征,提出了基于度的种群初始化方法和交集杂交算子;为加快算法的收敛速度,设计了新的贪婪局部搜索算子来改进杂交产生的后代个体。在此基础上,提出了图着色问题的一种新的混合遗传算法,对10个标准算例的仿真结果表明,新混合遗传算法可以获得问题高质量的解,是一种有潜力的算法。

3TMF排序问题的计算复杂性及分支定界算法

本文研究了TMF排序问题是NP-完全问题.利用混合定界方法,获得了求解该模型的分支定界算法,改进了复合并行机排序模型和装配式流水作业排序模型.

蚁群算法求解多维0/1背包问题

0/1背包问题是一类典型的组合优化问题,并且是NP-完全的问题,研究它具有很重要的意义。本文针对多维0/1背包问题的特点,设计了二进制编码的有向图,使得蚁群算法可以应用到背包问题上。仿真结果表明,该蚁群算法在求解多维0/1背包问题上的是相当出色的。

用混合遗传算法求解图的邻强边着色问题

图的邻强边着色算法是一个NP完全问题。提出了图的邻强迫着色问题的混合遗传算法。在设计交叉、变异方式时,将两点交叉与局部扫描结合起来,避免了种群的退化,从而有利于快速找到最好的解域。根据实际情况,将图的结构性质和迭代次数结合起来,巧妙地设计了算法的终止条件。实验仿真结果表明,混合遗传算法可以获得问题高质量的解,即对图进行邻强边着色所使用的颜色数接近图的邻强边色数。

与装箱(切割)问题有关的数论结果

在生产与储运领域,把(小的)矩形货物装入(大的)矩形箱子是一项重要的工作。本文回答了以下的问题:设有一个长度为X的一维箱子以及设有两种(或三种)长度分别为a,b(或a,b,c)的货物许多,问在什么条件下,可以(或不能)用这些货物(假定货物数量不限)装满箱子?或当两(或三)种货物的长度a,b(或a,b,c)给定时,一维箱子的长度X为多大时,用这两(或三)种货物能或不能装满箱子?不能被这些货物装满的箱子有多少个?