旅行商问题c++回溯法

旅行商问题是一个NP难问题，可以使用回溯法进行求解。下面是一个使用C++实现的回溯法解决旅行商问题的示例代码：

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

using namespace std;

const int INF = 0x3f3f3f3f;

int n; // 城市数量
int dist[20][20]; // 城市之间的距离
vector<int> path; // 当前路径
vector<int> bestPath; // 最优路径
int bestDist = INF; // 最优路径长度

void backtrack(int curDist) {
    if (path.size() == n) { // 所有城市已经遍历完
        curDist += dist[path.back()][path.front()]; // 回到起点
        if (curDist < bestDist) { // 更新最优路径
            bestDist = curDist;
            bestPath = path;
        }
        return;
    }

    for (int i = 0; i < n; i++) {
        if (find(path.begin(), path.end(), i) == path.end()) { // 当前城市未访问过
            int nextDist = curDist + dist[path.back()][i]; // 计算距离
            if (nextDist < bestDist) { // 剪枝
                path.push_back(i); // 标记为已访问
                backtrack(nextDist); // 继续搜索
                path.pop_back(); // 恢复状态
            }
        }
    }
}

int main() {
    cin >> n;

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

    // 从第一个城市开始遍历
    path.push_back(0);
    backtrack(0);

    // 输出最优路径和最优路径长度
    cout << "Best Path: ";
    for (int i = 0; i < n; i++) {
        cout << bestPath[i] << " ";
    }
    cout << endl << "Best Distance: " << bestDist << endl;

    return 0;
}

这个代码使用了回溯法对旅行商问题进行求解，通过剪枝来优化搜索效率。在代码中，`dist`数组表示城市之间的距离，`path`表示当前遍历的路径，`bestPath`表示最优路径，`bestDist`表示最优路径长度。在`backtrack`函数中，首先判断是否已经遍历完了所有城市，如果是则比较当前路径长度与最优路径长度，如果更短则更新最优路径。然后遍历所有未访问的城市，计算到该城市的距离，如果小于最优路径长度则继续搜索该城市，否则剪枝。最后输出最优路径和最优路径长度即可。