时慧琨

一种基于K-means聚类及分组策略的TSP问题启发式算法

时慧琨

（淮南师范学院 计算机学院，安徽 淮南 232038）

提出了一种基于分组策略的TSP启发式算法。采用二分均值聚类方法对顶点进行递归分组，当组内顶点数降到给定阈值之下时进行精确求解，对求解结果合并从而得到原问题的解。实验结果及分析表明，求解结果和精确解/当前最优解差距很小，可以作为精确解的近似。该方法具有(2)的复杂度，并可以进一步简化到(log)。

TSP；启发式算法；K-means聚类

TSP问题又称旅行商问题，定义为：给定图=(,,)，其中为顶点集，为边集，为边的权重信息，求一条经过所有顶点的封闭路径(包含所有顶点的排列)，使得该回路权重之和最小。按照问题的不同特性可以分为对称TSP(STSP)、非对称TSP(ATSP)、单人TSP、多人TSP(MTSP)、单目标TSP、多目标TSP(moTSP)等各种不同类型。TSP问题在交通运输、线路设计及物流配送等领域内有着广泛的应用，国内外学者对其进行了大量的研究。

1 TSP问题描述及研究现状

TSP问题是典型的NP完全问题，假设=||，则其完全的解组合共有！种。当比较小时，可以利用动态规划、回溯，甚至蛮力法求得问题的精确解；当比较大时，利用前述解法求出精确解从时间方面考虑是不可能的，这时可以采用的以下的求解方法。

(1)近似解法。近似解法是指在解的最优性方面进行了放宽，从而满足求解复杂性和使用范围方面要求而得到的算法。这类算法通常用近似比来衡量算法得到的解和最优解之间的接近程度。目前最优的近似解法的近似比为3/2。……