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

给出了闭环DNA计算模型及其生化实验。用闭环DNA计算模型设计出了指派问题的DNA算法。首先对决策变量进行二维DNA编码来存放决策变量和效益值，然后通过有目的的终止技术和删除实验得到指派问题的全部可行解，最后通过电泳实验和检测实验获得最优指派问题的最优解。举例说明了算法的可行性。最后，为减少DNA编码数量和缩短DNA编码的码长，讨论了算法的两种改进方法。

An Algorithm of Assignment Problem Based on Closed Circle 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.