用C++写旅行商问题的代码

旅行商问题（Traveling Salesman Problem，TSP）是计算机科学中一个经典的组合优化问题，其目标是在所有城市之间找到一条最短的回路，使得每个城市恰好被访问一次。以下是使用 C++ 实现旅行商问题的代码。

#include<iostream>
#include<cstring>
using namespace std;

const int maxn = 20;      // 最大城市数量
const int inf = 0x3f3f3f3f;  // 无穷大

int n;   // 城市数量
int dist[maxn][maxn];   // 各城市之间的距离
int dp[1<<maxn][maxn];  // 记忆化数组

// 计算从起点start出发，经过vis集合中的所有城市，最终到达end城市的最短路径长度
int dfs(int vis, int start)
{
    if(vis == (1<<n)-1)    // 所有城市都已经访问过了（vis是一个二进制数，表示哪些城市已经被访问过）
        return dist[start][0];  // 返回从终点0到起点start的距离

    if(dp[vis][start] != -1)   // 如果已经计算过了，则直接返回记忆化数组中的值
        return dp[vis][start];

    int ans = inf;
    for(int i = 0; i < n; i++)   // 枚举下一个要访问的城市i
    {
        if((vis&(1<<i)) == 0)   // 如果城市i还没有访问过
        {
            int d = dist[start][i] + dfs(vis|(1<<i), i);   // 计算从start到i的距离，加上从i出发访问其他城市的最短路径长度
            ans = min(ans, d);   // 取最小值
        }
    }
    dp[vis][start] = ans;   // 记录结果到记忆化数组中
    return ans;
}

int main()
{
    memset(dp, -1, sizeof(dp));   // 初始化记忆化数组为-1
    cin >> n;
    for(int i = 0; i < n; i++)
        for(int j = 0; j < n; j++)
            cin >> dist[i][j];

    int ans = dfs(1, 0);   // 从起点0开始，访问所有城市的最短路径长度
    cout << ans << endl;
    return 0;
}

在这个实现中，我们使用记忆化搜索来求解旅行商问题。具体来说，我们定义状态 `dp[vis][start]` 表示当前已经访问过的城市集合为 `vis`，当前所在城市为 `start`，从这里出发访问剩下城市的最短路径长度。在每个状态中，我们枚举下一个要访问的城市 `i`，计算从 `start` 到 `i` 的距离，加上从 `i` 出发访问其他城市的最短路径长度，然后取最小值。最终，我们从起点0开始，访问所有城市的最短路径长度即为 `dp[1][0]`。