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

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

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

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

基于DNA折纸基底的与非门计算模型

与非门(NAND)的本质是与门(AND)和非门(NOT)的叠加,先进行与运算,再进行非运算,它是建立DNA计算机的基础。为了实现与非门的计算,该文在DNA折纸基底上建立了一个与非门计算模型,逻辑值的输入是通过在DNA折纸基底上发生有向的杂交链式反应(HCR)来完成的,输入链先经过与门区域再经过非门区域,最后通过DNA折纸基底上是否还保留纳米金颗粒来显示计算结果的真假。利用Visual DSD对该计算模型进行仿真模拟,显示该计算模型具有较好的可行性。     

DNA-纳米颗粒共聚体在最大匹配问题中的应用

该文提出一种DNA计算模型,利用DNA-纳米金颗粒共聚体的自组装来解决图论中的一个NP完全问题——最大匹配问题。根据模型该文设计了能够基于一个具体的图进行自组装的特殊的DNA-纳米金颗粒共聚体,然后利用一系列的实验方法来获得最终的解。这种生物化学算法可以极大地降低求解最大匹配问题的复杂度,这将为DNA自组装计算模型提供一种切实可行的方法。     

DNA-纳米颗粒共聚体在最大匹配问题中的应用

该文提出一种DNA计算模型,利用DNA-纳米金颗粒共聚体的自组装来解决图论中的一个NP完全问题——最大匹配问题.根据模型该文设计了能够基于一个具体的图进行自组装的特殊的DNA-纳米金颗粒共聚体,然后利用一系列的实验方法来获得最终的解.这种生物化学算法可以极大地降低求解最大匹配问题的复杂度,这将为DNA自组装计算模型提供一种切实可行的方法.     

DNA计算机的研究现状

为了帮助研究者进一步认识DNA计算机的研究现状,通过查找文献法和归纳法对DNA计算机的研究现状进行了梳理。首先介绍了DNA计算机的原理基础和研制过程,然后综述了DNA计算机的主要研究成果及应用,分析了DNA计算机目前面临的主要困难。特别讨论了DNA计算机中的数据结构与自组装技术的研究情况。最后得到DNA计算机的研究已取得一些进展,但还面临许多困难和技术挑战的结论。     

基于FPGA的图着色问题求解

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

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

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

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

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

基于Hopfield网络的图的着色算法

应用Ｈｏｐｆｉｅｌｄ网络模型，系统地研究了图的正常ｋ－顶点着色，正常ｋ－边着色以及正常ｋ－全着色的具体算法，建立了相应的数学理论，改进了此领域内的某些工作。     

A Tree Based Novel Approach for Graph Coloring Problem Using Maximal Independent Set

Wireless Personal Communications - Graph coloring problem is a famous NP-complete problem and there exist several methods which have been projected to resolve this issue. For a graph colouring...     

基于图着色的事务调度算法的设计

将处理对象抽象转换为事务,对于事务的调度问题提出了基于图着色思想的算法.将事务以及之间的联系建立事务调度模型,同时等价地转化为图着色问题,通过对图中的顶点着色来实现具有冲突的事务的调度.与一般图着色处理方式不同的是,本算法思想采用了对节点进行着色的思想来实现事务调度.基于图着色的算法的设计与实现使多事务多冲突问题得到解决、并且最大程度满足事务执行所需各元素的特殊要求.     

用自适应图着色算法解决RFID阅读器冲突问题

建立了阅读器网络的图模型,阐述了阅读器网络拓扑结构固定和可随机改变情况下对解决阅读器冲突问题的不同要求。对于动态阅读器网络应用中的阅读器冲突问题,基于图着色方法提出了一种自适应分布式的颜色选择算法,这种算法能降低相邻阅读器冲突概率,并且使获得特定百分率的成功传输所需的总时隙数最少。     

基于图着色的大规模无人机群三维网络资源分配算法

为了解决大规模无人机集群组网中的网络资源有限、有效分配网络资源难度大的问题,本文针对任意对无人机收发节点构成的通信网络,联合考虑时域、频域、空域,提出了一种基于图着色的三维网络资源分配算法。具体的,本文利用方向回溯阵列天线在传统时频二维网络资源划分的基础上开辟空间维度,得到三维网络资源划分问题。为了解决该三维资源分配问题,本文首先将其建模为图着色问题,然后提出了启发式和贪婪式两种复杂度不同、适应场景也不同的图着色算法,并进一步设计了由着色结果到网络资源分配方案的映射算法。仿真结果验证了所提方法的有效性,相较于传统时分多址接入和时频二维资源分配而言,大大提高了吞吐量和传包成功率。      

A Graph Coloring Based TDMA Scheduling Algorithm for Wireless Sensor Networks

Wireless sensor networks should provide with valuable service, which is called service-oriented requirement. To meet this need, a novel distributed graph coloring based time division multiple access scheduling algorithm (GCSA), considering real-time performance for clustering-based sensor network, is proposed in this paper, to determine the smallest length of conflict-free assignment of timeslots for intra-cluster transmissions. GCSA involves two phases. In coloring phase, networks are modeled using graph theory, and a distributed vertex coloring algorithm, which is a distance-2 coloring algorithm and can get colors near to $(\updelta +1)$ , is proposed to assign a color to each node in the network. Then, in scheduling phase, each independent set is mapped to a unique timeslot according to the set’s priority which is obtained by considering network structure. The experimental results indicate that GCSA can significantly decrease intra-cluster delay and increase intra-cluster throughput, which satisfies real-time performance as well as communication reliability.     

基于有序划分编码的图着色算法

 针对整数编码的冗余性,提出了求解图着色问题的一种新的编码方式.采用有序划分编码问题的解,编码后的个体具有与问题的潜在解一一对应的特点.与整数编码相比,新的编码避免了冗余性,将搜索空间缩小了k!倍.对5个标准图着色问题的仿真结果表明,基于有序划分编码的新算法是求解图着色问题的一种有效的算法.     

基于顺序图着色方法的地面数字电视频率指配

介绍了频率指配的数学模型和顺序图着色方法,并举例说明了顺序图着色方法在地面电视频率指配规划中的实际应用.