回溯法 -- 旅行售货员问题

旅行售货员问题给定一个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::vectorstd::vectorint a; // int vernum 0; std::vectorint x; // 当前序列 {0,1,2,3,4} std::vectorint 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::vectorstd::vectorint 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!)