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

旅行商问题属于NP问题，因此在实际应用中无法找到最优解，只能利用分支界限法寻求一个较优解。下面是一个利用分支界限法实现TSP的C++代码示例：

#include<bits/stdc++.h>
using namespace std;
const int N=20;
int n,ans=1e9,dis[N][N],vis[N];
void dfs(int u,int step,int sum){
    if(step==n) ans=min(ans,sum+dis[u][1]); //更新最优解
    if(sum>=ans) return; //剪枝
    for(int i=2;i<=n;i++){
        if(vis[i]) continue;
        vis[i]=1;
        dfs(i,step+1,sum+dis[u][i]);
        vis[i]=0;
    }
}
int main(){
    cin>>n;
    for(int i=1;i<=n;i++)
        for(int j=1;j<=n;j++)
            cin>>dis[i][j];
    vis[1]=1;
    dfs(1,1,0); //从1号城市开始遍历，step=1，sum=0
    cout<<ans<<endl;
    return 0;
}

以上代码仅实现了基本的分支界限算法，还有很多优化方法可以使用，比如最小边界估算等。

相关问题

c++利用分支界限法实现旅行商问题并每行加上注释并且结果要有最短路径是什么以及最短路径的长度

以下是使用分支界限法实现旅行商问题的C++代码，每行都添加了注释：

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

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

int n; // 城市数量
int graph[MAXN][MAXN]; // 城市间距离矩阵
int visited[MAXN] = {0}; // 标记城市是否访问过
int ans = INF; // 最短路径长度
int path[MAXN]; // 最短路径

// 定义一个结构体，用于存储搜索状态
struct Node {
    int u; // 当前所在的城市
    int depth; // 搜索深度
    int cost; // 已经走过的路径长度
    int path[MAXN]; // 已经走过的路径
};

// 定义一个比较函数，用于优先队列的排序
struct cmp {
    bool operator() (const Node& a, const Node& b) {
        return a.cost > b.cost;
    }
};

// 分支界限算法
void TSP() {
    priority_queue<Node, vector<Node>, cmp> q; // 定义一个优先队列
    Node start = {0, 1, 0, {0}}; // 起点
    q.push(start); // 将起点压入队列
    while (!q.empty()) {
        Node cur = q.top(); // 取出队头元素
        q.pop(); // 弹出队头元素
        if (cur.depth == n && graph[cur.u][0] != INF) { // 已经走过所有城市，返回起点
            cur.path[cur.depth-1] = 0; // 最后一个城市的下一个城市一定是起点
            if (cur.cost + graph[cur.u][0] < ans) { // 更新最短路径
                ans = cur.cost + graph[cur.u][0];
                for (int i = 0; i < n; i++) {
                    path[i] = cur.path[i];
                }
            }
            continue; // 继续搜索
        }
        for (int i = 0; i < n; i++) { // 枚举下一个城市
            if (!visited[i] && graph[cur.u][i] != INF) { // 如果这个城市没有被访问过，并且和当前城市相邻
                visited[i] = 1; // 标记这个城市已经被访问过
                Node next = {i, cur.depth+1, cur.cost+graph[cur.u][i], {0}}; // 创建下一个状态
                for (int j = 0; j < cur.depth-1; j++) { // 复制之前走过的路径
                    next.path[j] = cur.path[j];
                }
                next.path[cur.depth-1] = i; // 记录当前城市
                q.push(next); // 将下一个状态压入队列
                visited[i] = 0; // 还原状态
            }
        }
    }
}

int main() {
    cin >> n;
    for (int i = 0; i < n; i++) {
        for (int j = 0; j < n; j++) {
            cin >> graph[i][j];
            if (graph[i][j] == -1) { // 无穷大
                graph[i][j] = INF;
            }
        }
    }
    visited[0] = 1; // 起点已经被访问过
    TSP(); // 分支界限算法
    cout << "最短路径是：";
    for (int i = 0; i < n; i++) {
        cout << path[i] << " ";
    }
    cout << "0" << endl; // 最后一个城市的下一个城市一定是起点
    cout << "最短路径长度是：" << ans << endl;
    return 0;
}

以上代码实现了旅行商问题的求解，其中使用了分支界限算法。程序先读入城市间距离矩阵，然后从起点开始搜索，遍历所有可能的路径，并记录最短路径。最后输出最短路径以及最短路径的长度。

注意，如果城市间距离为无穷大，则要将其转化为一个较大的数，这里使用的是 `INF`。同时，最后一个城市的下一个城市一定是起点，因此最终输出路径时需要手动添加。

旅行商问题c++并输出最短路径，用分支限界法

旅行商问题（TSP）是一个经典的组合优化问题，其目标是在所有城市之间找到最短的回路。分支限界法是一种常用的解决TSP问题的方法。下面是一个用C++实现TSP问题并输出最短路径的代码。

#include<iostream>
#include<algorithm>
#include<cstring>
#include<queue>
using namespace std;
const int INF=1e9;
const int MAXN=15;
int n;
int w[MAXN][MAXN];
int best[MAXN];
int ans=INF;
struct node{
    int u,dis,head;//当前访问的节点，当前路径长度，已经访问的节点集合
    bool operator < (const node &rhs)const{
        return dis>rhs.dis;
    }
};
void dfs(int u,int dis,int head[]){//DFS求最优解
    if(dis>=ans)return;
    if(u==n){
        if(dis+w[head[u-1]][1]<ans){
            ans=dis+w[head[u-1]][1];
            for(int i=1;i<=n;i++)best[i]=head[i];
        }
        return;
    }
    for(int i=u;i<=n;i++){
        swap(head[u],head[i]);
        dfs(u+1,dis+w[head[u-1]][head[u]],head);
        swap(head[u],head[i]);
    }
}
void bfs(){//BFS求最优解
    priority_queue<node> q;
    q.push((node){1,0,1});
    while(!q.empty()){
        node t=q.top();
        q.pop();
        if(t.dis>=ans)break;
        if(t.u==n){
            if(t.dis+w[t.head][1]<ans){
                ans=t.dis+w[t.head][1];
                for(int i=1;i<=n;i++)best[i]=t.head;
            }
            continue;
        }
        for(int i=2;i<=n;i++){
            if((t.head&(1<<i-1))==0){
                q.push((node){i,t.dis+w[t.head][i],t.head|(1<<i-1)});
            }
        }
    }
}
int main(){
    cin>>n;
    for(int i=1;i<=n;i++){
        for(int j=1;j<=n;j++){
            cin>>w[i][j];
        }
    }
    int head[MAXN];
    for(int i=1;i<=n;i++)head[i]=i;
    dfs(2,0,head);
    cout<<ans<<endl;
    for(int i=1;i<=n;i++)cout<<best[i]<<" ";
    cout<<endl;
    ans=INF;
    bfs();
    cout<<ans<<endl;
    for(int i=1;i<=n;i++)cout<<best[i]<<" ";
    cout<<endl;
    return 0;
}

该代码中，我们先通过DFS和BFS两种方式求解TSP问题，然后输出最短路径。其中，DFS方法通过不断交换节点的位置，遍历所有可能路径，并记录最优解。BFS方法则使用优先队列，每次取出路径长度最短的节点进行拓展，并记录最优解。