旅行商问题

描述

给定一组城市和每对城市之间的火车票的价钱，找到每个城市只访问一次并返回起点的最小车费花销（城市总数 ）。

分析

记这 个城市为 ，第一次需要从 中选择一个城市，第二次从剩下的 个城市中选择一个...，一直到第 次仅剩一个城市可供选择，一共有 种可能的情况。考虑动态规划的解法，建立一个数组 记录从城市 出发，访问一个城市集合 中的每个城市一次并最终返回城市 所需的最小车费。我们最终要求的就是 {}， 数组第一维可以直接用下标 表示城市 ，难点在于第二维对城市集合的表示。我们要表示的是集合 及其所有子集，包括空集一共有 种情况，不难发现， ~ 每一个数的二进制表示都可以表示其中一种集合， 表示空集， 二进制表示是 个 ，恰好可以表示。我们从 出发，从 遍历到 选择其中一个 使得 {} 最小，迭代这个过程直至 的第二维为空集，其中 ，表示从 返回 。上面描述的是正向推导路径的过程，实际上我们的求值顺序是反向的，以确保后面可以用上前面所求的结果。

代码

#include <bits/stdc++.h>

using namespace std;

const int N = 25;
int a[N][N];

// 旅行商问题
void initDp(vector<vector<int>>& dp, int n, int m) {
    // 先处理第0列，表示直接从当前城市返回起点城市
    for(int i = 0; i < n; i++) {
        dp[i][0] = a[i][0];
    }

    // 从第一列 {1} 到最后一列 {1,2,...,n-1}
    for(int j = 1; j < m; j++) {
        int p = 0; // 用于判断的指针
        for(int i = 0; i < n; i++) {
            dp[i][j] = INT_MAX;
            if(p & j) continue; // 集合中存在当前dp的起点i

            // 遍历 j 所表示的集合
            int p2 = 1; int k = 1;
            while(p2 <= j) {
                if(p2 & j) {  // 表示 k 在集合中
                    dp[i][j] = min(dp[i][j], a[i][k] + dp[k][j-p2]);
                }
                p2 = (p2 << 1); k++;
            }

            p = (p << 1); // 指针右移
        }
    }
}

int main() {
    int n; cin >> n;
    for(int i = 0; i < n; i++) {
        for(int j = 0; j < n; j++) {
            cin >> a[i][j];  // 可以理解为边(i, j)的权重
        }
    }

    int m = (1 << (n-1)); // m = 2^(n-1)，表示除起点外(n-1)个城市的组合数
    // 0 ~ m-1 的二进制表示恰好对应集合[1 ~ n-1]的一种选择情况
    vector<vector<int>> dp(n, vector<int>(m, 0));
    initDp(dp, n, m);  // 初始化dp数组

    cout << dp[0][m-1] << '\n';  // 最小费用

    // 在得到dp数组的情况下，正向推导一条最优路径
    int h = m-1;
    int pre = 0; cout << pre;
    while(h) {
        int minV = INT_MAX, minK = 0;
        int p2 = 1; int k = 1;

        // 遍历 h 表示的集合，选取其中达到最小值的节点
        while(p2 <= h) {
            if((p2 & h) && a[pre][k] + dp[k][h-p2] < minV) {  // 表示 k 在集合中
                minV = a[pre][k] + dp[k][h-p2];
                minK = k;
            }
            p2 = (p2 << 1); k++;
        }

        cout << " -> " << minK;
        h -= (1 << (minK-1));
        pre = minK;
    }
    return 0;
}