TSP的聚類算法

我正在嘗試解決大約10,000個城市的非常大的TSP問題。爲了將我的任務並行化，我希望將這些城市分爲集羣並解決每個集羣的TSP。TSP的聚類算法

我想要一種方式，我可以將我的城市分爲集羣（基於城市密度/該集羣中每個城市之間的鄰近度）。

有誰知道有效的命令來做到這一點？

2012-12-14 Ananth Saran

這是一個非常忙碌的推銷員。祝你好運。 –

您是否意識到無法僅使用每個羣集的TSP解決方案來最優化地解決TSP問題？所有頂點上的最優TSP可能訪問集羣1中的某些頂點，然後訪問集羣2中的某些頂點，然後再訪問集羣1中的更多頂點，依此類推。即使您發現，對於每個羣集中的每對點，連接這對點的最短路徑並訪問羣集中的所有頂點，通過將這些路徑拼接在一起可以構建的最佳TSP仍然可能遠遠不是最佳。 –

有一個簡單的近似算法，它承諾解決方案最多比最佳解決方案差2倍（如果我沒有記錯，至少在歐幾里德度量中）。該算法是：獲得最小生成樹。使用樹邊來旅行。

我會研究更好的近似算法，而不是自己發明一個算法。

，分離成集羣，如果你想這樣做，有K-means和其他算法（在同一篇文章中）

來源

2012-12-14 05:27:30 Drakosha

有幾種基於密度的聚類算法，只是你正在尋找的工具，無論如何都將點分成集羣。

DBSCAN是其他人的主要來源。 OPTICS是DBSCAN的一個擴展，它本身不會產生聚類，但會繪製一些點，您可以檢查以提取聚類（還有另一部分算法也會自動提取聚類）。DBSCAN更簡單，OPTICS更多靈活。這兩種方法都可以通過適當的索引結構（如R-tree）變得更好。工具包中有一些實現，例如ELKI，scikit和WEKA。

（和，作爲j_random_hacker說，有通過做這樣沒有了TSP全球最優的擔保）

來源

2013-05-07 09:09:44 Sephra

TSP的聚類算法

回答

相關問題