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

旅行商问题是一个经典的NP完全问题，它的解法有很多种，其中一种是利用分支界限法。

以下是C++代码实现：

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

const int MAXN = 20;
const int INF = 0x3f3f3f3f;

int n; // 城市数量
int dis[MAXN][MAXN]; // 城市间距离矩阵
int ans = INF; // 最小路径长度

// 分支界限法
void BranchBound(int u, int d, int len, int vis[])
{
    // 当前路径长度已超过最小路径长度，剪枝
    if (len >= ans) return;

    // 所有城市都已访问过，更新最小路径长度
    if (u == n)
    {
        ans = len;
        return;
    }

    // 建立子节点队列
    priority_queue<pair<int, int>> q;
    for (int i = 1; i <= n; ++i)
    {
        if (vis[i] == 0)
        {
            q.push(make_pair(dis[d][i], i));
        }
    }

    // 访问子节点
    while (!q.empty())
    {
        int v = q.top().second;
        q.pop();

        vis[v] = 1;
        BranchBound(u + 1, v, len + dis[d][v], vis);
        vis[v] = 0;
    }
}

int main()
{
    // 读入城市数量和距离矩阵
    cin >> n;
    for (int i = 1; i <= n; ++i)
    {
        for (int j = 1; j <= n; ++j)
        {
            cin >> dis[i][j];
        }
    }

    // 初始化访问数组
    int vis[MAXN];
    memset(vis, 0, sizeof(vis));
    vis[1] = 1;

    // 分支界限法求解
    BranchBound(1, 1, 0, vis);

    // 输出结果
    cout << ans << endl;

    return 0;
}

在以上代码中，我们使用了一个优先队列来存储当前节点的子节点，并按照距离从小到大排序，每次访问距离最近的子节点。这样做的目的是尽可能快地找到最优解，从而加速算法的运行。

分支界限法的核心思想是通过剪枝来减少搜索空间，从而提高算法的效率。在本题中，我们使用了两个剪枝：

1. 当前路径长度已超过最小路径长度，剪枝；
2. 所有城市都已访问过，更新最小路径长度。

这两个剪枝可以有效地减少搜索空间，提高算法的效率。