图顶点着色问题的改进粘贴DNA算法

An Improved DNA Algorithm of Graph Vertex Coloring Problem Based on Sticker Model

针对目前存在的解决图顶点着色问题的DNA算法或DNA编码量过大或复杂度太高的问题,为了提高解题效率,将多级分离技术应用到图顶点着色问题的求解中,对解决该问题原有粘贴DNA算法加以改进;改进后的算法减少了操作步骤,达到了预期目的;最后,通过对一个实例的模拟,说明了改进算法的可行性。

The existed DNA algorithms of graph vertex-coloring either needed lots of DNA strands or had extortionate complexity. In order to improve the efficiency to solve the problems, the multi-separation techniques were applied to solve the graph vertex-coloring problem, and the former algorithm was improved. The improved algorithm reduced the operating steps. At last, the feasibility of the improved algorithm was proved by a simulation experiment to an instance.