旅行商問題(TravelingSalesmanProblem，TSP)是一個經(jīng)典的組合優(yōu)化問題。經(jīng)典的TSP可以描述為：一個商品推銷員要去若干個城市推銷商品，該推銷員從一個城市出發(fā)，需要經(jīng)過所有城市后，回到出發(fā)地。應(yīng)如何選擇行進(jìn)路線，以使總的行程最短。

旅行商問題分析

分析

旅行商問題要從圖G的所有周游路線中求取最小成本的周游路線，而從初始點出發(fā)的周游路線一共有(n-1)!條，即等于除初始結(jié)點外的n-1個結(jié)點的排列數(shù)，因此旅行商問題是一個排列問題。排列問題比子集合的選擇問題通常要難于求解得多，這是因為n個物體有n!種排列，只有 個子集合(n!>O( ))。通過枚舉(n-1)!條周游路線，從中找出一條具有最小成本的周游路線的算法，其計算時間顯然為O(n!)。

所以該怎么求解呢，很容易想到一種類似于窮舉的思路：現(xiàn)在假設(shè)我們要拜訪11個城市，從城市1出發(fā)，最后回到城市1。顯然，從城市1出來后，我們隨即可以選擇剩余的10個城市之一進(jìn)行拜訪（這里所有城市都是連通的，總是可達(dá)的），那么很顯然這里就有10種選擇，以此類推，下一次就有9種選擇……總的可選路線數(shù)就是：10!。也就是說需要用for循環(huán)迭代10!次，才能找出所有的路線，進(jìn)而篩選出最短的那條路線。如果只拜訪10個城市的話（需要迭代3628800次）或許還好，那要拜訪100個城市（需要迭代9.3326215443944 * 10^157）開銷可想而知

更一般地，如果要拜訪n+1個城市，總的可選路線數(shù)就是n!，進(jìn)而時間復(fù)雜度就是O(n!)