旅行推銷員問題求解器 (TSP)

旅行推銷員問題求解器 (TSP)

旅行推銷員問題求解器 TSP 是一款實用且具有教育意義的計算機，專為經典的旅行推銷員問題 (TSP) 設計：給定一組城市和每對城市之間的距離，尋找訪問每個城市恰好一次並返回起點的最短可能路徑。此求解器接受平面坐標或自定義距離矩陣，根據問題規模自動選擇最佳算法，並將產生的路徑呈現為動畫 SVG 地圖。

什麼是旅行推銷員問題？

形式上，給定一個具有頂點集 V = {1, 2, ..., n} 和邊權重 d(i, j) 的完全賦權圖 G = (V, E)，TSP 尋找頂點的一個排列 π，使以下各項最小化：

最後一項使路徑閉合。TSP 是組合優化中最古老且研究最廣泛的問題之一——它在一般情況下是 NP-hard 的，這意味著目前沒有已知算法能在多項式時間內解決所有實例。儘管如此，它仍出現在無數的現實應用中：車輛路線規劃、電路板 (PCB) 鑽孔、DNA 測序、倉庫揀貨路線、天文觀測時間安排，甚至是農村郵政遞送。

此求解器如何運作

Held–Karp 動態規劃 (精確算法)

對於小規模實例（最多 12 個城市），求解器使用 Held–Karp 算法計算可證明的最佳路徑，該算法於 1962 年由 Richard Bellman 以及 Michael Held & Richard Karp 獨立發表。關鍵的遞推關係如下，其中 C(S, j) 是從頂點 1 到頂點 j 且恰好訪問子集 S 的最短路徑：

最佳路徑成本即為 min_j [C({1,...,n}, j) + d(j, 1)]。Held–Karp 的運行時間為 O(2ⁿ · n²)，內存為 O(2ⁿ · n)——這比暴力破解 n! 有了巨大改進，但仍呈指數級增長。超過約 20 個城市後，內存佔用就會變得不切實際。

最近鄰 (Nearest-Neighbor) + 2-opt (啟發式算法)

對於較大規模的實例，求解器使用兩階段啟發式算法。首先，最近鄰 (Nearest-Neighbor) 算法通過從每個起始頂點貪婪地走向最近的未訪問城市來構建快速路徑。求解器嘗試多個起始頂點並保留最佳路徑。然後，2-opt 局部搜索通過反復移除兩條邊並以唯一另一種可能的方式重新連接得到的兩條路徑來改進路徑：

從幾何上講，2-opt 移除了路徑中所有的「交叉」：任何兩條交叉的線段總是可以通過取消交叉來獲得更短的總長度。算法停止於局部最優解，即沒有任何單次交換可以改進路徑，稱為 2-optimal 路徑。在現實的歐幾里得實例上，2-opt 通常能在幾毫秒內找到與真實最優解相差 2–5% 以內的路徑。

輸入格式

坐標模式 (x, y)

每行一個城市。每行格式為 標籤, x, y —— 標籤是可選的。求解器會自動計算歐幾里得距離，並在城市的真實位置視覺化城市。

距離矩陣模式

一個 n × n 的非負距離方陣，每行一個橫列，數值由空格或逗號分隔。矩陣可以是對稱或不對稱的——不對稱矩陣可以模擬單行道、可用性變化的機票價格以及受風向影響的旅行。可以選擇在「矩陣標籤」欄位提供標籤。

算法比較

如何使用此計算機

1. 選擇輸入模式。 如果您的城市具有有意義的 (x, y) 位置，請選擇「坐標」；如果您的成本是非歐幾里得或不對稱的，請選擇「距離矩陣」。
2. 粘貼或輸入您的數據。 每行一個城市或一行矩陣。點擊表單上方的快速示例按鈕可預填一個有效的示例。
3. 選擇算法。 保持在「自動」以使用合適的預設值：當實例規模足夠小能證明最優性時使用 Held–Karp，否則使用 NN + 2-opt。如果您想進行比較，可以強制選擇特定算法。
4. 選擇封閉或開放。 封閉路徑會返回起點——這是傳統的 TSP。開放路徑模式解決相關的哈密頓路徑問題，即推銷員在不同的城市結束。
5. 點擊「求解」。 結果頁面會顯示路徑總長度、路線的動畫 SVG（點擊「重播動畫」再次觀看）、完整的城市序列、每條邊的細目，以及高亮顯示路徑邊的距離矩陣。

運算示例

考慮五個城市——一個長方形加一個頂點：A (0, 0), B (4, 0), C (4, 3), D (0, 3), E (2, 5)。求解器返回：

• 路徑： A → D → E → C → B → A
• 長度： 3 + √8 + √8 + 3 + 4 ≈ 15.66
• 是否最佳？ 是 —— Held–Karp 證明不存在更短的路徑。
• 為什麼是這個順序？ 該路線追蹤了五個點的凸包 (A → D → E → C → B → A)。歐幾里得 TSP 的一個經典屬性是，最佳路徑會按循環順序訪問凸包上的點；內部點則插入相鄰的凸包鄰居之間。任何交叉自身路徑的路徑，例如 A → C → B → D → E → A（長度 ≈ 21.8），總是可以通過 2-opt 取消交叉以獲得更短的結果。

現實世界應用

• 物流與配送 —— 優化司機在 15 個站點之間的每日路線，以儘量減少燃料和時間。
• 製造業 —— 安排 CNC 鑽頭在 PCB 上鑽孔的順序，以減少機頭移動。
• 基因組組裝 —— 根據重疊相似度對 DNA 片段進行排序，編碼為距離矩陣。
• 天文學 —— 在目標恆星之間安排望遠鏡轉向，以最大限度地增加觀測時間。
• 倉庫揀貨 —— 安排過道訪問序列，以最少的步數完成訂單。
• 旅遊規劃 —— 規劃一個多城市的旅行，儘量減少旅行時間和票價成本。

常見問題解答

什麼是旅行推銷員問題？

旅行推銷員問題 (TSP) 要求尋找訪問每個城市恰好一次並返回起始城市的最短路徑。它是組合優化中最著名的問題之一，在一般情況下屬於 NP-hard，這意味著目前沒有已知算法能在多項式時間內解決所有實例。

什麼是 Held–Karp 算法？

Held–Karp 是一種動態規劃算法，能在 O(2ⁿ · n²) 時間和 O(2ⁿ · n) 內存中精確解決 TSP。它比暴力破解 (n factorial) 快得多，但仍呈指數級增長，因此在實踐中僅用於約 20 個城市以下的實例。此求解器在城市數量為 12 個或更少時使用 Held–Karp。

什麼是 2-opt 為什麼要使用它？

2-opt 是一種局部搜索啟發式算法，它反復從當前路徑中移除兩條邊，並以另一種可能的方式重新連接得到的兩條路徑。當新路徑更短時，則保留該交換。2-opt 在每次疊代中以多項式時間運行，並能穩定地找到與最佳路徑誤差在百分之幾以內的路徑，這就是為什麼它是處理較大 TSP 實例的經典首選啟發式算法。

我應該何時使用坐標與距離矩陣？

當您的城市位於平面上且具有直線距離時（例如地圖上的點、倉庫位置或電路板上的鑽孔），請使用坐標。當成對成本非歐幾里得時（例如機票價格、含路況的交通時間、單行道距離或不對稱成本），請使用距離矩陣。矩陣模式接受任何非負距離，甚至是不對稱的距離。

2-opt 解決方案是最佳的嗎？

不是，2-opt 返回的是 2-optimal 路徑，這意味著沒有任何單獨的一對邊可以通過交換產生更短的路線。這是一個局部最優解，在表現良好的實例上通常在全局最優解的百分之幾以內，但不能保證是全局最佳。對於小規模實例中可證明的最優路徑，請選擇 Held–Karp。

此工具支持不對稱距離矩陣嗎？

支持。在距離矩陣模式下，您可以輸入任何非負方陣，包括 D[i][j] 與 D[j][i] 不同的不對稱矩陣。Held–Karp 和 2-opt 都能正確處理不對稱矩陣。這對於涉及單行道、交通或受風向影響的飛行成本的現實世界路線規劃問題非常有用。

延伸閱讀

• 旅行推銷員問題 — 維基百科
• Held–Karp 算法 — 維基百科
• 2-opt — 維基百科
• 最近鄰算法 — 維基百科

其他相關工具:

進階數學計算:

• antilog計算機
• Beta函數計算機
• 二項式係數計算機
• 二項概率分布計算機
• 按位計算機
• 中央極限定理計算機
• 組合計算機 精選
• 互補誤差函數計算機
• 複數計算機
• 熵計算機
• 誤差函數計算機
• 指數衰減計算機-高精度
• 指數增長計算機 高精度
• 指數積分計算機
• 指數計算機-高精度
• 階乘計算機 精選
• 伽瑪功能計算機
• 黃金比例計算機
• 半衰期計算機
• 百分比增長率計算機 精選
• 排列計算機
• 泊松分佈計算機
• 多項式根計算機與詳細步驟
• 機率計算機
• 概率分布計算機
• 比例計算機 精選
• 二次公式計算機 精選
• 科學計算機 精選
• 科學記數法計算機
• 有效數字計算機 新
• 立方和計算機
• 連續數之和計算機
• 平方和計算機
• 真值表產生器 新
• 集合論計算機 新
• 韋恩圖產生器3集合 新
• 中國剩餘定理計算機 新
• 歐拉函數計算機 新
• 擴展歐幾里得演算法計算機 新
• 模乘逆元計算機 新
• 連分數計算機 新
• 戴克斯特拉最短路徑計算機 新
• 最小生成樹計算機 新
• 圖度數序列驗證器 新
• 錯排 子階乘計算機 新
• 斯特林數計算機 新
• 鴿巢原理計算機 新
• 馬可夫鏈穩態分布計算機 新
• 四捨五入計算機 新
• 負二項分布計算機 新
• 重複排列計算機 新
• 模冪運算計算機 新
• 原根計算機 新
• 布林代數化簡器 新
• 卡諾圖 (K-Map) 求解器 新
• 圖著色計算機 新
• 拓撲排序計算機 新
• 鄰接矩陣計算機 新
• 容斥原理計算機 新
• 線性規劃求解器 新
• 旅行推銷員問題求解器 (TSP) 新
• 漢密爾頓路徑檢查器 新