基于闭环DNA的指派问题算法  

An Algorithm of Assignment Problem Based on Closed Circle DNA

作　　者：周康[1] 同小军[1] 许进[2] 

机构地区：[1]武汉工业学院数理科学系,武汉430023 [2]华中科技大学控制科学与工程系,武汉430074

出　　处：《计算机科学》2007年第12期211-213,共3页Computer Science

基　　金：国家自然科学基金项目资助(编号:60403002);湖北省自然科学基金项目资助(编号:2005ABA233);湖北省优秀中青年科持创新团队计划项目资助;浙江省自然科学基金项目资助(编号:ZJNSF-Y105654)

摘　　要：给出了闭环DNA计算模型及其生化实验。用闭环DNA计算模型设计出了指派问题的DNA算法。首先对决策变量进行二维DNA编码来存放决策变量和效益值,然后通过有目的的终止技术和删除实验得到指派问题的全部可行解,最后通过电泳实验和检测实验获得最优指派问题的最优解。举例说明了算法的可行性。最后,为减少DNA编码数量和缩短DNA编码的码长,讨论了算法的两种改进方法。In this paper, a model of closed circle DNA computing and its bio-chemistry experiments are brought forward. An algorithm based on closed circle DNA is designed for assignment problem. In the algorithm, first planar DNA encoding for each decision-maklng variable is encoded to deposit each decision-making variable and benefit value. Then all feasible solutions are gained with purposive ending technology and delete experiment. And then all optimization solutions are obtained with electrophoresis experiment and detect experiment. Feasibility of this algorithm is explained by an example. Finally two improving methods of this algorithm are discussed in order to decrease number of DNA encodings and to shorten encoding length of DNA encodings.

关 键 词：闭环DNA计算模型 指派问题 删除实验 有目的的终止技术 

分 类 号：O221.3[理学—运筹学与控制论]