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

旅行商问题是一个经典的组合优化问题，其目的是找到一条路径，使得经过所有城市恰好一次的总路程最小。利用分支界限法可以很好地解决该问题。

以下是C++代码实现：

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

const int INF = 0x3f3f3f3f; // 无穷大
const int MAXN = 20; // 最大城市数

int n; // 总城市数
int e[MAXN][MAXN]; // 邻接矩阵
int ans = INF; // 最小路径长度
int vis[MAXN]; // 标记城市是否已访问

struct Node {
    int cur; // 当前城市编号
    int dis; // 当前路径长度
    int v[MAXN]; // 标记城市是否已访问
    bool operator<(const Node &a) const { // 重载小于运算符，用于优先队列排序
        return dis > a.dis;
    }
};

void dfs(int cur, int dis, int cnt) { // 普通 DFS
    if (cnt == n && e[cur][1] != INF) { // 若所有城市已访问完且最后一个城市与起点有通路，更新答案
        ans = min(ans, dis + e[cur][1]);
        return;
    }
    for (int i = 2; i <= n; i++) { // 枚举下一个城市
        if (vis[i] == 0 && e[cur][i] != INF && dis + e[cur][i] < ans) { // 若该城市未访问且与当前城市有通路，且当前路径长度小于当前最优解
            vis[i] = 1; // 标记该城市已访问
            dfs(i, dis + e[cur][i], cnt + 1); // 继续搜索
            vis[i] = 0; // 回溯，将该城市标记为未访问
        }
    }
}

void bfs() { // 分支界限法
    priority_queue<Node> q; // 优先队列，用于存储状态节点
    Node start;
    start.cur = 1;
    start.dis = 0;
    start.v[1] = 1;
    q.push(start); // 将起始状态节点入队
    while (!q.empty()) {
        Node u = q.top();
        q.pop();
        if (u.cur == 1 && u.dis == ans) { // 若搜索到起始节点且当前路径长度等于当前最优解，结束搜索
            break;
        }
        for (int i = 2; i <= n; i++) { // 枚举下一个城市
            if (u.v[i] == 0 && e[u.cur][i] != INF) { // 若该城市未访问且与当前城市有通路
                Node v;
                v.cur = i;
                v.dis = u.dis + e[u.cur][i];
                for (int j = 1; j <= n; j++) { // 将标记数组复制到新状态节点中
                    v.v[j] = u.v[j];
                }
                v.v[i] = 1; // 标记该城市已访问
                q.push(v); // 将新状态节点入队
            }
        }
    }
    cout << ans << endl; // 输出最优解
}

int main() {
    cin >> n;
    for (int i = 1; i <= n; i++) {
        for (int j = 1; j <= n; j++) {
            cin >> e[i][j];
            if (e[i][j] == 0) { // 若两个城市之间没有通路，则将其距离设为无穷大
                e[i][j] = INF;
            }
        }
    }
    // dfs(1, 0, 1); // 普通 DFS
    bfs(); // 分支界限法
    return 0;
}

代码中包含两种方法，一种是普通的 DFS，一种是利用优先队列实现的分支界限法。

其中，优先队列可以用来存储状态节点，每次从队列中取出路径长度最短的状态节点进行扩展，避免了不必要的搜索，提高了效率。利用优先队列实现的分支界限法是一种比较常用的解决旅行商问题的方法。