用C++写分支定界法——旅行商(TSP)问题的代码

好的，以下是一个用 C++ 实现的分支定界法解决旅行商问题（TSP）的代码。

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

using namespace std;

const int INF = 1e9;
const int MAX_N = 10;

int n; // 城市数量
int dist[MAX_N][MAX_N]; // 城市间距离矩阵
int best_dist = INF; // 最优解
int best_path[MAX_N]; // 最优路径
bool vis[MAX_N]; // 标记每个城市是否被访问

// 定义状态结构体
struct Node {
    int d; // 当前已经走过的距离
    int path[MAX_N]; // 当前已经走过的路径
    int level; // 当前搜索的层数
    bool vis[MAX_N]; // 标记每个城市是否被访问

    bool operator<(const Node &other) const {
        return d > other.d; // 按照距离从小到大排序
    }
};

// 计算从城市i到城市j的距离
int calc_dist(int i, int j) {
    // 这里使用无向图，所以dist[i][j]和dist[j][i]的值相同
    return dist[i][j];
}

// 分支定界法搜索
void BranchAndBound() {
    // 初始化起点
    Node start;
    start.d = 0;
    start.level = 0;
    start.path[0] = 0; // 起点为0号城市
    start.vis[0] = true;

    priority_queue<Node> q;
    q.push(start);

    while (!q.empty()) {
        Node cur = q.top();
        q.pop();

        // 如果当前路径已经超过了最优解，剪枝
        if (cur.d >= best_dist) continue;

        // 如果已经搜索到叶子节点，更新最优解
        if (cur.level == n - 1) {
            int last_city = cur.path[n - 1];
            cur.d += calc_dist(last_city, 0);
            if (cur.d < best_dist) {
                best_dist = cur.d;
                for (int i = 0; i < n; i++) {
                    best_path[i] = cur.path[i];
                }
            }
            continue;
        }

        // 枚举下一个城市的所有可能
        for (int i = 1; i < n; i++) {
            if (cur.vis[i]) continue;
            Node next;
            next.level = cur.level + 1;
            next.d = cur.d + calc_dist(cur.path[cur.level], i);
            for (int j = 0; j < n; j++) {
                next.path[j] = cur.path[j];
                next.vis[j] = cur.vis[j];
            }
            next.path[next.level] = i;
            next.vis[i] = true;
            q.push(next);
        }
    }
}

int main() {
    // 读入城市数量
    cin >> n;

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

    // 开始搜索
    BranchAndBound();

    // 输出最优解
    cout << "Best distance: " << best_dist << endl;
    cout << "Best path: ";
    for (int i = 0; i < n; i++) {
        cout << best_path[i] << " ";
    }
    cout << endl;

    return 0;
}

以上就是一个用 C++ 实现的分支定界法解决旅行商问题的代码。