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

【Abstract】 A TSP heuristic algorithm based on grouping strategy is proposed. The binary K-means clustering method is used to group the vertices recursively, when the number of vertices in the group is reduced under a given threshold, the exact solution is carried out, and the solution results are combined to obtain the solution to the original problem. The experimental results and analysis show that the difference between the solution and the exact solution or the current optimal solution is slight, which can be used as the approximation of the exact solution. This method has O(n~2) complexity and can be further simplified to O(nlog n).更多还原