DNA计算方法在求解NP完全问题中的应用

DNA计算是应用分子生物技术进行计算的新方法.本文主要介绍了DNA计算的基本思想及解决NP完全问题的DNA模型,讨论了目前DNA计算存在的问题和今后的发展方向.     

DNA计算方法在求解NP完全问题中的应用

DNA计算是应用分子生物技术进行计算的新方法．本文主要介绍了DNA计算的基本思想及解决NP完全问题的DNA模型，讨论了目前DNA计算存在的问题和今后的发展方向．     

基于微流控技术图顶点着色问题的DNA计算模型

为减少DNA计算中的人为操作,实现对生化操作的精确控制,设计了一种基于微流控技术求解图顶点着色问题的微流控DNA计算模型。通过温度来控制微反应器中DNA链库与磁珠探针的杂交与变性,并利用不同电极间的电位差来驱动DNA分子在微通道内移动以实现整个计算过程。分析表明,采用本文模型可以自动化地求解任意一个图顶点着色问题,提高了DNA计算的可靠性。     

基于 DNA 自组装的全错位排列问题模型

针对全错位排列这类NP 完全问题,提出了一种基于DNA 自组装的全错位排列问题计算模型。该模型利用了DNA分子间的自组装能力,在具体操作时只用到凝胶电泳技术,在一定程度上减少了实验误差。     

装配序列规划的DNA计算及其仿真

为了解决装配序列规划中的NP问题,引入DNA计算的方法进行最优装配序列求解.依据信息论中信息熵的概念,采用信息分解转换法提取装配体信息,提出用装配信息熵评价零件之间的关联,将装配序列规划问题转化为求最小Hamilton回路问题.研究了DNA计算理论,并给出了利用DNA计算求解最优装配序列的步骤.设计了DNA计算的仿真模...     

基于表面的DNA计算模型解决排课表问题

考虑到教师、班级以及课时等的不同要求,复杂的排课表问题就属于NP问题。为了使排课表问题更加简捷,方便,提出了基于微量点样技术的表面DNA计算模型。在实验中,通过对每次结果进行记录和比较,得到了满足问题要求的可行解。不需要改变问题的初始点列,适于研究规模较大的问题。     

基于分子生物技术的DNA计算系统

DNA计算是一种应用分子生物技术进行计算的新方法,DNA计算的2个主要特点是高度并行性和巨大的信息存储容量。为解决 DNA计算初始化过程存在的问题,提出了数据初始化模型,保证了初始数据的完整性,减少了计算过程中参与筛选的 DNA链的数量,提高了计算精度。针对生物实验反应时间较长、活性DNA材料成本高的现状,开发了DNA计算系统,通过仿真实验解决了哈密尔顿问题。     

基于自组装纳米颗粒的顶点着色问题的DNA计算模型

自组装纳米颗粒由于其特殊的结构,具有较好的稳定性,广泛应用于DNA计算中,使用DNA自组装模型可以有效减少运算的复杂度。文章利用自组装纳米金属颗粒求解了图的顶点着色问题。首先,将图的顶点进行自组装设计;其次,根据顶点构造相应的连接探针,二者通过碱基互补配对自动生成初始数据池;最后,利用特殊结构的删除探针对数据池中的方案进行筛选,结合凝胶电泳得到满足条件的解。该模型无需对DNA片段进行编码,操作简单,在检测解时无需酶的参与,降低了复杂度,提高了运算效率。     

分子计算机的诞生与现状

介绍了计算机领域的一项最新成果－分子计算机，分子计算机利用脱氧核糖核酸（DNA）来进行计算，腺嘌呤，胞密啶，胸腺密啶（核苷酸0在计算中起了重要的作用，使用限制内切酶，接合酶，移酶，外切核酸酶，修饰酶来实现计算所需要的各种操作，介绍了分子计算机完成的第1个计算－解哈密顿通路问题的方法，用这种方法使NP完全问题在短的时间内就得到解决。     

基于虚拟技术的数据库I/O解决方案研究

探讨了数据库系统的主要性能瓶颈——I/O问题和虚拟技术及其应用,将虚拟技术引入数据库I/O解决方案中,建立了基于虚拟技术的数据库I/O解决方案模型,通过实验和对实验结果进行测试、对比、分析,证实了虚拟技术解决数据库I/O问题的可行性.研究表明,虚拟技术是解决数据库I/O问题的一种较好的方法.     

求解最短路径问题的DNA动态规划算法

最短路径问题是一个组合优化问题,许多交通运输、工程、管理等实际问题可转化为最短路径问题进行求解。文中利用DNA计算的并行计算模式,给出一个求解最短路径问题的DNA动态规划算法,该算法最多需要7n-11个生物操作。     

基于蚁群算法的TSP问题求解

TSP问题是典型的NP—hard组合优化问题,蚁群算法是一种求解此类问题的优化算法,通过模拟蚂蚁觅食行为来解决NP问题。文章使用蚁群算法求解TSP问题,并结合TSP问题的特点选择了一种合适的蚁群更新策略。     

Two personification strategies for solving circles packing problem

Two personification strategies are presented, which yield a highly efficient and practical algorithm for solving one of the NP hard problems——circles packing problem on the basis of the quasi-physical algorithm. A very clever polynomial time complexity degree approximate algorithm for solving this problem has been reported by Dorit S.Hochbaum and Wolfgang Maass in J. ACM. Their algorithm is extremely thorough-going and of great theoretical significance. But, just as they pointed out, their algorithm is feasible only in conception and even for examples frequently encountered in everyday life and of small scale, it is the case more often than not that up to a million years would be needed to perform calculations with this algorithm. It is suggested toward the end of their paper that a heuristic algorithm of higher practical effectiveness should be sought out. A direct response to their suggestion is intented to provide.     

Realization and Performance Analysis of Sequence Cipher Based on NP Problem

0~aeONSeqUencecipherassumesgoodcharactersbyencipheringplaintextShitforbit.Asacounterpartofblockcipher,tLhetimed}vidricsofseqUenceciphergeneratorensuresthatidenticalplaintextScanbetransformedintodifferentciphertextS,therebyenlarginguncertainty'ofciphertextStoinvalidPe~.Ingeneral,aseqUenceciphercanbedescribedbyanabstractmodelcalleddefinitestatesmachine,andweciteitasfollow,[11.Where,FisthekeygeneratingfLinction,Cisthestate~fearingfunction,s,Ii=0,l,2,..'isthestateparameter,k,isgivenastheinit…     

基于约束满足问题的ILOG技术的应用

约束满足问题是求解复杂调度和资源分配问题的有效方法.在综述了约束满足问题建模和搜索策略理论的基础上,引出了有效解决约束满足问题的优化工具--ILOG组件.然后介绍了ILOG组件在对约束满足问题建模和求解方面的具体应用,并给出了应用ILOG解决工序安排问题的实例.