Computer Science ›› 2014, Vol. 41 ›› Issue (Z11): 7-9.

Previous Articles     Next Articles

Application of Generalized Molecular Computation Model in 0-1 Knapsack Problem

YANG Zhen,MA Tian-bao,YU Wen and LI Yan-mei   

  • Online:2018-11-14 Published:2018-11-14

Abstract: Biomolecular computing has many limitations in implementation.In the literature,molecular computing sticker model and turing machine were combined to generate a generalized turing model GTM.The model has been proved to be accurate to get all the feasible solution set of mulitiple NP complete problems like 0-1 integer programming and set covering .In this paper,on this basis,GTM was applied to solve the 0-1 knapsack problem.The simulation shows the advantages of the model and further validation of the extensive application of the model.

Key words: Generalized molecular computation,Turing model,0-1 knapsack problem

[1] 余文,高荔,杨旭东,等.一种基于分子计算的广义图灵模型[J].计算机科学(专刊),2006,33(7):362-365
[2] Adleman L.Molecular computation of solutions to combinatorial problems[J].Science,1994,266(11):1021-1024
[3] Ouyang Q,Kaplan P D,Liu S,et al.DNA solution of the aximal clique problem[J].Science,1997,8(546-9):446-449
[4] Sakamoto K,Gouzu H,Komiya K,et al.Molecular computation by DNA hairpin formation[J].Science,2000,8(5469):1223-1226
[5] Zhou Kang,Gao Zun-hai,Xu Jin.An algorithm of DNA computing on 0-1 planting problem[J].Advances in Systems Science and Applications,2002,5(4):587-593
[6] 王子成,周康,罗亮,等.DNA计算中编码序列的过滤函数研究[J].计算机工程与应用,2008,4(32):10-11
[7] 周康,殷燕芳,李玉华,等.DNA编码的模型分析[J].华中科技大学学报:自然科学版,2007,5(7):67-70
[8] Lee J Y,Shin S Y,Park T H,et al.Solving traveling salesman problems with DNA molecules encoding numerical values[J].BioSystem,2004,8(1/3):39-47
[9] 周康,同小军,许进.背包问题的闭环DNA算法[J].系统仿真学报,2008,0(17):4605-4608
[10] Lipton R J.DNA solution of hard computational problems[J].Science,1995,8(5210):542-545
[11] Dirk F,Cukras A R,Lopton R J,et al.Molecular compution:RNA solution to chess problem[J].Biochemistry,2000,7(4):1385-1389
[12] 周康,同小军,许进.基于粘贴DNA芯片模型的八皇后问题算法[J].系统工程学报,2008,3(3):372-376
[13] 李艳梅,余文,宁建国.一种广义分子计算模型及其在NP问题中的应用[J].计算机应用研究,2014
[14] 霍红卫,庄心谷.超立方体上0-1背包问题的并行算法[J].西安电子科技大学学报,1995,2(3):249-255
[15] 霍红卫.序列比较问题的分治法[J].西安电子科技大学学报,1998,5(3):345-347

No related articles found!
Viewed
Full text


Abstract

Cited

  Shared   
  Discussed   
No Suggested Reading articles found!