DNA计算在整数规划问题中的应用

DNA Computation for a Category of Special Integer Planning Problem

基于生化反应原理的DNA计算由于在解决一类困难问题,特别是NP-完全问题上具有硅计算机无法比拟的优势,因此对DNA计算的研究具有重要意义。利用在基于表面的DNA计算中采用荧光标记的策略,提出了一种基于DNA计算的一类特殊整数规划问题最优解的求解算法,新算法利用荧光猝灭技术,通过观察DNA分子表面的荧光来排除非解。算法分析表明,新提出的基于DNA计算的求解算法具有编码简单和错误率低等特点。

Biochemical reaction theory based DNA computation is of much better performance in solving a class of intractable computational problems such as NP-complete problems, it is important to study the DNA computation. A novel algorithm based on DNA computation is proposed, which solves the problem of a category of special integer planning problem by using the method of fluorescence labeling in the surface based approach to DNA computation. By utilizing the techniques of fluorescence distinguishing, the new algorithm can eliminate all of those false solutions through observing the fluorescence on the surface of DNA molecules. Algorithm analyses show that the new proposed algorithm based on DNA computation has such good characteristics as simple encoding and low fault rate etc.