c++利用分支界限法实现旅行商问题

旅行商问题 (Travelling Salesman Problem, TSP) 是一个经典的组合优化问题，其目标是在给定的一组城市和每对城市之间的距离下，找到一条最短的路径，使得每个城市恰好被访问一次，最终回到起点。分支界限法是求解TSP问题的一种常用方法，其基本思路是将搜索空间划分为很多子空间，并通过剪枝策略来减少搜索的复杂度。

以下是C++实现TSP问题的分支界限法的代码：

#include <iostream>
#include <vector>
#include <algorithm>
#include <queue>
#include <cstring>
#include <cmath>
using namespace std;

const int INF = 1e9;
const int MAXN = 20;

struct Edge {
    int from;
    int to;
    int w;
    Edge(int f, int t, int ww) : from(f), to(t), w(ww) {}
    bool operator<(const Edge& e) const {
        return w > e.w;
    }
};

int n; // 城市数量
int d[MAXN][MAXN]; // 距离矩阵
int f[MAXN][1 << MAXN]; // 记忆化数组，f[i][S]表示i为当前节点，S为已经走过的状态时的最短路径长度
int g[MAXN][1 << MAXN]; // 保存i节点到S集合中所有节点的最短距离，用于剪枝
priority_queue<Edge> q; // 用于最小生成树
vector<int> nodes; // 节点集合，用于初始化

void init() {
    nodes.clear();
    for (int i = 0; i < n; ++i) {
        nodes.push_back(i);
        for (int j = 0; j < n; ++j) {
            cin >> d[i][j];
        }
    }
}

void prim(int s) { // 求解最小生成树
    bool vis[MAXN];
    memset(vis, false, sizeof(vis));
    vis[s] = true;
    for (int i = 1; i < n; ++i) {
        for (int j = 0; j < n; ++j) {
            if (vis[j]) {
                for (int k = 0; k < n; ++k) {
                    if (!vis[k]) {
                        q.push(Edge(j, k, d[j][k])); // 将不在集合中的节点加入队列
                    }
                }
            }
        }
        while (!q.empty()) {
            Edge e = q.top();
            q.pop();
            if (!vis[e.to]) { // 如果to节点不在集合中
                vis[e.to] = true;
                g[e.to][1 << s | 1 << e.to] = e.w; // 更新最短距离
                g[e.from][1 << s | 1 << e.to] = e.w;
                // 如果集合中有多个节点，需要更新最短距离
                for (int S = 0; S < (1 << n); ++S) {
                    if (g[e.to][S] > 0) {
                        g[e.to][S | 1 << e.to] = min(g[e.to][S | 1 << e.to], g[e.to][S] + e.w);
                        g[e.from][S | 1 << e.to] = min(g[e.from][S | 1 << e.to], g[e.from][S] + e.w);
                    }
                }
                break;
            }
        }
    }
}

int dfs(int u, int S) { // 分支界限搜索
    if (f[u][S] != INF) {
        return f[u][S];
    }
    if (S == (1 << n) - 1) { // 所有节点均已经遍历完毕
        return f[u][S] = d[u][0];
    }
    int res = INF;
    for (int i = 0; i < n; ++i) {
        if (!(S >> i & 1)) { // 如果i节点没有被访问过
            int tmp = g[u][S | 1 << i]; // 剪枝，如果到集合S中所有节点的最短距离之和都大于当前已知的最短路径长度，则不需要进行搜索
            if (f[i][S | 1 << i] != INF && f[u][S] + f[i][S | 1 << i] + tmp >= res) {
                continue;
            }
            res = min(res, dfs(i, S | 1 << i) + d[u][i]);
        }
    }
    return f[u][S] = res;
}

int main() {
    cin >> n;
    init();
    memset(f, INF, sizeof(f));
    memset(g, INF, sizeof(g));
    prim(0);
    cout << dfs(0, 1) << endl;
    return 0;
}

上述代码中，使用最小生成树求解每个节点到集合S中所有节点的最短距离，用于剪枝。在搜索过程中，如果到集合S中所有节点的最短距离之和已经大于当前已知的最短路径长度，则不需要进行搜索，这就是分支界限法的剪枝策略。