旅行推銷員問題求解器並不保證能給出全域最短路徑——它會回傳一個以啟發式建構、再透過局部雙邊交換加以改善的近似封閉路線。本站的 旅行推銷員問題求解器對這項限制說明得非常清楚：它結合最近鄰建構法與確定性的 2-opt 改善步驟，然後回報結果，並不聲稱已達到全域最優。這份誠實很重要，因為旅行推銷員問題本身屬於 NP-hard：當城市數量增加時，要找到真正的最短路線所需的計算量會以階乘級別爆炸性成長，因此實務工具只能依賴可能停在局部最小值的啟發式方法。所謂在 2-opt 下達到局部最佳，意思是不存在任何單一的雙邊交換能讓路徑縮短，這與「走訪每一點一次的最短路線」相比，仍是一個遠遠較弱的條件。在信任任何 TSP 結果用於規劃、調度或成本承諾之前，第一件要釐清的事，就是「局部改善」與「全域最短」之間的差異。
「全域最短」在 TSP 中真正的意涵
旅行推銷員問題要求找出一條封閉路徑，走訪每一個輸入點恰好一次並回到起點，且總距離盡可能最短。在所有合法排列中取出的這個最小值，就是全域最短路徑。對於 n 個點，一旦固定起點，需要比較的相異路徑數為 (n−1)!/2，而這個數量會以比任何 n 的多項式更快的速度成長。Google OR-Tools 也描述了同樣的路由目標，並警告由於路由問題在計算上相當困難，實務求解器可能回傳非最佳解。
一旦輸入點數大約超過十五到二十個，分支界線法或 Held–Karp 動態規劃等精確演算法仍可完成，但計算成本會迅速攀升。超過數十個點之後，即使是專用的研究級求解器，也往往需要數小時或特殊硬體才能證明全域最優性。這就是為什麼面向一般使用者的 TSP 工具（包括本頁的這個）刻意採用有界限的啟發式，並回報改善幅度而非最優性。
最近鄰法如何建立第一條路線
旅行推銷員問題求解器首先把第一列輸入鎖定為起點，然後以貪婪方式逐步前進。它從當前點出發，根據歐氏距離 sqrt((x₂−x₁)² + (y₂−y₁)²) 挑選最近的未造訪點。當兩個候選點距離完全相同時，平手規則保留原始輸入順序，這使得重複執行具有確定性。當所有點都被造訪完，最後一段會回到起點，使路線成為封閉。
最近鄰規則快速且直覺，但有個眾所周知的弱點：貪婪的第一步可能讓後續步驟陷入長程繞路。某個點之所以被早早選中，只因它局部距離近，卻可能迫使路線其餘部分自我交叉——這是封閉路線並非全域最短的一個強烈訊號。求解器會回報最近鄰距離，讓你能清楚看出 2-opt 還有多少改善空間。
2-opt 如何在局部改善路線
一旦形成一條完整的封閉路線，求解器會掃描成對的路徑邊並問一個簡單的問題：若把這兩條邊之間的線段反轉，總歐氏距離是否會嚴格下降？答案是肯定的話，就套用該交換，並從新路線重新開始掃描。當沒有任何一對邊能產生嚴格改善——或達到防護性的掃描次數上限——迴圈就會停止。執行過的 2-opt 掃描次數會與改善後的距離一起顯示，因此啟發式所做的工作是公開可見的，而非隱而不宣。
這正是 1958 年 Croes 為旅行推銷員問題所描述的局部改善法。其中關鍵在於「局部」的定義：最終路線只能保證不存在任何可改善的雙邊交換。這個條件對全域最優性而言是必要但非充分，因為一條路徑可能在 2-opt 下已局部最小，卻仍比真正的全域最優解更長。不同的起點或不同的建構規則，可能讓啟發式落入另一個局部最小值。
如何使用旅行推銷員問題求解器
- 開啟旅行推銷員問題求解器，依名稱、x、y 格式逐行輸入 3 到 50 個地點。名稱不得含有逗號，座標必須是有限且有界的數值，每組座標對必須唯一。
- 把希望作為起點的地點放在第一列，使建構出的路線從該處開始與結束。求解器會把第一列視為固定，這能讓相同輸入順序下的重複執行具有確定性。
- 送出座標以建立近似路線。頁面會顯示最近鄰的起始距離、2-opt 改善後的距離，以及所套用的 2-opt 掃描次數。
- 檢視封閉路線並詳讀頁面上所列的假設——直線歐氏距離、無道路、無交通、無時間窗——再判斷這些假設是否符合你的任務需求。
- 只有在直線歐氏距離確實是正確的衡量指標時，才複製結果。複製出來的內容包含完整的封閉名稱序列與計算出的距離。
為何不同起點會改變結果
由於求解器將第一列固定為起點，並使用確定性的最近鄰建構加上依輸入順序的平手處理，因此調換輸入列的順序會產生不同的路線。對某些輸入而言，這些路線的總距離可能一致，但在許多實際配置中並非如此。若路線品質很重要，標準做法是對同一組座標以不同起點執行數次，保留最短的結果，並視之為實務上的最佳解。
另外有兩項值得手動進行的檢查。首先，在草圖上目視檢查封閉路線，確認折線沒有自我交叉——自我交叉的路線強烈暗示存在更佳的順序。其次，在反轉輸入順序後重跑一次；最近鄰法從尾端出發的行為往往與從頭部不同，若得到較低的改善距離，便是清楚顯示前一次執行落入了較差的局部最小值。
求解器刻意忽略的部分
本工具使用平面上的直線歐氏距離，不呼叫任何外部地圖或路徑規劃 API，因此許多真實世界的複雜因素被刻意排除在外。座標會被視為抽象的平面數值，例如局部繪圖上的公尺數、版面配置中的像素，或無單位的課堂座標——而非經緯度。若直接把歐氏距離套用於角度，會扭曲真實的地球距離，尤其是跨越廣大區域或跨越換日線時更是如此。對於地理點，請轉換至合適的局部投影，或交由基於測地線距離的路由服務處理；指南 TSP 求解器能輸入經緯度嗎？對相關限制有更深入的說明。
| 面向 | 旅行推銷員問題求解器的行為 |
|---|---|
| 座標系統 | 兩軸使用相同單位的平面 |
| 距離衡量 | 直線歐氏距離，sqrt((x₂−x₁)²+(y₂−y₁)²) |
| 道路、交通、單行道 | 忽略；不呼叫任何地圖或路徑規劃 API |
| 地理點（經緯度） | 不適合作為可靠的距離來源 |
| 解的保證 | 在雙邊交換下達到局部最佳，非全域最短 |
| 隱私 | 輸入與輸出皆留在瀏覽器中；資料不會離開裝置 |
啟發式足夠的時機——與不足的時機
對於學習 TSP 演算法原理、在小型座標草圖上探索空間排序、為局部格線規劃近似巡檢順序，或產生可重現的測試資料，啟發式是合適的工具。在輸入很小、精確枚舉輕而易舉時，它也很適合作為健全性檢查。對任何謎題、課堂練習，或衡量指標確實就是平面上直線距離的版面配置問題來說，同樣適用。
當路線驅動的是真實決策時，啟發式就成了不適當的工具：調度、導航、成本承諾、時間窗、車輛容量、多名駕駛，或任何安全關鍵的路由。面對這類任務，正確的輸入應該是真實的距離或時間矩陣，而正確的引擎則是經獨立驗證網路資料校驗過的路由求解器，例如 Google OR-Tools。請把本頁的局部近似視為學習輔助與快速估算工具，而非營運層級的權威依據。
一個小型範例
為了讓建構過程與距離運算更具體，取三個點：A 在 (0, 0)、B 在 (3, 0)、C 在 (0, 4)，並以 A 作為固定的起始列。從 A 出發，最近鄰步驟比較到 B 的距離 sqrt((3−0)²+(0−0)²) = 3，以及到 C 的距離 sqrt((0−0)²+(4−0)²) = 4，因此選 B。從 B 出發，唯一未造訪的點是 C，距離為 sqrt((0−3)²+(4−0)²) = sqrt(9+16) = 5。將路線從 C 閉合回 A 再加上 4。最近鄰的總距離為 3 + 5 + 4 = 12。由於這三條邊構成一個 3-4-5 的直角三角形，且沒有可交叉的替代方案，2-opt 找不到任何嚴格的改善交換，因此改善後的距離維持在 12——這提醒我們，在小型幾何輸入上，局部最佳與全域最佳可能恰好一致，儘管在規模放大後兩者便會分道揚鑣。
若想進一步了解，請參閱 含小數的 24 點求解器：通往 24 的分數路線。