POJ 2907 Collecting Beepers：旅行商問題 (TSP) 暴力排列解法

題目大意

給定起點和 n ≤ 10 個目標點，求從起點出發訪問所有目標點（至少一次）並返回起點的最短路徑長度。曼哈頓距離。

暴力全排列

n ≤ 10，n! ≤ 3,628,800，可行。
步驟：

1. 預計算所有點對距離 dist[i][j]（含起點作為 0 號）。
2. 生成目標點索引數組 perm = [1,2,...,n]。
3. next_permutation 枚舉所有順序，計算路徑長 dist[0][perm[0]] + Σ dist[perm[i]][perm[i+1]] + dist[perm[n-1]][0]，取最小值。

C++ 代碼

#include 
using namespace std;
int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    int T; cin >> T;
    while (T--) {
        int W, H; cin >> W >> H; // 無用
        int sx, sy; cin >> sx >> sy;
        int n; cin >> n;
        vector x(n+1), y(n+1);
        x[0] = sx; y[0] = sy;
        for (int i = 1; i <= n; ++i) cin >> x[i] >> y[i];
        // 距離矩陣
        int dist[11][11];
        for (int i = 0; i <= n; ++i)
            for (int j = 0; j <= n; ++j)
                dist[i][j] = abs(x[i]-x[j]) + abs(y[i]-y[j]);
        // 枚舉排列
        vector perm(n);
        iota(perm.begin(), perm.end(), 1);
        int ans = INT_MAX;
        do {
            int sum = dist[0][perm[0]];
            for (int i = 0; i < n-1; ++i) sum += dist[perm[i]][perm[i+1]];
            sum += dist[perm[n-1]][0];
            ans = min(ans, sum);
        } while (next_permutation(perm.begin(), perm.end()));
        cout << "The shortest path has length " << ans << '\n';
    }
    return 0;
}

優化方向（大 n 時）

• 狀態壓縮 DP：dp[mask][last] O(n²2ⁿ)，n=15 可行。
• 最近鄰啟發式 + 2-opt 局部搜索（近似解）。
• 分支限界精確算法。

總結

POJ 2907 是「小規模 TSP 暴力排列」的教科書案例。n ≤ 10 時 next_permutation 簡潔高效；掌握 狀態壓縮 DP 可擴展至 n ≤ 15~20。同類題：UVA 10496、HDU 1562。