首页 | 本学科首页   官方微博 | 高级检索  
相似文献
 共查询到18条相似文献,搜索用时 93 毫秒
1.
通过生化实验求解割集的方法改进传统的粘贴模型,利用该方法得到最小连接问题的DNA算法.将分离实验分为基于分离板和电泳技术的分离实验.利用分离实验运算的并行性求解割集,最小链接问题的DNA算法所用时间是可判定的,降低了算法所需的时间.  相似文献   

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

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

4.
针对传统单核DNA计算机算法求解Ramsey数时运算效率较低, 求解过程耗时高, 所得结果误差较大的问题, 提出一种基于集合理论的求解Ramsey数算法. 该算法以基于集合理论的MapReduce模型中Phoenix++系统为基础, 设计单核CPU下的圈集对完全图的Ramsey数求解算法并对其实施优化, 优化时进行数据预处理、 高效任务分割和键值对规划等过程, 获取根据Phoenix++系统基于集合理论的并行算法, 采用DNA计算机算法求解Ramsey数, 并对其数值进行验证, 实现Ramsey数的求解. 实验结果表明, 程序处理图像数量随着顶点数的增加而不断增大, 该方法求解Ramsey数的正确性较高, 最大加速比和执行效率较好, 运算性能较强.  相似文献   

5.
针对柔性作业车间调度问题,建立了以最大完工时间最小、机器最大负荷最小、总机器负荷最小为优化目标的多目标优化模型.引入多色集合理论,建立了柔性车间调度问题的多色集合约束模型,提出了基于多色集合约束模型的元胞遗传算法(apolychromatic collection based cellular genetic algorithm,PCGA),以解决遗传算法在求解柔性车间调度问题时表现出的早熟和收敛性不足等问题.用改进的元胞遗传算法求解柔性车间调度的多目标优化算例,并与其它遗传算法进行比较,实验结果表明,基于多色集合的改进元胞遗传算法在求解此问题时更为高效.  相似文献   

6.
基于粘贴和删除系统求解旅行商问题的DNA算法   总被引:1,自引:1,他引:0  
旅行商问题(Traveling Salesman Problem,TSP)是一个典型的NP完全问题.粘贴和删除模型是DNA计算的两个基本计算模型.结合上述两个模型的优点,构造粘贴-删除模型,并利用该模型给出求解旅行商问题一种新的DNA算法.  相似文献   

7.
为有效求解最短路径问题, 避免传统算法计算量大、 求解时间长的问题, 充分发挥DNA(Deoxyribo Nuclec Acid)计算的并行性在求解复杂计算问题的优势, 提出一种基于k-臂分子和粘贴计算求解最短路径问题的DNA计算模型, 阐述了顶点、边及权值的编码方案, 描述了求解最短路径的DNA算法, 经验证, 该模型对求解最短路径问题是有效的。  相似文献   

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

9.
介绍了闭环DNA计算模型及其生化实验,分析了集合覆盖问题及其数学模型.根据任何一个元素至少属于一个集合构成可行集合覆盖的原理,设计了集合覆盖问题闭环DNA算法,该算法首先对集合的0-1决策变量按照0和1的取值、对应的价值系数进行两组DNA编码并形成所有可能解;再用接入实验和删除实验筛选出全部可行解;然后用接入实验得到这些可行解的目标函数值,并用电泳实验得到全部最优解;最后通过检测实验输出所有最优解.首次提出基于电泳技术检测实验以"接入-电泳-删除"为实验顺序,可以检测多种DNA编码.算例说明了算法的有效性.  相似文献   

10.
给出并证明了在DNA计算中处理实数问题的策略,即首先在误差限范围内用有理数集合代替实数集合;再取出与有理数集合一一对应的最小的整数集合.针对赋权匹配问题,给出了基于闭环DNA计算模型的赋权匹配问题算法.该算法首先按边进行三组编码并合成初始闭环DNA;再以相邻两条边为约束条件用删除实验获得所有匹配,并用电泳实验得到所有最大权匹配,最后用检测实验输出最优解.证明了算法的正确性,讨论了算法复杂度,并以一个例子说明了算法的有效性.  相似文献   

11.
Sticker model is one of the basic models in the DNA computer models. This model is coded with sin-gle-double stranded DNA molecules. It has the following advantages that the operations require no strands extension and use no enzymes; What抯 more, the materials are reusable. Therefore, it arouses attention and interest of scientists in many fields. In this paper, we extend and improve the sticker model, which will be definitely beneficial to the construction of DNA computer. This paper is the second part of our series paper, which mainly focuses on the application of sticker model. It mainly consists of the following three sections: the matrix representation of sticker model is first presented; then a brief review of the past research on graph and com-binatorial optimization, such as the minimal set covering problem, the vertex covering problem, Hamiltonian path or cycle problem, the maximal clique problem, the maximal independent problem and the Steiner spanning tree problem, is described; Finally a DNA algorithm for the graph iso-morphic problem based on the sticker model is given.  相似文献   

12.
根据解决最大独立集问题的需要,讨论了简化的粘贴模型,该模型只由单链DNA的存储链和分离板组成.以分离实验为基础提出了批分离实验和生化操作过程,该实验可以快速分离存储链.基于批分离实验设计了最大独立集问题的DNA算法,并给出其生化实现过程:先形成所有顶点子集的初始解空间;接着用批分离实验对每个顶点进行检测,筛选全部满足不相邻要求的顶点子集,从而得到全部独立集;然后通过电泳实验得到全部最大独立集;最后通过检测实验输出实验结果.讨论并证明了算法的正确性和复杂性,算法的操作次数是线性的,通过仿真实验说明了算法的有效性和可行性.  相似文献   

13.
通过一个实例给出了粘贴系统模型的基本定义,讨论了粘贴系统模型的正则文法特性,并从自动机的角度给出了相当于正则文法表达能力的有限自动机模型。  相似文献   

14.
Sticker DNA computer model ——Part Ⅰ: Theory   总被引:5,自引:0,他引:5  
DNAcomputationisanewcomputationalpatternusingDNAmoleculesandsomeenzymesforessentialmaterials,whichisbasedonsomebiochemicalreactions.ThiscomputationalmethodwasfirstlyproposedbyDr.Adlemanin1994[1].ItsprominentadvantageismakingthebestofDNAmoleculeswithenormousmemorygeneticcodes,andimmenseparallelismofbiochemicalreactions.Asaresult,DNAcomputersbasedontheDNAcomputa-tionmodelwillhaveenormousmemorycapacityandegregiousoperationspeed.DNAcomputercanrunwithhighspeed,enormousinformationmemorycapab…  相似文献   

15.
Sticker model is one of the basic models in the DNA computer models. This model is coded with single-double stranded DNA molecules. It has the following advantages that the operations require no strands extension and use no enzymes; What‘s more, the materials are reusable.Therefore it arouses attention and interest of scientists in many fields. In this paper, we will systematically analyze the theories and applications of the model, summarize other scientists‘ contributions in this field, and propose our research results. This paper is the theoretical portion of the sticker model on DNA computer, which includes the introduction of the basic model of sticker computing. Firstly, we systematically introduce the basic theories of classic models about sticker computing; Secondly, we discuss the sticker system which is an abstract computing model based on the sticker model and formal languages; Finally, extend and perfect the model, and present two types of models that are more extensive in the applications and more perfect in the theory than the past models: one is the so-called k-bit sticker model, the other is full-message sticker DNA computing model.  相似文献   

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

17.
The aim of this work is to solve the partitioning problem, the most canonical NP-complete problem containing numerical parameters, within the sticker model of DNA computing. We firstly design a parallel program for addition, and then give a program to calculate the subset sums of a set. At last, a program for partitioning is given, which contains the former programs. Furthermore, the correctness of each program is proved in this paper.  相似文献   

18.
高清春 《科学技术与工程》2013,13(2):457-459,490
杜813-H203井是辽河油田在超稠油油藏所钻的一口浅水平井。由于该井水平段较长且岩性疏松,井壁掉块严重,井眼多呈台阶状,加之岩屑堆积,增大了后续作业遇卡的风险。为解决测井及后期下套管遇阻问题,根据超稠油油藏的特点采用水平井扩眼技术,清除岩屑床,扩大、修正了原井眼。实测结果表明:该水平段摩擦阻力高于该地层正常钻进水平井的两倍以上,严重影响后续作业。扩眼后整个测井和下套管安全顺利,有效解决了后期作业的复杂情况,提高了固井质量,延长了油井使用寿命。  相似文献   

设为首页 | 免责声明 | 关于勤云 | 加入收藏

Copyright©北京勤云科技发展有限公司  京ICP备09084417号