回溯法写旅行售货员问题C++实现

好的，旅行售货员问题是一个经典的组合优化问题，可以使用回溯法进行求解。下面是一个基于C++的回溯法实现：

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

using namespace std;

// 计算当前路径的长度
int calcDistance(vector<int>& path, vector<vector<int>>& graph) {
    int res = 0;
    for (int i = 0; i < path.size() - 1; i++) {
        res += graph[path[i]][path[i + 1]];
    }
    return res + graph[path[path.size() - 1]][path[0]];
}

void backtrack(vector<int>& path, vector<vector<int>>& graph, vector<int>& visited, int& minDist) {
    // 如果当前路径已经包含所有节点，则计算路径长度并更新最小值
    if (path.size() == graph.size()) {
        minDist = min(minDist, calcDistance(path, graph));
        return;
    }

    // 遍历所有未访问的节点
    for (int i = 0; i < graph.size(); i++) {
        if (visited[i]) continue;
        visited[i] = 1;
        path.push_back(i);
        backtrack(path, graph, visited, minDist);
        path.pop_back();
        visited[i] = 0;
    }
}

int main() {
    vector<vector<int>> graph = {
        {0, 2, 9, 10},
        {1, 0, 6, 4},
        {15, 7, 0, 8},
        {6, 3, 12, 0}
    };

    vector<int> path = { 0 };
    vector<int> visited(graph.size(), 0);
    visited[0] = 1;
    int minDist = INT_MAX;
    backtrack(path, graph, visited, minDist);
    cout << "Min distance: " << minDist << endl;
    return 0;
}

在这个实现中，我们使用一个`path`变量来记录当前遍历的路径，使用一个`visited`数组来记录哪些节点已经被访问过。在每次回溯时，我们遍历所有未访问的节点，将其加入到路径中，并递归调用回溯函数。当路径包含所有节点时，我们计算路径长度并更新最小值。在回溯过程中，我们需要记得恢复状态，即在返回时从路径中移除当前节点，并设置其为未访问。