巡回推銷員之謎

以推銷員為主角的難題

數學世界中存在著一個有關“巡回推銷員”的有趣難題。就像題目里說的這樣，這個問題的主角就是“推銷員”。

所謂“巡回推銷員問題”就是“一個推銷員每次造訪一個城市，經過所有的城市后再回到出發點，怎樣做才能讓他移動的距離是最短路徑”。今天去大阪，明天去廣島……將這個推銷員想象成在日本全國范圍內進行推銷的工作人員就容易理解了。

別看題目好像很貼近生活又很簡單，這可是“排列組合最適化問題”中有名的難題，就算用上超級計算機，想要求得最適合的解答也相當困難。

將城市數設為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～）研讀了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億年，以與我們生活息息相關的“巡回推銷員”問題為契機，計算機也開始跟生物一樣邁上了進化之路。

計算機的世界現在正在實現著令人驚奇的“進化”。

也許某一天，會有一個超越人類智慧的算法橫空出世，可以解決所有的數學難題和日常問題。