货郎担回溯法代码

以下是一个使用货郎担回溯法求解TSP问题的C++代码：

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

const int MAXN = 20;      // 最多20个城市
const int INF = 1e9;      // 无穷大

int n;                    // 城市数量
int dist[MAXN][MAXN];     // 距离矩阵

vector<int> path;         // 当前路径
bool vis[MAXN];           // 标记城市是否访问过

int ans = INF;            // 最短路径长度
vector<int> ansPath;      // 最短路径

// 计算两个城市之间的距离
int getDist(int i, int j) {
    int x1 = x[i], y1 = y[i];
    int x2 = x[j], y2 = y[j];
    return round(sqrt((x1-x2)*(x1-x2) + (y1-y2)*(y1-y2)));
}

// 货郎担回溯法
void dfs(int u, int cost) {
    // 如果当前路径长度已经大于最短路径长度，直接返回
    if (cost >= ans) {
        return;
    }
    // 如果所有城市都已经访问过，更新最短路径
    if (path.size() == n) {
        ans = cost;
        ansPath = path;
        return;
    }
    // 尝试访问所有未访问过的城市
    for (int i = 0; i < n; i++) {
        if (!vis[i]) {
            vis[i] = true;
            path.push_back(i);
            dfs(i, cost + dist[u][i]);
            path.pop_back();
            vis[i] = false;
        }
    }
}

int main() {
    // 输入城市数量和城市坐标
    cin >> n;
    for (int i = 0; i < n; i++) {
        cin >> x[i] >> y[i];
    }
    // 计算距离矩阵
    for (int i = 0; i < n; i++) {
        for (int j = 0; j < n; j++) {
            dist[i][j] = getDist(i, j);
        }
    }
    // 使用货郎担回溯法求解TSP问题
    vis[0] = true;
    path.push_back(0);
    dfs(0, 0);
    // 输出结果
    cout << "最短路径长度为：" << ans << endl;
    cout << "最短路径为：";
    for (int i = 0; i < ansPath.size(); i++) {
        cout << ansPath[i] << " ";
    }
    cout << endl;
    return 0;
}

在这个例子中，我们使用了递归函数dfs来实现货郎担回溯法。在dfs函数中，我们依次尝试访问所有未访问过的城市，并计算经过这些城市的路径长度。如果当前路径长度已经大于最短路径长度，直接返回；如果所有城市都已经访问过，更新最短路径。最后，输出最短路径长度和最短路径。需要注意的是，在实现中，我们使用了一个path数组来记录当前路径，一个vis数组来标记城市是否访问过。