旅行推销员问题（又称为旅行商问题、TSP问题）是一个多局部最优的最优化问题：有n个城市，一个推销员要从其中某一个城市出发，唯一走遍所有的城市，再回到他出发的城市，求最短的路线。

路线计算方法

DNA计算步骤

DNA计算机的优越性

路线计算方法

[用DNA去计算]

经过了一番深思熟虑的奇思妙想之后，1994年，美国科学家艾德曼（Adleman）利用试管中的DNA计算了7个城市13条航线的旅行推销员问题。这真是一个绝妙的想法，令人叹为观止，而这工作也从此开辟了DNA计算机研究的新纪元。

DNA计算步骤

首先，艾德曼分别用20个核苷酸长的不同的DNA序列对7个城市进行了编码。比如，第二个城市的编码（O2）为TATCGGATCGGTATATCCGA；第三个城市的编码（O3）为CTATTCGAGCTTAAAGCTA。然后，对13条航线进行编码。以城市2与城市3之间的航线O2-3为例，编码的规则是O2的后十个核苷酸作为O2-3的前十个核苷酸，O3的前十个核苷酸作为O2-3的后十个核苷酸，即O2-3为GTATATCCGAGCTATTCGAG。接着再合成7个城市编码DNA的互补DNA。所谓互补DNA就是如果前一个DNA链上某一位置上的核苷酸是A，则互补DNA链上同一位置上的核苷酸就是T；前者是C，后者则为G；反之亦然。以O3为例，它的互补DNA（记作O3~）就是GATAAGCTCGAATTTCGAT。最后，用7个城市的互补DNA（O1~、O2~、O3~、O4~、O5~、O6~、O7~）与13条航线的不同编码DNA（Oi-j）在试管中进行混合。举例来说，由于O3~上的核苷酸正好是O2-3上后十个核苷酸和O3-4上前十个核苷酸的互补核苷酸，通过A—T、C—G的配对法则，O3~就可以像“夹板”一样将O2-3和O3-4连接在一起。同理，利用Oi~为“夹板”使对应的Oi-j分别连接，就可以产生大量的随机连接通路。

第二步，利用O1和O7~作为引物，对这些随机产生的DNA序列进行聚合酶链式反应。这样，只有那些从O1开始到O7为止的通路DNA序列可以被大量扩增，而其它通路（比如：始于O1终止于O6）因不满足扩增条件而不被扩增。

第三步，将PCR扩增的DNA序列进行电泳分离，选取分子质量为140个核苷酸的双链DNA。因为每个城市都是由20个核苷酸的DNA编码，连通7个城市的编码DNA应为20×7=140个核苷酸，所以，选取的140个核苷酸的DNA序列就是可以连通7个城市通路的DNA序列。

第四步，将选出的140个核苷酸的双链DNA序列加热变性，将双链DNA拆分成单链，再用含有O2~序列的磁珠与其互补结合，选取结合了O2~序列的单链DNA序列，这样的序列就是由城市1连通城市2的通路。将选取的序列退火复性后，再加热变性，分别用含有O3~、O4~、O5~、O6~的磁珠进行分离提取。最后能与O6~结合的序列就是从城市1起始，途径城市2、3、4、5、6，终止于城市7的通路DNA序列。

第五步，将上述分离的DNA序列再次进行聚合酶链式反应，扩增的DNA序列经过电泳分离，最终得到的序列就是7个城市13条航线的旅行推销员问题的正确答案。

DNA计算机的优越性

我们知道旅行推销员问题的一个特点，就是城市节点数与运算步数呈指数关系，而艾德曼利用DNA计算机却将城市节点数与运算步数转化为线性关系，大大简化了运算的复杂性。另外，DNA计算机的一个巨大优越性就是DNA上核苷酸可编码信息的巨量性和DNA杂交运算的高度并行性。可以预计，随着研究的不断深入，DNA计算机这一分子生物学与计算机科学的学科交叉产物必将逐步走向实用，或许，就将成为改变人类生活面貌的明日计算机。