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

DNA tetrahedron walker calculation model for 0-1 integer programming problem

作　　者：杨新木 杨静 殷志祥 唐震 崔建中 YANG Xinmu;YANG Jing;YIN Zhixiang;TANG Zhen;CUI Jianzhong(School of Mathematics and Big Data,Anhui University of Science and Technology,Huainan Anhui 232001,China;School of Mathematics,Physics and Statistics,Shanghai University of Engineering Science,Shanghai 201620,China;School of Electrical and Information Engineering,Anhui University of Science and Technology,Huainan Anhui 232001,China;Department of Computer Science,Huainan Union University,Huainan Anhui 232001,China)

机构地区：[1]安徽理工大学数学与大数据学院,安徽淮南232001 [2]上海工程技术大学数理与统计学院,上海201620 [3]安徽理工大学电气与信息工程学院,安徽淮南232001 [4]淮南联合大学计算机系,安徽淮南232001

出　　处：《阜阳师范大学学报（自然科学版）》2020年第2期89-94,共6页Journal of Fuyang Normal University:Natural Science

基　　金：国家自然科学基金项目(61672001,61702008);安徽省自然科学基金项目(1808085MF193);安徽高校自然科学研究项目(KJ2019A0538)资助。

摘　　要：DNA折纸术是一种新型的自组装方法,广泛应用于DNA计算中.基于DNA折纸术设计了一个DNA四面体步行者,并将DNA四面体步行者应用于求解0-1整数规划问题.通过DNA四面体步行者的行走,来找出所有可能解.最后,通过DNA四面体步行者所携带的纳米金颗粒的个数来判断是否是0-1整数规划问题的可行解.该模型求解错误率低,具有很强的可控性和实用性.DNA origami is a novel self-assembly method widely used in DNA computing.The DNA tetrahedral walker was designed based on DNA origami,and the DNA tetrahedron walker was applied to solve the 0-1 integer programming problem.By walking with DNA tetrahedron walker,we can find all possible solutions.Finally,the number of nano-gold particles carried by DNA tetrahedron walkers is used to determine whether it is a feasible solution to the 0-1 integer programming problem.This model has a low error rate and is highly controllable and practical.

关 键 词：0-1整数规划 DNA折纸术 DNA四面体 DNA计算 

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