基于质粒模型的DNA计算机算法求解背包问题  

Solving knapsack problem based on plasmid Model DNA computer algorithm

作　　者：陈改霞 耿瑞焕 

机构地区：[1]鹤壁汽车工程职业学院,河南鹤壁458030

出　　处：《佳木斯职业学院学报》2014年第10期159-,162,共2页Journal of Jiamusi Vocational Institute

摘　　要：本研究在穷举法的背包策略的基础上借鉴二表算法的思路,应用求解最大团问题的思路计算DNA计算机的NP完全计算问题。使用这种算法,能将DNA分子计算的维数从60扩大至120,这种算法的DNA链数可达亚指数的O(1 414n),这种算法拓展了穷举法背包策略的限制,使DNA计算机NP完全问题算法优化。Draw lessons from the thinking of two table algorithm, this study applied thinking in solving the largest group of DNA computer npcomplete calculation problem. Using this algorithm, the dimensions of the DNA molecular computation can be expanded from 60 to 120, the number of DNA strands of this algorithm can reach the index, expand the exhaustive method backpack strategy, make the algorithm to optimize DNA computer NP complete problem.

关 键 词：质粒模型 DNA计算机算法 背包问题 

分 类 号：TP301.6[自动化与计算机技术—计算机系统结构]