“巡回推销员”之谜

以推销员为主角的难题

数学世界中存在着一个有关“巡回推销员”的有趣难题。就像题目里说的这样，这个问题的主角就是“推销员”。

所谓“巡回推销员”问题就是“一个推销员每次造访一个城市，经过所有的城市后再回到出发点，怎样做才能让他移动的距离是最短路径”。今天去大阪，明天去广岛……将这个推销员想象成在日本全国范围内进行推销的工作人员就容易理解了。

别看题目好像很贴近生活又很简单，这可是“排列组合最适化问题”中有名的难题，就算用上超级计算机，想要求得最适合的解答也相当困难。

将城市数设为n，那么可能的路径总数就有条。

当n是一个小数字时，我们可以尝试所有组合的可能，然后从中找到最短路径。可是，当n是一个很大的数字时，这种组合的数量会呈爆发式增长，想要尝试所有路线事实上是不可行的。

比如说，要经过10个城市时，路径排列的总数就达到了181440条；经过30个城市时，可能的路径就有4.42×1030条。

这个数字到底有多么令人绝望，我们用计算速度为10太Flops的计算机（1秒钟能演算1013次小数点浮动的计算机。顺便告诉大家，playstation 4的运算速度是1.84太Flops，地球模拟程序的运算速度是35.86太Flops），想要运算出所有的组合需要25万兆年以上。宇宙已诞生137亿年，却无法跟这项运算所需的时间相比。

隐藏在生活中的“排列组合最适化问题”

就像“费马大定理”一样，正因为这是个绝对性的难题，所以关于它的解法才得以进化。以“巡回推销员”为例的“排列组合最适化问题”是一个非常现实的问题。

超市的商品配送；

快递等的配送计划问题；

汽车导航系统的路径检索；

手机的频率分配；

铁路、航空乘务员的分配；

制作体育比赛日程表……

以上都是与我们日常生活息息相关的活动，而这些都是“排列组合最适化”的问题。“巡回推销员”问题自身已经被应用到了配送计划制订和电子线路板上安装零件时挖洞的顺序决定问题上。

十进制算法会遗传吗？

在“巡回推销员”的问题中，如果城市数量很多的话，想求得最适答案简直难如登天。高效又严谨的求解方法还没有确立，因此求得近似解的方法就显得尤为重要了。其中有一种有效的近似值解法被称为“遗传算法”（Genetic Algorithm）。

“十进制算法”是一种决定计算顺序、旨在解决问题的阶段式方法。用特定的编程语言（C、Basic、Java等）来记述算法就叫作程序。

遗传算法是1975年由密歇根大学的约翰·霍兰德（1929—　）提出的。生物的进化依赖于遗传因子的重组，他从生物的“进化过程”中得到启示，得出了“最适化算法”，即从遗传因子中选择复数的个体（解的候补）组成集团，再利用这个集团将解的候补一个个重组，以探索最合适的答案的计算方法。

将问题当作物种遗传因子序列的进化来谋求最适解。遗传算法中会用到“选择”（适应环境的后代个体会增加，不适应的物种则会减少）、“交叉”（按一定的概率将两个物种的遗传因子序列组合起来形成其他物种）、“突变”（遗传因子序列的特定存储单位发生了反转）等遗传学范畴内的概念来进行操作。

如果在网上搜索“巡回推销员问题Java”，我们会找到很多程序。

实际上，在网上能看到很多关于“巡回推销员”问题的解法。

DNA计算机的诞生

遗传因子本属于生物学，但是却出现在了数学和计算机的世界，真是有趣极了。而且，它还有更深的妙趣，那就是利用遗传因子而诞生的超高速计算机——DNA计算机。

令人震惊的是，生物学家杰拉尔德·埃德尔曼（1929—2014）研读了DNA双螺旋结构的发现者——美国生物学家詹姆斯·沃森（1928—　）的《遗传因子的分子生物学》后，产生了将DNA应用到计算机中的灵感。1994年，他制作出DNA计算机，并为大家演示了其对“巡回推销员”问题的解答。

运用DNA算法解答巡回推销员的问题时，首先将各个城市及连接的路径用DNA的四个碱基A（腺嘌呤）、T（胸腺嘧啶）、G（鸟嘌呤）、C（胞嘧啶）表示出来。

东京＝｛CGCATT｝、大阪＝｛CTAGAT｝，像这样将DNA人工合成，然后放到试管中混在一起让它们发生反应。这样一来，由于DNA的特性是只有“A和T” “C和G”这两种组合，从东京和大阪的碱基序列中就可以创造出｛TAAGAT｝这样的新DNA。这也就成了东京和大阪之间路径的一个候补项。

像这样可以表示解的候补项的DNA会因为PCR（聚合酶连锁反应）被大量制造出来，再根据去哪个城市比较顺路为条件将这些解分离开来，最后将表示解的DNA抽出来。

因为DNA是极小的分子，可以大量制造。仅1立方厘米就可以容纳6×1016个DNA分子。如果每个DNA都能当作计算单位来运作，那么超并列运算就可能实现，这对于解决像“巡回推销员”这种复杂又很耗费时间的问题来说是非常有效的方法。

我们可以认为DNA计算机就是由DNA组成的生命体，就是计算机本身。很不可思议吧！

生物的进化已经持续了137亿年，以与我们生活息息相关的“巡回推销员”问题为契机，计算机也开始跟生物一样迈上了进化之路。

计算机的世界现在正在实现着令人惊奇的“进化”。

也许某一天，会有一个超越人类智慧的算法横空出世，可以解决所有的数学难题和日常问题。