以TSP為代表的NP問題理論上沒有突破，也不會有突破。因為它不是真正的數學問題，所以沒啥好研究的。研究的論文鋪天蓋地，但是並沒有什麼理論價值。這不是數學理論問題，而比較像是應用數學問題，一個工程問題，甚至是一個軟件程序問題。理論討論沒有意義，有價值的僅僅是程序運行效果。

其次，我討論一下TSP及其相關的一類問題，如貨郎擔問題，哈密頓環，是不是完全圖，對稱性，有無權，搜索所有點（即不必回原點）等等。

雖然有種種差別，但為了便於討論，這裡僅僅討論如下情形：

完全圖，同時，非直接連接的兩個點（中間經過至少其他一個點）的距離，即兩個或更多點距離之和，一定大於這兩個點的直接距離。而如果約定是幾何距離的概念，無論是二維，是三維，也是確定的。即，如果給與每個點坐標，上述距離的關係一定成立。

但點連接的類TSP問題這一點不一定是必須的。另外，正規的TSP問題不允許重新訪問一個點，而符合上述幾何概念的對稱完全圖也沒有沒有必要回到一個點。但原則上，非完全圖，非幾何距離概念，也可能允許重複訪問。也可以對非完全圖做出相應的完全圖，一種是將不通兩點的距離當作無窮大。另外一種可行性比較好的做法是:如果允許重複訪問，那可以把兩點（或更多點）之間的距離（之和），當作這兩個點的直接距離。但根據筆者的實踐，如此將非完全圖完全化的處理，減少了信息量，對改進某些算法不利。

此外，對稱，有權。

TSP的算法琳琅滿目，最主要有遺傳，蟻群。但結果都不可重複，隨機，每次結果不同，顯然都是局優解，陷入其中不可自拔，不滿意結果只能從頭開始。貪心解法可重複，速度快，但是質量低。窮盡法只能用於點數很少的情況，計算量隨點數乘介的增加是其NP問題的原因。

但是如果不能窮盡，TSP原則上無法驗證最佳解。好壞只能在最後質量，需要時間等方面在各種方法比較中才顯出意義來。一個矛盾是在計算時間和質量之間取得平衡，就是說，通常時間長，質量會好一些。這在實踐上時間的限制對質量有了限制。就既可能因為每次結果不同而需要多試幾次，但有些運行參數可以幫助取這兩方面的平衡和取捨。

因為完全圖每一個點都有N-1條連線，在最理想情況下，只有最短（權重最低）的兩條被用上。如果最後結果和這個和相等，就完美了。但是對於完全隨機產生的數據里，這沒有可能。毫無疑問，最優解會分布在同這個和略微大於1的一個高斯分布上。根據我的經驗，這個比主要區間在1.1到1.2之間，大體是隨着點數，比如從30到3000，而慢慢增加。

筆者的方法是最慢加入法：隨機割掉一段，然後以最短的一個點加入，直到最後。這個方法有點類似遺傳法，因為結果不一定會比原來的結果好，但你一般總可以找到更好的結果，然後重複這個過程，直到你無論你如何切割，都不能得到更好的結果為止（得到局優解）。

這個算法中用到個點之間的距離，有N（N-1）/2條。如果N夠大（比如超過1000），這個計算需要一點時間（如果是比較弱的個人計算機）。但筆者辦法得到收斂，而且結果不錯，需要的時間也沒有多多少。幾千點也只需要若干小時。如果幾百，那就非常快，若干分鐘。

當然，貪心算法只需要若干秒，哪怕幾千點，但這個結果很差，只能作為筆者方法的起點。