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