基于DNA链置换反应网络求解0-1背包问题  

Solving 0-1 Knapsack Problem Based on DNA Strand Displacement Reaction Network

作　　者：杨静 郑雅雯 张彤彤 蒋天怿 YANG Jing;ZHENG Yawen;ZHANG Tongtong;JIANG Tianyi(School of Mathematics and Big Data,Anhui University of Science and Technology,Huainan Anhui 232001,China)

机构地区：[1]安徽理工大学数学与大数据学院,安徽淮南232001

出　　处：《安徽理工大学学报（自然科学版）》2024年第1期78-88,共11页Journal of Anhui University of Science and Technology:Natural Science

基　　金：国家自然科学基金资助项目(62272005)。

摘　　要：目的基于DNA链置换的化学反应网络可以作为一种有效的编程语言来解决各种数学问题,而0-1背包问题是一个经典的NP问题。为了求解0-1背包问题。方法提出利用DNA链置换反应网络,并利用Visual DSD设计仿真实验。结果通过加权、求和和阈值3个反应模块进行求解,最后由输出的单链DNA来表达结果。由于浓度的检测存在一定误差,使用带有荧光分子的单链DNA输出表达操作结果。最后,使用DSD仿真软件得到变量转换模块相对应的链置换反应网络图、变量仿真图以及阈值比较图。模型表明,该算法能够有效降低0-1背包问题的复杂度,并且具有较高的求解精度和稳定性。结论所提出的模型进一步丰富了DNA计算,并拓宽了DNA链位移的计算宽度。Objective To solve the 0-1 knapsack problem,which is a classical NP problem since the chemical reaction networks based on DNA strand displacement can be used as an effective programming language to solve various mathematical problems.Methods The DNA strand displacement reaction network was proposed and Visual DSD was used to design the simulation experiment.Results Three reaction modules,weighting,summation and threshold,were used to solve the problem,and the result was expressed by the output single strand DNA.Due to the error of concentration detection,the results of the operation were expressed by using a single strand DNA with fluorescent molecules.Finally,DSD simulation software was used to obtain the chain displacement response network diagram,variable simulation diagram and threshold comparison diagram corresponding to the variable conversion module.The model showed that the algorithm reduced effectively the complexity of 0-1 knapsack problem and had high accuracy and stability.Conclusion The model proposed in this paper is able to enrich DNA computation and broaden the computational width of DNA strand displacement.

关 键 词：DNA链置换 0-1背包问题 NP问题 DNA计算 

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