c++ 旅行商问题

旅行商问题（TSP）是一个著名的组合优化问题，它是指给定一个包含 n 个城市的地图，要求从其中选出 n 个城市，构成一条回路，使得这条回路经过每个城市恰好一次，并且总路程最短。

C++ 中可以使用动态规划或者回溯算法来解决旅行商问题。其中，动态规划算法的时间复杂度为 O(n^2 * 2^n)，回溯算法的时间复杂度则为 O(n!)。

以下是一个使用回溯算法来解决旅行商问题的 C++ 代码示例：

#include <bits/stdc++.h>
using namespace std;

const int N = 20;
int n, ans = INT_MAX;
int g[N][N], vis[N];

void dfs(int u, int dist) {
    if (u == n) {
        ans = min(ans, dist);
        return;
    }
    for (int i = 0; i < n; i++) {
        if (!vis[i]) {
            vis[i] = 1;
            dfs(u + 1, dist + g[u][i]);
            vis[i] = 0;
        }
    }
}

int main() {
    cin >> n;
    for (int i = 0; i < n; i++) {
        for (int j = 0; j < n; j++) {
            cin >> g[i][j];
        }
    }
    vis[0] = 1;
    dfs(1, 0);
    cout << ans << endl;
    return 0;
}

该代码中，使用邻接矩阵存储城市之间的距离，vis 数组用于标记已经访问过的城市。dfs 函数用于搜索每个城市的情况，并更新最短路径长度 ans。在主函数中，首先读入城市数量和距离矩阵，然后从第一个城市开始进行搜索，最后输出最短路径长度。