用c++ 回溯法解决旅行商问题

旅行商问题（TSP）是指给定一些城市和它们之间的距离，求出一条经过每个城市一次且只经过一次的最短回路。旅行商问题是一个NP-hard问题，暴力解法的时间复杂度是O(n!)，因此我们可以采用回溯算法来解决。

回溯算法是一种搜索算法，它通过不断地尝试每一种可能的情况，来找到问题的解。对于旅行商问题，我们可以用回溯算法来枚举每一种路径，然后选择最短的路径作为结果。

下面是用C++实现回溯法解决旅行商问题的代码：

#include <iostream>
#include <algorithm>
#include <vector>

using namespace std;

const int INF = 0x3f3f3f3f;

int n; // 城市数量
int minDist = INF; // 最小距离
int dist[20][20]; // 城市间距离
vector<int> path; // 路径

void dfs(int cur, int cost, vector<int>& visited) {
    if (path.size() == n) { // 找到一条路径
        minDist = min(minDist, cost + dist[cur][0]); // 更新最小距离
        return;
    }

    for (int i = 1; i < n; i++) {
        if (!visited[i]) { // 如果城市i未被访问
            visited[i] = 1; // 标记城市i已被访问
            path.push_back(i); // 将城市i加入路径
            dfs(i, cost + dist[cur][i], visited); // 继续搜索
            path.pop_back(); // 回溯
            visited[i] = 0; // 取消标记
        }
    }
}

int main() {
    cin >> n;

    // 输入城市间距离
    for (int i = 0; i < n; i++) {
        for (int j = 0; j < n; j++) {
            cin >> dist[i][j];
        }
    }

    // 初始化visited数组
    vector<int> visited(n);
    visited[0] = 1;

    // 从城市0开始搜索
    path.push_back(0);
    dfs(0, 0, visited);

    // 输出最小距离
    cout << minDist << endl;

    return 0;
}

在上面的代码中，我们定义了一个dfs函数来进行搜索，其中cur表示当前所在的城市，cost表示到达当前城市的花费，visited表示每个城市是否被访问过。在dfs函数中，我们首先判断是否找到了一条路径，如果是，就更新最小距离；否则，我们枚举所有未被访问的城市，将其加入路径中，继续搜索，然后回溯。最后，我们从城市0开始搜索，输出最小距离即可。

需要注意的是，这种解法的时间复杂度是O(n!)，当n较大时，会非常耗时，因此对于较大的问题，我们需要采用其他算法来解决。