旅行商问题回溯法算法思想C++

旅行商问题是一个经典的组合优化问题，它的目标是找到一条路径，经过所有城市并回到起点，使得路径长度最短。回溯法是求解旅行商问题的一种常见算法。

回溯算法的基本思想是：从问题的某一种状态开始搜索，每次搜索时先找到一个可行解，然后再找到下一个状态，继续搜索，直到找到问题的最优解为止。如果搜索到某一步发现不行，就回溯到上一步，从而寻找其他可行解。

下面是使用回溯法求解旅行商问题的C++代码：

#include <iostream>
#include <vector>
#include <algorithm>
using namespace std;

const int INF = 0x3f3f3f3f;

int n; // 城市个数
int graph[20][20]; // 图的邻接矩阵
vector<int> path; // 存放路径
int minDist = INF; // 存放最短路径长度

void TSP(int cur, int dist, vector<int>& visited) {
    if (cur == n) { // 所有城市已经遍历完，更新最短路径
        if (dist + graph[path[n - 1]][path[0]] < minDist) {
            minDist = dist + graph[path[n - 1]][path[0]];
        }
        return;
    }
    for (int i = 0; i < n; i++) {
        if (!visited[i]) { // 如果城市i没有被遍历过
            visited[i] = 1; // 标记城市i为已遍历
            path.push_back(i); // 将城市i加入路径
            TSP(cur + 1, dist + graph[path[cur - 1]][i], visited); // 继续遍历下一个城市
            path.pop_back(); // 回溯，将城市i从路径中删除
            visited[i] = 0; // 标记城市i为未遍历
        }
    }
}

int main() {
    cin >> n;
    for (int i = 0; i < n; i++) {
        for (int j = 0; j < n; j++) {
            cin >> graph[i][j];
        }
    }
    vector<int> visited(n, 0); // 初始化为未遍历
    visited[0] = 1; // 从第一个城市开始遍历
    path.push_back(0); // 将第一个城市加入路径
    TSP(1, 0, visited); // 从第二个城市开始遍历
    cout << minDist << endl;
    return 0;
}

这段代码中，TSP函数是核心函数，它的参数cur表示当前已经遍历的城市个数，dist表示当前路径长度，visited表示每个城市是否已经被遍历过。在函数中，我们使用for循环遍历每个城市，如果一个城市没有被遍历过，就将它加入路径中，继续遍历下一个城市，直到所有城市都被遍历过，然后更新最短路径长度。如果一个城市已经被遍历过，就跳过它，继续遍历下一个城市，直到所有城市都被遍历过或者找到了更优的路径。在回溯过程中，我们需要将当前城市从路径中删除，并将它标记为未遍历。