针对旅行售货员问题

针对旅行售货员问题，本节给出较好的近似算法，即最邻近算法和一个修改算法。设n个顶点的赋权完全图G(V,E)，

W(wij)nn为此图的权值矩阵。根据实际问题，可规定：对V(G)中任何三个顶点u，v和x均满足w(uv)w(vx)w(ux)。

首先给出求近似最优Hamilton圈的最邻近算法的基本思想：

任选一个点v0作起点，找一条与v0关联且权最小的一条边e1，e1的另一个端点记为v1，得一条路v0v1；

设已选出路v0v1vi，在V(G)v0,v1,,vi中取一个与vi最近的相邻顶点vi1得路

v0v1vivi1；

Cv0v1vpv0若i1n1，用i代i1返回；否则，记。停止。

最后，所得的C就是赋权完全图G的一条近似最优的Hamilton回路。用最邻近法求得的

Hamilton回路一般不是最优的，但是通过以下的改良，可获得更短的Hamilton回路。

设Cv1v2vnv1是图G的一个已知的Hamilton圈。对圈C中所有满足 的1i1jv的

i，j，按照以下方法最终可得一条新的Hamilton圈C1；

vvE(G)vvE(G)在C上检查是否有ij，使得ij，i1j1且w(vivj)w(vi1vj1)w(vivi1)w(vjvj1)，则构成新图

C1v1v2vivjvj1vi1vj1vnv1

用C1代替C转，直至终止。

以上的算法称为改良圈算法。改良圈算法是一种近似算法，给出的结果不一定是最优的，但有理由认为它常常是比较好的。