引言
TSP(Traveling Salesman Problem)即旅行商問(wèn)題，是數(shù)學(xué)領(lǐng)域中著名問(wèn)題之一魄咕。這個(gè)問(wèn)題是這樣的：假設(shè)有一個(gè)旅行商人要拜訪n個(gè)城市，他必須選擇所要走的路徑，路徑的限制是每個(gè)城市只能拜訪一次磕诊，而且最后要回到原來(lái)出發(fā)的城市。路徑的選擇目標(biāo)是要求得的路徑長(zhǎng)度為所有路徑之中的最小值纹腌。TSP是一個(gè)典型的組合優(yōu)化問(wèn)題霎终，且是一個(gè)NP完全難題，關(guān)于NP的這個(gè)概念本文就不做詳細(xì)介紹了升薯，但簡(jiǎn)單的說(shuō)就是：TSP問(wèn)題目前尚不能找到一個(gè)多項(xiàng)式時(shí)間復(fù)雜度的算法來(lái)求解莱褒。
問(wèn)題分析
1.識(shí)別本質(zhì)
這個(gè)問(wèn)題乍一看，有那么一點(diǎn)像“最短路徑問(wèn)題”覆劈，然后我們就會(huì)自然地想到用Dijkstra算法去求得“從某一個(gè)城市出發(fā)保礼，到其他所有剩余城市的最短路徑”沛励，再或者如果是個(gè)真實(shí)地圖，我們可以用啟發(fā)式的“A星算法”快速搜索出“從某一個(gè)城市到另一個(gè)指定城市間的最短路徑”炮障。的確目派，如果是這樣真的挺好，但仔細(xì)想胁赢，這個(gè)問(wèn)題并非單純這么簡(jiǎn)單企蹭，它還要求去尋找“從某個(gè)城市開始，分別經(jīng)過(guò)其它城市一次且僅一次智末，最后再回到這個(gè)出發(fā)城市的最短巡回路徑”谅摄。
2.深入分析
所以該怎么求解呢，我們很容易想到一種類似于窮舉的思路：現(xiàn)在假設(shè)我們要拜訪11個(gè)城市系馆，從城市1出發(fā)送漠，最后回到城市1。顯然由蘑，從城市1出來(lái)后闽寡，我們隨即可以選擇剩余的10個(gè)城市之一進(jìn)行拜訪（這里所有城市都是連通的，總是可達(dá)的尼酿，而不連通的情況屬于個(gè)人特殊業(yè)務(wù)的裝飾處理爷狈，不是本文考慮范疇），那么很顯然這里就有10種選擇裳擎，以此類推涎永，下一次就有9種選擇…總的可選路線數(shù)就是：10!。也就是說(shuō)需要用for循環(huán)迭代10!次鹿响，才能找出所有的路線羡微，進(jìn)而篩選出最短的那條來(lái)。如果只拜訪個(gè)10個(gè)城市或許還好的話（需要迭代3628800次）抢野，那要拜訪100個(gè)城市（需要迭代9.3326215443944 * 10^157）簡(jiǎn)直就是計(jì)算機(jī)的噩夢(mèng)拷淘！更多個(gè)城市的話，計(jì)算的時(shí)間開銷可想而知指孤！
更一般地启涯，如果要拜訪n+1個(gè)城市，總的可選路線數(shù)就是n!恃轩，進(jìn)而時(shí)間復(fù)雜度就是O(n!)结洼，從這里我們同理也可以看出，這個(gè)算法的時(shí)間復(fù)雜度是非多項(xiàng)式的叉跛，它的開銷大是顯而易見的松忍。所以問(wèn)題的關(guān)鍵不在于尋找兩兩城市間的最短路徑，而在于去尋找一那條最短的巡回路徑筷厘，換句話說(shuō)鸣峭，就是尋找一組拜訪城市的先后次序序列 n1n2n3…nini+1…nnn1宏所。
解決方案
這是個(gè)NP完全問(wèn)題，窮舉算法的效率又不高摊溶，那我們?cè)撊绾瓮ㄟ^(guò)一個(gè)多項(xiàng)式時(shí)間復(fù)雜度的算法快速求出這個(gè)先后次序呢爬骤？目前比較主流的方法是采用一些隨機(jī)的、啟發(fā)式的搜索算法莫换，比如遺傳算法霞玄、蟻群算法、模擬退貨算法拉岁、粒子群算法等坷剧。但這些算法都有一個(gè)缺點(diǎn)，就是不一定能求出最優(yōu)解喊暖，只能收斂于（近似逼近）最優(yōu)解惫企，得到一個(gè)次優(yōu)解，因?yàn)樗麄儽举|(zhì)都是隨機(jī)算法陵叽，大多都會(huì)以類似“一定概率接受或舍去”的思路去篩選解雅任。各算法的實(shí)現(xiàn)思路都有不同，但也或多或少有互相借鑒的地方咨跌，有的與隨機(jī)因子有關(guān)、有的與初始狀態(tài)有關(guān)硼婿、有的與隨機(jī)函數(shù)有關(guān)锌半、有的與選擇策略有關(guān)……本文主要講述遺傳算法和蟻群算法的求解思路，關(guān)于其他更多類型的搜索算法可以在網(wǎng)上查閱寇漫，都有很多資料噠刊殉。
所以，綜合上述分析州胳，我們不難看出TSP問(wèn)題的求解大概是由兩步構(gòu)成的：
- 計(jì)算兩兩城市間的最短路徑：利用類似Dijkstra记焊、Flord、A星的算法求出最短路線栓撞。
- 計(jì)算最短巡回路徑：利用類似遺傳算法遍膜、蟻群算法的搜索算法求巡回拜訪的次序。
關(guān)于1中需要說(shuō)明一點(diǎn)瓤湘，就是現(xiàn)實(shí)生活中我們的地圖往往不是一個(gè)完全圖瓢颅，而是一個(gè)非完全圖，甚至有些節(jié)點(diǎn)僅僅是道路的分岔口弛说，而不是城市節(jié)點(diǎn)挽懦。
-
完全圖：兩兩城市間都有直達(dá)的路線，這條路線不需要經(jīng)過(guò)中間其他節(jié)點(diǎn)木人；
-
非完全圖：偶爾有兩個(gè)城市間的路線需要經(jīng)過(guò)其他中間節(jié)點(diǎn)信柿。
由于本文著重?cái)⑹霾襟E2)冀偶，更側(cè)重于搜索算法本身，所以后續(xù)文章一律將地圖簡(jiǎn)化為一個(gè)完全圖渔嚷。因?yàn)榫退闶欠峭耆珗D进鸠，我們也完全可以事先地、離線地采用步驟1)中的算法求解圃伶，得到兩兩城市間的最短路線堤如，存入數(shù)據(jù)庫(kù)，作為持久數(shù)據(jù)提供給后續(xù)在線的窒朋、需由用戶指定拜訪的城市的步驟2)使用搀罢，所以簡(jiǎn)化成完全圖是合乎情理的。
結(jié)語(yǔ)
本章就先講到這啦侥猩，下一篇會(huì)著重講述“遺傳算法”榔至，因?yàn)樗谒惴ㄋ枷搿⒆顑?yōu)解準(zhǔn)確率欺劳、適用面等各方面表現(xiàn)都比較好（一方面是我自己的感受唧取，一方面很多論文也這樣寫到），所以我選擇把它的設(shè)計(jì)與實(shí)現(xiàn)過(guò)程分享給大家作為參考（如果不嫌棄的話）划提。
