引用之前ACM博客状压DP一文对于TSP问题的描述： 经典的TSP可以描述为：一个商品推销员要去若干个城市推销商品，该推销员从一个城市出发，需经过所有城市后，回到起点。应该如何选择路线，使得总行程距离最短。从图论的观点来看是，该问题实质是在一个有权完全无向图中找一个权值最小的哈密顿回路。 大部分TSP问题都是NP-hard问题，即没有多项式时间复杂度的算法，一般倾向于剪枝搜索或者状压DP的方式解决。这类问题地点数量通常很小。

以上主要考虑的是TSP问题精确解的求法，在数模中我们可以求近似解，从中筛选较优解。

首先回顾一下之前状压DP的方法： 定义状态： f [ s t a t u s ] [ j ] ：表示状态为 s t a t u s （即已经过 s t a t u s 所表示点集），最后访问的是节点 j 的最短距离 f[status][j]： 表示状态为 status （即已经过 status 所表示点集），最后访问的是节点 j 的最短距离 f[status][j]：表示状态为status（即已经过status所表示点集），最后访问的是节点j的最短距离 递推方程： f [ s t a t u s ] [ j ] = m i n k ∈ s t a t u s & & j ∉ s t a t u s ( f [ s t a t u s − ( 1 < < j ) ] [ k ] + d i s [ k ] [ j ] ) f[status][j] = min_{k{\in}status\&\&j{\notin}status}(f[status-(1 // 枚举 if (!((i >> j) & 1)) continue; // 枚举状态f[i]可能的最后访问节点 for (int k = 0; k e0​,e1​,e2​,...ei​}中选择 e i + 1 e_{i+1} ei+1​: （a） e i + 1 e_{i+1} ei+1​与 v i v_{i} vi​关联； （b）除非无别的边供选择，否则 e i + 1 e_{i+1} ei+1​不应该是 E ( G ) − { e 0 , e 1 , e 2 , . . . e i } E(G)-\{e_0,e_1,e_2,...e_i\} E(G)−{e0​,e1​,e2​,...ei​}中的桥。 （3）（2）不能进行时算法停止。

割边：设无向图 G ( V , E ) G(V, E) G(V,E)为连通图，若边集 E 1 ⊆ E E_1⊆E E1​⊆E，在图G 中删除 E 1 E_1 E1​中所有的边后得到的子图是不连 通的，而删除了 E 1 E_1 E1​的任一真子集后得到的子图是连通图，则称 E 1 E_1 E1​是G的一个割边集。若一条边 构成一个割边集，则称该边为割边，或桥。

首先求一个 Hamilton 圈 C ，然后适当修改 C 以得到具有更小权的新 Hamilton 圈。修改的方法为改良圈算法。设初始圈为 C = v 1 v 2 . . . v n v 1 C = v_1v_2...v_nv_1 C=v1​v2​...vn​v1​ 。 （1）对于 1 ≤ i < i + 1 < j ≤ n 1\leq{i}