TSP的DNA计算算法

提出了TSP的DNA算法,共有六个步骤:首先将TSP转化为有向图的经过所有点最短闭链问题并进行编码;其次从某点开始用有目的的终止技术——芯片技术、保护基技术以及杂交实验——得到起点和终点相同的DNA链;再用分离实验产生经过所有顶点的DNA链;然后用电泳实验取出链长最短的DNA链;最后用标记实验解读最优解集。讨论了算法的复杂性并用实例说明了算法的有效性。还讨论了推广的TSP——推销员在城市有停留时间——的算法的变化——只需改变编码方式,以及实验的简化问题。最后说明了本算法提出的一种新的合成技术——有目的的终止技术的优势和前景。