旅行售货员问题
给定一个n 个顶点的带权无向完全图 G=(V, E, w)，其中顶点代表城市，边的权值 w(i,j) 代表从城市 i 到城市 j 的距离（w(i,j)>0，且 w(i,j)=w(j,i)）。
要求：
找到一条从顶点 1（起点城市）出发，经过其余所有 n-1 个顶点各一次，最后回到起点 1的周游路线；
使得这条路线的总权值（总路程）最小。
代码求解
class TraveLing { private: std::vector<std::vector<int> > a; // int vernum = 0; std::vector<int> x; // 当前序列 {0,1,2,3,4} std::vector<int> bestx; // 当前最有序列 int cc; // 当前费用 int bestc; // 当前最优费用 void PrintVecX() { for (int i = 1; i <= vernum; ++i) { printf("%5d", x[i]); } printf("\n-----------------\n"); } void BackTrack(int i) { if (i == vernum) { if (a[x[i-1]][x[i]] != INT_MAX && a[x[i]][x[1]] != INT_MAX && (cc + a[x[i - 1]][x[i]] + a[x[i]][x[1]]) < bestc) { bestx = x; bestc = cc + a[x[i - 1]][x[i]] + a[x[i]][x[1]]; } } else { for (int j = i; j <= vernum; ++j) { if(a[x[i-1]][x[j]] != INT_MAX && (cc + a[x[i-1]][x[j]]) < bestc || bestc == INT_MAX ) { std::swap(x[i], x[j]); cc += a[x[i - 1]][x[i]]; BackTrack(i + 1); cc -= a[x[i - 1]][x[i]]; std::swap(x[i], x[j]); } } } } public: TraveLing() {} ~TraveLing() {} void PrintVec() const { for (int i = 1; i <= vernum; ++i) { printf("%5d", bestx[i]); } printf("%5d", bestx[1]); printf("\n-----------------\n"); } int TSP(const std::vector<std::vector<int> >& aa, int n) { a = aa; vernum = n; x.resize(n + 1, 0); for (int i = 1; i <= vernum; ++i) { x[i] = i; } bestc = INT_MAX; BackTrack(2); return bestc; } }; 固定起点，深度优先枚举所有路线，用剪枝减少搜索，回溯尝试所有可能，最终找到最短回路
时间复杂度：O (n!)
