c++ - TSP 的聚类算法

Question

我正在尝试解决一个包含大约 10,000 个城市的非常大的 TSP。为了并行化我的任务，我想将这些城市划分为集群并解决每个集群的 TSP。

我想要一种可以将我的城市分成集群的方法（基于城市的密度/该集群中每个城市之间的接近度）。

有谁知道这样做的有效命令？

Answer 1

有一个简单的近似算法，它保证解决方案最多比最优解决方案差 2 倍（如果我没记错的话，至少在欧几里得度量中）。算法是：得到一个最小生成树。使用树边旅行。

我会研究更好的近似算法，而不是自己发明一个。

要分离到集群，如果你想这样做，有K-means和其他算法（在同一篇文章中）

Answer 2

有几种基于密度的聚类算法正是您正在寻找的工具，用于将点分成聚类。

DBSCAN 是其他的主要来源。OPTICS 是 DBSCAN 的扩展，它本身不会产生聚类，但会绘制一个点图，您可以检查这些点以提取聚类（算法的另一部分也可以自动提取聚类。） DBSCAN 更简单，OPTICS 更简单灵活的。通过适当的索引结构（例如 R-tree），这两者都会变得更好。在 ELKI、scikit 和 WEKA 等工具包中有实现。

（并且，正如 j_random_hacker 所说，这样做并不能保证 TSP 的全局最优性）