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

旅行商问题（TSP）是一个经典的组合优化问题，它要求一个旅行商从起点出发，经过所有城市恰好一次，最终回到起点，使得走过的总路程最短。

分支界限法是一种解决TSP问题的有效算法。它的基本思路是将TSP问题转化为一个树形结构，每个节点表示旅行商在当前已经走过的路径上的位置。通过对当前节点的限定条件进行分支，生成子节点，将问题规模不断缩小，直到找到一个可行解或者证明无解。

以下是一份c++代码，实现了TSP问题的分支界限法求解：

#include<iostream>
using namespace std;

const int MAXN = 20; // 最大城市数
const int INF = 0x3f3f3f3f; // 无穷大
int n; // 城市数
int a[MAXN][MAXN]; // 距离矩阵
bool vis[MAXN]; // 标记城市是否已经被访问

int ans = INF; // 当前最优解
int path[MAXN]; // 当前路径
int cur_dis = 0; // 当前路径长度

void dfs(int cur)
{
    if(cur_dis >= ans) return; // 前面已经搜索到更优解，剪枝

    if(cur == n)
    {
        ans = cur_dis + a[path[n-1]][path[0]]; // 更新最优解
        return;
    }

    for(int i=0;i<n;i++)
    {
        if(!vis[i])
        {
            vis[i] = true;
            path[cur] = i;

            cur_dis += a[path[cur-1]][i];
            dfs(cur+1);
            cur_dis -= a[path[cur-1]][i];

            vis[i] = false;
        }
    }
}

int main()
{
    cin>>n;
    for(int i=0;i<n;i++)
    {
        for(int j=0;j<n;j++)
        {
            cin>>a[i][j];
        }
    }

    vis[0] = true;
    path[0] = 0;
    dfs(1);

    cout<<ans<<endl;

    return 0;
}

这份代码中，我们通过dfs函数实现了TSP问题的分支界限法求解。在dfs函数中，我们先对当前节点的限定条件进行判断，如果当前路径已经比之前搜索到的最优解长，则直接返回。如果当前节点是最后一个节点，则更新最优解。否则，我们枚举所有未被访问的城市，生成子节点，并继续进行搜索。在搜索的过程中，我们用vis数组记录哪些城市已经被访问，path数组记录当前路径，cur_dis记录当前路径长度。

代码中的时间复杂度为O(n!)，空间复杂度为O(n)，当n较小时可以得到较好的结果，但是当n较大时会出现时间复杂度过高的问题，需要进一步优化算法。