基于改进的粘贴模型求解图最大独立集的DNA算法

改进的DNA粘贴模型在解决SAT问题时所需的寡核苷酸片段数量有显著降低,对改进的粘贴模型做了进一步的改进,建立了图最大独立集的一种改进的DNA粘贴模型.首先将图的独立集问题转化为可满足性问题,然后利用本文改进的粘贴模型给出了图的最大独立集的DNA算法.最后通过一个实例给出算法实现并求出了最大独立集.     

基于DNA自组装模型解决图的最大独立集问题

为了寻找图的最大独立集问题,先利用DNA自组装模型解决可满足性问题,再把最大独立集问题转化为可满足性问题,从而解决最大独立集问题。整个过程只用到凝胶电泳操作,在很大程度上减少了误差。     

最大独立集问题的表面计算模型

DNA计算是解决一类难于计算问题的一种新方法,最大独立集问题是一个著名的NP完全问题,最大团问题及最小覆盖问题等价于最大独立集问题。本文中,我们尝试将最大独立集转化为0-1规化问题,利用0-1规化问题的表面计算模型求解最大独立集。本文充分说明了NP-完全问题可以相互转化的性质。     

基于DNA计算的最大权团问题设计

介绍了最大团和最大权团的概念和国内外学者运用DNA计算解决最大团的研究成果;结合前人运用质粒、二进制、粘贴模型等方式进行DNA计算操作的原理,设计了新的用于解决最大权团问题的算法步骤,大大提高了算法效率,实现了最大团和最大权团的同步求解,对市场分析、方案选择等领域有一定的意义。     

基于闭环DNA的边着色问题DNA算法

提出一种新的DNA计算模型——闭环DNA计算模型。引进了批删除实验。讨论了其实现过程;提出并证明了边着色问题的基本定理,设计并实现了闭环DNA计算算法．该算法将边的DNA编码分为两部分,一部分存储边和色位置的二维数据,另一部分存储色号值;在DNA计算的主体部分用批删除实验得到全部正常的边着色,并通过电泳实验和检测实验获得χ′^-正常边着色．举例说明了算法的有效性和可行性．     

寻找最大独立集的算法

提出两种基于贪婪思想的局部搜索算法寻找给定图的最大独立集,通过测试第二种算法在图密度小时更优与第一种算法.由于局部搜索算法的缺陷,修改邻域函数与顶点的选择是进一步研究的问题;考虑到算法的有效性,时间复杂度和近似算法的比较也是值得进一步研究的方向.     

求解最大完全子图的一种DNA算法

最大完全子图是图论中一个重要的问题。粘贴和删除模型是DNA计算的两个基本计算模型。利用改进的粘贴和删除模型给出求解最大完全子图的DNA算法。     

图的最大独立集问题的模拟退火算法

给出了一种具有全局优化特性的改进的模拟退火算法 ,建立了图的最大独立集的模拟退火模型 ,研究了扰动的形成和算法参数的选取 ,并用计算机进行模拟 ,结果表明该算法是有效的     

地图着色问题的粘贴DNA算法

提出多级分离的概念,给出一个多级分离装置的模型,并介绍粘贴模型中的多级分离操作、将地图着色问题转化为可满足性问题、基于粘贴模型的巨大并行性及多级分离的优势,提出解决该问题的粘贴DNA算法。通过一个实例给出实验操作步骤,并对生化反应过程进行模拟,得出具体的着色方案,从而证明了该多级分离装置的有效性以及该算法的可行性。     

最小生成树DNA算法

为了改进粘贴模型,提出了用生化实验实现求解割集的计算方法,并基于该方法给出了最小生成树DNA算法.首次将分离实验扩展为基于分离板的分离实验和基于电泳技术的分离实验,所提出的最小生成树DNA算法打破了DNA计算的计算模式——用求解割集的最小边的方法逐步产生最小生成树.用该方法求解割集利用了分离实验运算的高度并行性,最小生成树DNA算法的时间复杂度是线性的,从而降低了算法的时间复杂度.     

一种求解最大独立集的自学习进化算法

为了求解最大独立集问题,通过对求解最大团问题EA/G算法的分析,从初始解选取、种群的构成、遗传策略等方面对EA/G算法进行了改进,提出了自学习进化算法,并在DIMACS基准图上进行了大量的实验.实验结果表明,该算法运算结果比EA/G算法所求结果有很好的改善.     

基于串行最大独立集的连通支配集构造及分析

针对传感器网络最大独立集的构造方法中并行构造算法生成的连通支配集尺寸没有明确的上界且难以确定边界节点的问题,在串行最大独立集构造算法的基础上,提出了基于权重和时序的触发式连通支配集构造算法.仿真结果表明:该算法无需构造生成树,降低了计算时延和通信开销;此外,由于最大独立集节点存在时间上的先后关系,因而使得边界节点的数量显著减少,最终求得的连通支配集存在明确的上界.     

A DNA length reducing computing model for maximum independent set problem

In this paper, a new molecular computing model is developed to solve the maximum independent set problem, based on the method of DNA length reducing. To solve the maximum independent set problem with n-vertices and m-edges, the time complexity is O(n+m). With the enlargement of the problem scale, the numbers of the required tubes will increase linearly. Two important methods in this experiment are single strand DNA (ssDNA) circularization and DNA length reducing. In addition, using reverse polymerase chain reaction (PCR) and circligase, the structure of DNA molecules is changed in each computing step, transforming from linear double strand DNA (dsDNA) to linear ssDNA and circular ssDNA. Using the circular DNA structure, the recombina-tion among DNA molecules is avoided. To verify this computing model, a small maximum independent set problem was solved.     

图顶点着色问题的质粒DNA计算

图的着色问题是著名的NP问题,有着重要的实际意义。比如通讯系统的频道分配、考试排考场问题等方面有直接应用。图的着色问题采用DNA计算方法很多,有表面DNA计算,粘贴DNA计算。本文提出质粒DNA计算,首先把顶点着色问题转化为求最大独立集问题,然后给出了图顶点着色问题的质粒DNA分子生物实验,利用限制性内切酶的特性切割有边相连的顶点,得到最大独立集,在试验中特别引入了一个备用试管,最后给出一个具体的实例。实例给出具体的着色方案,证明了该质粒DNA算法有效并且是可行的。     

图的最小顶点覆盖的粘贴DNA计算模型

本文在对经典粘贴模型以及全信息化的粘贴DNA计算模型的基本方法进行充分讨论的基础上,提出一种用粘贴DNA计算模型解决图的最小顶点覆盖问题的新方案,将数学问题的求解同并行生物操作有效结合.     

基于DNA粘贴模型求解最小集合覆盖问题

运用DNA计算模式中基于粘贴运算的粘贴模型求解最小集合覆盖问题.在粘贴模型中,用存储复合体来表示子集,并利用粘贴运算的巨大并行性,可以有效地求解最小集合覆盖问题.举例说明了基于DNA粘贴模型求解最小集合覆盖问题的过程.     

M2M业务批量到达排队系统性能分析

针对M2M(Machine to Machine)业务的大规模应用给当前移动通信网络的QoS带来的冲击和影响问题,采用IBP(Interrupt Bernoulli Process)建模M2M业务的到达过程,业务以批量的形式到达,建立并求解了离散时间系统排队模型IBP/Geom/1/K.区别于传统的IBP模型,该模型每次到达的不是一个,而是一批.采用具有不同突发度的数学模型表征M2M业务每批到达的数量,在概率空间上求解队长的稳态概率,进而得到系统的吞吐量和丢包率等性能指标,并与相同排队强度下M2M业务单个到达时的性能进行对比.实验结果表明,每批到达包数的突发度越大,系统的性能越差;在相同排队强