# TSP 演算法策略與效能權衡分析
[TOC]

由於 $TSP$ 屬於 $NP\text{-hard}$ 問題，在計算理論上，我們無法在多項式時間內找到保證最佳的解（除非 $P = NP$）。因此，針對不同規模的問題與精確度需求，演算法被分為「精確解法」與「近似/啟發解法」。

---

### (一) 蠻力法 (Brute Force Method)

這是最直觀的解法，透過列舉所有可能的組合來尋找最小值。

* **核心邏輯**：
列出所有 $n$ 個城市的排列組合（取其中一個為起點，剩下的進行排列），總共會有 $\frac{(n-1)!}{2}$ 條不同的路徑（考慮對稱性）。
* **複雜度**：
時間複雜度為 $O(n!)$。
* **評析**：
當 $n=10$ 時，計算量尚可接受；但當 $n=20$ 時，$(19!)$ 的數量級已超過目前的運算極限。這僅適用於極小規模的問題。

---

### (二) 分支界定法 (Branch-and-Bound Method)

這是一種系統化搜索解空間的方法，利用「剪枝」來減少運算量。

* **核心邏輯**：
1. **分枝 (Branching)**：將問題拆解成子問題（例如：決定是否走某一段路）。
2. **界定 (Bounding)**：計算每個分枝的「下界 ($Lower \ Bound$)」。如果某分枝的下界已經大於目前已找到的最好路徑，則該分枝不可能包含最佳解。
3. **剪枝 (Pruning)**：捨棄該分枝，不再往下搜索。
* **複雜度**：
最壞情況仍為 $O(n!)$，但透過良好的下界估計函數，平均情況下比蠻力法快得多。
* **評析**：
這是精確演算法的核心，能保證找到最佳解，且通常能處理到 $n=40 \sim 100$ 左右的規模（視具體限制條件而定）。

---

### (三) 動態規劃 (Dynamic Programming)

經典的 $Held\text{-}Karp$ 演算法，利用「重疊子問題」來優化計算。

* **核心邏輯**：
定義狀態 $DP(S, i)$ 為：已經訪問過城市集合 $S$，且最後一個城市是 $i$ 的最短路徑長度。
透過遞迴關係式：
$$DP(S, i) = \min_{j \in S \setminus \{i\}} \{ DP(S \setminus \{i\}, j) + dist(j, i) \}$$
* **複雜度**：
時間複雜度為 $O(n^2 2^n)$。
* **評析**：
相較於蠻力法的階乘級成長，指數級成長大幅縮減了計算空間。然而，空間複雜度同樣達到 $O(n 2^n)$，因此當城市數量增加到一定程度時，記憶體將成為主要瓶頸。

---

### (四) 近似法與啟發式演算法 (Approximation & Heuristics)

當問題規模巨大（如 $n > 1000$），我們放棄「絕對最佳解」，轉而尋找「足夠好」的解。

* **核心邏輯**：
1. **近似法 (Approximation Algorithms)**：保證解與最佳解的差距在特定比例內（例如 $1.5\text{-approximation}$ 的 $Christofides$ 演算法）。
2. **啟發式/超啟發式 (Heuristics / Metaheuristics)**：如遺傳演算法 ($GA$)、模擬退火 ($SA$)、蟻群演算法 ($ACO$)。這類演算法透過隨機搜尋與迭代優化，在極短時間內產出高品質解。
* **複雜度**：
通常為多項式時間，如 $O(n^2)$ 或 $O(Generations \times Population)$。
* **評析**：
這是工業界最常用的解法，因為「時間成本」往往比「那 0.1% 的精度」更重要。

---

### 演算法綜合比較表

| 演算法 | 解的品質 | 時間複雜度 | 適用場景 |
| :--- | :--- | :--- | :--- |
| **蠻力法** | 絕對最佳解 | $O(n!)$ | 教學演示、極小規模 ($n < 10$) |
| **分支界定法** | 絕對最佳解 | $O(n!) \sim O(2^n)$ | 需要精確解的中小規模問題 |
| **動態規劃** | 絕對最佳解 | $O(n^2 2^n)$ | 經典演算法競賽、記憶體充足的情況 |
| **近似/啟發式** | 高品質次優解 | $O(poly(n))$ | **工業實務、智慧工廠排程、大規模路徑規劃** |

---

### 從理論到實作：為何選擇啟發式演算法？

既然最佳化版本的 $TSP$ 被證實為 **$NP\text{-hard}$**，這在工程實務上意味著一個殘酷的事實：隨著城市數量 $n$ 的增加，搜尋空間將面臨「組合爆炸」。

* **暴力搜尋的侷限**：當 $n=20$ 時，可能的路徑數已超過 $6 \times 10^{16}$，即便使用高效能工作站也難以在合理時間內窮舉。
* **精確演算法的代價**：雖然動態規劃（如 DP 或 Branch and Bound）能找到最優解，但其複雜度仍具備指數特性，難以應對工業級規模。

為了在運算成本與解的品質（Solution Quality）之間取得平衡，本專案採取了 **混合遺傳演算法 (Memetic Algorithm)** 架構：
1. **全域搜尋 (Global Search)**：透過遺傳演算法 (GA) 的多樣性，在廣大的搜尋空間中快速定位具備潛力的區域。
2. **局部開發 (Local Exploitation)**：引入 2-Opt 算子針對個體進行微調，彌補純 GA 收斂精準度不足的問題。

透過這種策略，我們成功將一個數學上的「難題」，轉化為工程上「可在多項式時間內獲得高品質滿意解」的專案實作。

---

### 🛠️ 工程決策：為何本專案選擇 Parallel GA + 2-Opt?

在分析完上述各類演算法後，針對本專案的目標與實際測試環境，我們做出了以下工程決策：

1. **應對規模化 (Scalability)**：
本專案的目標是處理 TSPLIB 中如 `ch150` (150個城市) 規模的問題。在這種規模下，動態規劃所需的 $O(2^{150})$ 空間與時間已遠遠超出硬體限制，因此啟發式演算法是唯一的選擇。

2. **平衡開發能力與搜尋範圍 (Exploration vs. Exploitation)**：
單純的 GA 容易在後期收斂緩慢（精確度不足）。因此我們引入 **2-Opt 局部搜尋** 作為遺傳運算子的一環，由 GA 負責廣域搜尋 (Global Search)，由 2-Opt 負責局部精煉 (Local Refinement)。

3. **利用多核優勢 (Parallel Computing)**：
啟發式演算法的缺點是需要大量迭代，但其「族群評估」具備高度的獨立性。透過 C++ **std::async** 進行平行化，我們能抵銷 GA 高計算量的缺點，在極短時間內獲得高品質解。

---