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

旅行商问题（Traveling Salesman Problem, TSP）是一个经典的组合优化问题，其目标是求解一个给定的城市集合中所有城市之间的最短路径，并且每个城市只能被经过一次。分支界限法是一种解决TSP问题的常用方法，其基本思路是通过不断分割问题的搜索空间，缩小搜索范围，从而找到最优解。

以下是使用C++语言实现TSP问题的分支界限法的代码示例：

#include<iostream>
#include<cstdio>
#include<cstdlib>
#include<cstring>
using namespace std;
const int MAXN=20;
const int INF=0x3f3f3f3f;
int n,d[MAXN][MAXN],ans=INF;//n表示城市的数量，d[i][j]表示第i个城市到第j个城市的距离
bool vis[MAXN];//记录城市是否已经被访问
void dfs(int u,int cost,int depth)
{
    if(depth==n)//所有城市都已被访问
    {
        ans=min(ans,cost+d[u][1]);//更新答案
        return;
    }
    if(cost>=ans)//当前路径已经超过了当前最优解，返回
        return;
    for(int i=2;i<=n;i++)
        if(!vis[i])
        {
            vis[i]=true;
            dfs(i,cost+d[u][i],depth+1);//继续搜索
            vis[i]=false;
        }
}
int main()
{
    scanf("%d",&n);
    for(int i=1;i<=n;i++)
        for(int j=1;j<=n;j++)
            scanf("%d",&d[i][j]);
    vis[1]=true;//从第一个城市开始
    dfs(1,0,1);//从第一个城市开始，当前代价为0，已经访问了1个城市
    printf("%d\n",ans);//输出最优解
    return 0;
}

在这个代码中，dfs函数表示搜索当前状态的所有可能情况，并且更新答案。vis数组记录城市是否已经被访问。如果所有城市都已经被访问，更新答案；如果当前路径已经超过了当前最优解，返回；否则继续搜索。最后输出最优解。

需要注意的是，这个代码仅适用于城市数量比较少的情况。当城市数量增加时，分支界限法的时间复杂度会非常高，需要使用其他更加高效的算法进行求解。