广义分子计算模型在0-1背包问题中的应用

计算机科学 ›› 2014, Vol. 41 ›› Issue (Z11): 7-9.

广义分子计算模型在0-1背包问题中的应用

杨震,马天宝,余文,李艳梅

北京理工大学机电学院爆炸科学与技术国家重点实验室北京100081;北京理工大学机电学院爆炸科学与技术国家重点实验室北京100081;北京邮电大学智能通信软件多媒体北京市重点实验室北京100876;北京理工大学机电学院爆炸科学与技术国家重点实验室北京100081

出版日期:2018-11-14 发布日期:2018-11-14
基金资助:
本文受国家自然科学基金资助

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

摘要： 生物分子计算在实现上有很多局限性。借鉴了广义图灵模型(Generalized Turing Model,GTM)[1]。该模型是由分子计算粘贴模型与图灵机相结合而得到的,并且已证明可以在多项式时间内准确获得0-1整数规划、集合覆盖等多个NP完全问题的全体可行解集。在此基础上将GTM应用于求解0-1背包问题,仿真展现了该模型的优点。

关键词: 广义分子计算,图灵机 ,0-1背包问题

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

杨震,马天宝,余文,李艳梅. 广义分子计算模型在0-1背包问题中的应用[J]. 计算机科学, 2014, 41(Z11): 7-9. https://doi.org/

YANG Zhen,MA Tian-bao,YU Wen and LI Yan-mei. Application of Generalized Molecular Computation Model in 0-1 Knapsack Problem[J]. Computer Science, 2014, 41(Z11): 7-9. https://doi.org/

参考文献

[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

Metrics

Viewed

Full text

Abstract

Cited

Shared

Discussed