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

旅行商问题（Traveling Salesman Problem，简称TSP）是指给定一些城市和每对城市之间的距离，求解访问每一座城市一次并回到起始城市的最短回路。这是一个著名的NP完全问题，通常采用回溯法求解。

回溯法是一种渐进式寻找并构建问题解的策略。它通过递归地搜索所有可能的解，找到问题的最优解或所有解。对于TSP问题，回溯法的基本思路是：从起始点开始，尝试一条路径上的每个城市，直到访问了所有城市，然后返回起始点。在每个城市上，尝试所有可能的下一步，并记录当前的最短路径。

以下是c++代码实现：

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

using namespace std;

const int MAXN = 20; // 最大城市数
int n; // 城市数
int graph[MAXN][MAXN]; // 距离矩阵
int bestPath[MAXN]; // 最短路径
int bestLength = INT_MAX; // 最短路径长度
bool visited[MAXN]; // 已访问标记

void dfs(int u, int length, int depth) {
    if(depth == n) { // 访问完所有城市
        if(length + graph[u][0] < bestLength) { // 更新最短路径
            bestLength = length + graph[u][0];
            for(int i = 0; i < n; i++) {
                bestPath[i] = visited[i] ? i : -1;
            }
        }
        return;
    }

    // 尝试所有可能的下一步
    for(int v = 1; v < n; v++) {
        if(!visited[v]) {
            visited[v] = true;
            dfs(v, length + graph[u][v], depth + 1);
            visited[v] = false;
        }
    }
}

int main() {
    cin >> n;

    // 输入距离矩阵
    for(int i = 0; i < n; i++) {
        for(int j = 0; j < n; j++) {
            cin >> graph[i][j];
        }
    }

    // 从第一个城市开始搜索
    visited[0] = true;
    dfs(0, 0, 1);

    // 输出最短路径
    cout << "Best path: ";
    for(int i = 0; i < n; i++) {
        cout << bestPath[i] << " ";
    }
    cout << endl;
    cout << "Best length: " << bestLength << endl;

    return 0;
}

该代码使用了深度优先搜索（DFS）实现回溯法，时间复杂度为O(n!)，因此只适用于小规模问题。对于大规模问题，需要使用更高效的算法，如动态规划、遗传算法等。