图3-着色问题的O链数DNA计算机算法

随着DNA计算的不断发展,如何克服穷举算法带来的指数爆炸问题已成为DNA计算领域的重要研究目标之一.为减少图3-着色问题DNA计算机算法中的DNA链数,本文将Adleman-Lipton模型生物操作与粘贴模型解空间相结合的DNA计算模型进行扩展,通过设计顶点着色器、稀疏图/稠密图搜索器,提出一种用于求解图3-着色问题的DNA计算模型与算法.将本算法与同类算法对比分析表明:本算法在保持多项式操作时间的条件下,将求解n个顶点的图3-着色问题所需DNA分子链数从O(3ⁿ)减少至O(2ⁿ),改进了3-着色问题同类文献的研究结果.     

基于FPGA的图着色问题求解

图着色问题是在满足相邻顶点不能分配相同颜色且颜色数最少的约束条件下,将图的顶点划分为不相交的集合,且每个集合中的顶点分配相同的颜色。由于图着色问题属于NP-完全问题,求解图着色问题的算法复杂度会随顶点个数的增加呈指数级增长。当顶点个数非常大时,通用处理器求解图着色问题的性能将会显著下降。因此,该文基于现场可编程逻辑门阵列(FPGA)实现求解图着色算法的专用硬件加速器。首先依据FPGA模块化的设计思路提出并实现了基于回溯法的图着色问题求解的硬件架构;其次分析了FPGA内部消耗资源与图着色顶点数之间的关系;最后利用通用异步收发传输器协议实现了通用处理器与FPGA的通信。实验结果表明,相比于在通用处理器上利用软件实现图着色算法,基于FPGA所实现的图着色算法运行时间减少了一个数量级。除此之外,FPGA内部消耗资源数与顶点个数呈线性关系,且每次迭代时FPGA运算所消耗的时间与顶点个数无关。     

基于自组装的N皇后问题DNA计算算法

N皇后问题是理论计算机科学中一个经典的NP难问题.自Adleman首次运用DNA计算来解决NP问题以来,DNA计算已成为计算机科学的研究热点之一,现有N皇后问题的DNA计算机算法多基于粘贴和剪接模型,存在生化操作复杂度和实验误差较高等问题.本文提出了一种基于DNA自组装模型来求解N皇后问题的DNA计算方法.算法通过减少实验操作步骤数,降低了生化解的错误率.算法使用的tiles分子块种类为O（n²）,生化操作复杂性为O（1）,其中n为皇后的个数.与求解N皇后问题的其它DNA算法的对比分析表明,本算法可提高生化解的准确性,降低算法生化实验的复杂度,具有良好的易操作性.     

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

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

一种基于分治的三维匹配问题DNA计算算法

 本文基于Aldeman-Lipton模型的生物操作与粘贴模型的解空间,提出一种三维匹配问题的DNA计算新模型;同时基于此模型和传统计算机中分治策略,提出一种求解三维匹配问题的DNA计算新算法.将提出的算法与已有文献结论的对比分析表明:本算法将穷举算法中的DNA链数从O(2ⁿ)减少至O(2^n/2)≈O(1.414ⁿ),同时生物操作数由O(n²)减少至O(15n+30q),测试试管数由所需的O(n)减少至O(1),最大链长由O(15n+45q)减少至O(15n/2+45q).因此,本算法理论上在试管级生化反应条件下能将求解三维匹配问题的规模从67(2⁶⁷≈10²²)提高到134(67×2=134).同时,与传统的穷举搜索算法相比,该算法具有高效的空间利用率及容错技术的优点.     

一种基于图论的RFID防冲突建模与优化方法

针对RFID系统的超高频段、多读写器的静态拓扑结构,研究了读写器冲突问题,并提出了一种图论的图着色算法与遗传算法相结合的防冲突干扰方法.该静态预定义算法对读写器冲突建立图论模型,将读写器时隙分配问题转化为图论模型的K-顶点着色问题,优化遗传算法并用于求解图的K-顶点着色问题,求得最小时隙数和最优时隙分配方案.最后将算法应用于算例.实验结果表明该方法可行、实用,能够有效地防止读写器冲突干扰.     

基于DNA折纸术求解图的顶点着色问题的方法

该文基于DNA折纸术,设计了一个通过DNA折纸结构的自组装求解图的顶点着色问题的方法。利用DNA折纸术可以构建出具有特定形状的DNA折纸结构。这些结构可以用来编码图的顶点和边,由于这些结构具有粘性末端,因此可以通过特异的分子杂交组装成为代表了不同的图的顶点着色方案的高级结构。利用DNA-纳米颗粒共聚体的属性和电泳等实验方法,可以筛选出正确的符合条件的图的顶点着色方案。该方法是一种高度并行的方法,可以极大地降低求解图的顶点着色问题的复杂度。     

基于DNA折纸术求解图的顶点着色问题的方法

该文基于DNA折纸术,设计了一个通过DNA折纸结构的自组装求解图的顶点着色问题的方法.利用DNA折纸术可以构建出具有特定形状的DNA折纸结构.这些结构可以用来编码图的顶点和边,由于这些结构具有粘性末端,因此可以通过特异的分子杂交组装成为代表了不同的图的顶点着色方案的高级结构.利用DNA-纳米颗粒共聚体的属性和电泳等实验方法,可以筛选出正确的符合条件的图的顶点着色方案.该方法是一种高度并行的方法,可以极大地降低求解图的顶点着色问题的复杂度.     

基于Tile自组装模型的最大匹配问题算法研究

Tile自组装模型作为一种重要的DNA计算模型,在解决NP问题时展现出了巨大优势.文中针对现有最大匹配问题DNA计算算法实验操作复杂,错误率高的缺点,提出了一种基于Tile自组装模型的最大匹配问题新算法.算法所需的Tile分子种类为O(mn),所需生物操作数为O(1),计算时间为O(m),计算空间复杂度为O(mn)(其中m为边数,n为顶点数,且O(m)=O(n²)).与现有的最大匹配问题DNA计算算法相比,本算法不仅可靠性更好,而且更具可操作性.     

图的最大权团的DNA计算

给定顶点赋权的无向图,图的最大权团问题是寻找每个顶点都相邻的顶点子集(团)具有最大权.这个问题是寻找无权图的最大团问题的推广.图的最大团和最大权团都是著名的NP-完全问题,没有非常有效的算法.1994年Adleman博士首先提出用DNA计算解决NP-完全问题,使得NP-完全问题的求解可能得到解决.本文给出了基于质粒技术的无向图的最大权团问题的DNA算法,依据Head T等的实验手段,本文提出的算法是有效并且可行的.     

最小顶点覆盖问题的改进粘贴模型

DNA计算是一种模拟生物分子DNA的结构并借助于分子生物技术进行计算的新方法。它开创了以化学反应作为计算工具的先例,具有广阔的应用前景。本文简单回顾了DNA计算的发展,并简要介绍了分子计算的一种模型粘贴模型。最后我们利用粘贴模型的基本原理,运用荧光标记技术,提出了最小顶点覆盖问题的表面技术解决方案。     

0-1规划问题的DNA计算

DNA计算是解决一类难以计算问题的一种新方法,这种计算随着问题的增大可以呈指数增长。迄今为止,许多研究成果已经成功地提高了它的性能和增加了它的可行性,该文提出了在基于表面的DNA计算中采用了荧光标记策略,解决简单的0-1规划问题的一种理论方案,尝试了DNA计算在规划问题中的应用。这种方法具有编码简单、耗材底、操作时间短、技术先进等优点。     

Ménage问题的一种粘贴DNA算法

 解决图论与排列组合难题是DNA计算领域的研究目标之一.为了使用分子生物方法解决Ménage问题,本文给出了Ménage问题的数学模型;并对解决该问题的难点进行了分析,提出一种解决方案,改进了该问题的数学模型;提出一种解决Ménage问题的粘贴DNA算法并简要分析了该算法的复杂度.为了提高效率,引入广义分离和广义多级分离操作;通过一个实例给出了实验操作步骤,对实验进行了模拟.     

TSP的DNA算法

由于Adleman和Lipton的开创性工作,最近DNA计算引起了人们的极大兴趣,他们提出的分子算法解决了图形的表示方法,但是没有给出如何处理图中节点的弧线的信息。本文的目的是通过提出在图中城市间的距离用简单的弧线代表,延伸了Adleman和Lipton提出的基本的分子算法。并提出只有当算法步骤由当前的需要人工干预被可执行的可在试管中操作的DNA链代替,解决计算难题的真正可行DNA计算可以实现。该算法的创新之处在于表示城市和路径的DNA链长度的设计,能使我们在合理的范围内寻找旅行商问题的解,较大地简化了问题的复杂度。     

解无约束极大极小问题的非对称神经网络算法

本文构造了一种新的非对称神经网络模型，用于求解极大极小无约束优化问题，并证明了非对称线性神经网络和非线性神经网络是整体Ｌｙａｐｕｎｏｖ稳定的，且收敛于对应的Ｌａｇｒａｎｇｅ方程的稳定点，计算机模拟的结果表明此方法是可行的，且具有良好的整体收敛性。