旅行商问题 （分枝定界）

#include <iostream>
#include <bits/stdc++.h>
using namespace std;
int G[10][10];
int bestp;
int bestx[10];
int n;
//层数
struct Node
{int weight;int level;int x[10];Node(){memset(x, 0, sizeof(x));}Node(int _weight, int _level){weight = _weight;level = _level;}
};
void Tra_bfs()
{Node newnode, livenode;newnode = Node(0, 2);priority_queue<Node> q;// priority_queuefor (int i = 1; i <= n; i++){newnode.x[i] = i;}q.push(newnode);while (!q.empty()){livenode = q.top();int t = livenode.level;if (t == n){ // 其实是倒数第二个节点if (livenode.weight + G[livenode.x[n - 1]][livenode.x[n]] + G[livenode.x[n]][1] < bestp){bestp = livenode.weight + G[livenode.x[n - 1]][livenode.x[n]] + G[livenode.x[n]][1];}continue;}if (livenode.weight > bestp)continue;for (int j = t; j <= n; j++){// 还要有一个判断有无连接int w = livenode.weight + G[livenode.x[t - 1]][livenode.x[j]];// 注意这里是  t-1 并不是 tNode lnode;lnode = Node(w, t + 1);for (int k = 1; k <= n; k++){lnode.x[k] = livenode.x[k];}swap(lnode.x[t], lnode.x[j]);if (w < bestp){q.push(lnode);}}}
}
void __init(){// 初始化函数 
}
int main()
{// Node 的level 指的是节点和选择拓展路径是有区别的 
}

主要就是正确理解解空间的拓展即可。

参考文档：
《趣学算法》