有界整数规划问题的DNA计算

DNA computation for integer planning problem with limited range

基于生化反应原理的DNA计算具有强大的并行运算能力,对于解决NP完全问题上具有硅计算机无法比拟的优势,因此对DNA计算的研究具有重要意义。基于荧光标记的策略,提出了约束方程变量分解的概念,通过将约束方程进行分解和增加约束补链的方法,解决了有界整数规划问题。利用荧光猝灭技术,基于DNA计算的新算法具有编码简单和错误率低的特点。

Since DNA computation based on the theory of biochemical reactions has better performance than traditional computing methods based on the current silicon computers in solving a class of intractable computational problems, especially the NP-complete problems, it is of great importance to study the DNA computation. On the basis of the fluorescence labeling scheme, this paper prop〈seed the concept of variable decomposition of restricted equations and solves the integer planning problem with limited range through the method of decomposing restricted equations and increasing restricted complement links. Using technology of fluorescence labeling in the surface, the novel algorithm based on DNA computation has good characteristics of simple encoding and low fault rates etc.