C# 解決旅行推銷員問題 (TSP)：N 點最短路徑的演算法選擇與實作策略

問題本質

給定 N 個點（城市），尋找遍歷所有點恰好一次並回到起點的最短迴路。這是經典的 旅行推銷員問題 (TSP)，屬於 NP-Hard 問題。N 稍大 (N > 20) 時，暴力窮舉 (N! 排列) 完全不可行。

演算法分級建議

C# 實作關鍵點

1. 距離矩陣預計算

double[,] dist = new double[N, N];
for (int i = 0; i < N; i++)
    for (int j = 0; j < N; j++)
        dist[i, j] = Distance(points[i], points[j]);

2. 遞歸/回溯模板 (小 N 精確解)

void TspDfs(int current, int visitedMask, double currentLen) {
    if (visitedMask == (1 << N) - 1) { // 全拜訪
        best = Math.Min(best, currentLen + dist[current, 0]);
        return;
    }
    for (int next = 0; next < N; next++) {
        if ((visitedMask & (1 << next)) == 0) {
            // 剪枝：若當前長度 + 剩餘最小生成樹下界 >= best，直接返回
            TspDfs(next, visitedMask | (1 << next), currentLen + dist[current, next]);
        }
    }
}

3. 2-opt 局部優化 (大 N 近似解核心)

bool improved = true;
while (improved) {
    improved = false;
    for (int i = 0; i < N; i++) {
        for (int k = i + 1; k < N; k++) {
            // 交換邊 (i,i+1) 和 (k,k+1) -> (i,k) 和 (i+1,k+1)
            double delta = dist[path[i], path[k]] + dist[path[i+1], path[(k+1)%N]]
                         - dist[path[i], path[i+1]] - dist[path[k], path[(k+1)%N]];
            if (delta < -1e-9) {
                Reverse(path, i+1, k);
                improved = true;
            }
        }
    }
}

工業級建議：直接用成熟庫

• Google OR-Tools (.NET NuGet: Google.OrTools)：內建世界級 TSP/VRP 求解器，支援約束、時間窗、多車輛，幾行代碼解決生產問題。
• Accord.NET / Math.NET Numerics：提供基礎優化演算法元件。

原答案參考連結補充

原最佳回答提供的 CSDN 部落格連結 (blog.csdn.net/ecttx/article/details/8372486) 可能已失效。建議搜尋關鍵字 "C# TSP Held-Karp" 或 "C# 2-opt algorithm" 獲取最新完整代碼範例。

總結

不要嘗試手寫 N 層巢狀迴圈或通用遞歸模板解決 TSP。根據 N 的大小選擇 精確演算法 (DP/分支限界) 或 近似演算法 (啟發式 + 2-opt)，生產環境優先整合 OR-Tools 等成熟求解器。