最大团问题的三链DNA计算模型

本文研究利用三链DNA求解最大团问题。首先将最大团问题中的顶点编码为DNA片段,进行生化反应,组合成所有可能的情况,然后利用三链模型对解进行筛选,最终得到图的最大团。该模型降低了编码的复杂度,提高了检测效率,其他的NP(Non-deterministic Polynomial)问题也可用此方法来求解。     

最大匹配问题的三链DNA计算模型

三螺旋结构的DNA链具有稳定性,在一定条件下易分解等特点,因此得到的三链模型具有错解率低的优点。利用三链模型来讨论最大匹配问题,拓展了DNA计算解决问题的方法和应用领域。     

基于DNA链置换的可满足性问题的计算模型

可满足性问题是经典的NP完全问题之一.本文建立了一个基于DNA链置换的可满足性问题的计算模型,可满足性问题的约束条件被映射成计算模型上的荧光个数,将可满足性问题中变量的两种取值(0和1)分别设计成不同的DNA链,通过DNA链置换反应,最后观察反应后的计算模型上荧光个数找出可满足性问题的可行解.该模型具有操作简单,结果便...     

基于进化规划算法的背包问题求解研究

背包问题是一个具有较强应用价值的NP完全问题.如何设计求解此类问题的算法,则具有很强的实用价值和理论意义.目前已有很多的求解方法,但背包问题并没有完全解决.本文在启发式算法的理论基础上,改进了进化规划算法求解背包问题,此方法简单通用、易于操作.数值实验表明该方法具有较高的准确率,能较快的收敛到全局最优点.     

图的k着色问题的DNA计算模型

DNA计算是一种新的并行计算模式,在解决NP完全问题等方面具有很大的优越性．利用DNA计算的计算特性给出了一个图的k着色问题的DNA计算模型,该算法最多需要3kn（n-1）/2＋6个生物操作即可求出图的色数及相应的着色模式．     

三维DNA自组装在多维背包问题中的应用研究

利用DNA自组装执行计算的思想已从实验上被证明了其可行性．已有多种理论模型被提出用以解决各种NP问题．基于DNA Tile自组装模型理论在二维下的扩展,本文设计了可以实现这一算法的三维DNA Tile组装系统,提出了一种用于解决多维背包问题的三维DNA自组装模型．该模型可以非确定性的输出可行性解决方案．分析表明系统可以在线性组装步骤内完成计算,所需的Tile种类数与问题维数无关．为探索三维DNA自组装的计算能力进行了一次有意义的尝试．     

0-1整数规划问题的DNA四面体步行者计算模型

DNA折纸术是一种新型的自组装方法,广泛应用于DNA计算中.基于DNA折纸术设计了一个DNA四面体步行者,并将DNA四面体步行者应用于求解0-1整数规划问题.通过DNA四面体步行者的行走,来找出所有可能解.最后,通过DNA四面体步行者所携带的纳米金颗粒的个数来判断是否是0-1整数规划问题的可行解.该模型求解错误率低,具...     

动态规划求解0-1背包问题的教学探索

针对动态规划在0—1背包问题中求解最优值时的教学难度,结合教学过程和特点,对计算最优值的算法进行了改进,在与最优值递归公式保持一致的情况下简化了迭代过程,消除算法技巧,增加了算法的规范性和连贯性,收到了理想的教学效果。     

基于遗传算法求解0—1背包问题的算法探讨

0-1背包问题是一类典型的组合优化问题,并且是NP完全问题,具有重要的研究意义.介绍了贪婪算法和基本遗传算法求解背包问题的设计思想,提出了基于贪婪算法的混合遗传算法求解0-1背包问题.实验结果表明改进的遗传算法有更好的近似解.     

基于遗传算法求解背包问题的算法探讨

将遗传算法应用于背包问题,利用遗传算法的求解思想,对传统的背包问题进行了详细的分析,按照遗传算法的基本结构设计了编码,并通过实例验证了遗传算法用于解决背包问题的可行性和有效性.     

DNA computing model based on lab-on-a-chip and its application on solving the timetabling problem

The essential characteristic of DNA computation is its massive parallelism in obtaining and managing information. With the develop- ment of molecular biology technique, the field of DNA computation has made a great progress. By using an advanced biochip technique, laboratory-on-a-chip, a new DNA computing model is presented in the paper to solve a simple timetabling problem, which is a special version of the optimization problems. It also plays an important role in education and other industries. With a simulated biological experiment, the result snggested that DNA comnutation with lab-on-a-chin has the notential to solve a real comtplex timetabling problem.     

多维0-1背包问题的新型近似解法

运用属性论的转换程度函数,结合贪婪算法和核问题的研究思路提出了多维0-1背包问题的一种新型近似解法。该算法对生产实践中的四大类背包实例都有很快的收敛速度。特别是常规方法难以解决的最大子集和实例及强相关实例,算法能在一个很好的时间范围内给出近似度为99.7%的近似满意解甚至是最优解。     

DNA computing model based on lab-on-a-chip and its application to solving the timetabling problem

The essential characteristic of DNA computation is its massive parallelism in obtaining and managing information.With the development of molecular biology technique,the field of DNA computation has made a great progress.By using an advanced biochip technique,laboratory-on-a-chip,a new DNA computing model is presented in the paper to solve a simple timetabling problem,which is a special version ofthe optimization problems.It also plays an important role in education and other industries.With a simulated biological experiment,the result suggested that DNA computation with lab-on-a-chip has the potential to solve a real complex timetabling problem.     

具有多父代重组的遗传算法解0-1背包问题

遗传算法的创始人最初是从自然界获取灵感的,但是后来的遗传算法的研究者也试图将生物界不存在的特征引入遗传算法,多父代重组(或称为N父代重组,N>2)就是其中的一种。有文献显示这种机制在解很多不同的问题时都能有较好的效果。本文用几种多父代重组方法(包括一种新的面向特定问题的方法)解0-1背包问题,结果显示多父代重组确实有较好的性能。     

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

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

量子免疫算法及在0-1背包问题中的应用

将免疫算法的免疫算子思想引入到量子遗传算法中,提出了改进的算法:量子免疫算法。算法在保持量子遗传算法优点的同时,提高了算法的全局收敛性。并将此算法应用在0-1背包问题中,仿真结果表明,此改进算法具有良好的性能。     

0-1背包问题的非线性降维近似算法

求解0-1背包问题的精确算法不能在较短时间内求解大规模0-1背包问题,使其实用性受到限制.针对该问题,给出求解0-1背包问题的非线性降维算法,并进行了数值实验,验证了算法的有效性.该算法属于近似算法,相对其他一些近似算法,计算结果更为精确.     

一类可分离的非线性0-1背包问题的分枝定界算法

构造出了一类可分离非线性0-1背包问题的分枝定界算法．分枝的过程是酱通的0-1变量分枝，用简单的取整启发式法确定更好的可行解；而在每个分枝结点处用线性松弛技术确定了它的子问题的一个线性规划松弛逼近。由此得到最优值的一个下界．数值结果表明所提出的算法是有效的．可以求解中等规模的问题．