c++ - TSPのクラスタリングアルゴリズム

Question

私は約10,000の都市を持つ非常に大きなTSPを解決しようとしています。タスクを並列化するために、これらの都市をクラスターに分割し、クラスターごとにTSPを解決したいと思います。

都市をクラスターに分離できる方法が必要です（都市の密度/クラスター内の各都市間の近接度に基づいて）。

誰かがこれを行うための効率的な順序を知っていますか？

Answer 1

解が最適解よりも最大で2倍悪いことを約束する単純な近似アルゴリズムがあります（少なくとも、私が正しく覚えていれば、ユークリッド距離では）。アルゴリズムは次のとおりです。最小スパニングツリーを取得します。木の端を使って移動します。

自分で発明するのではなく、より良い近似アルゴリズムを研究したいと思います。

クラスターに分離するために、それを実行したい場合は、K-meansと他のアルゴリズムがあります（同じ記事にあります）

Answer 2

とにかくポイントをクラスターに分離するための、まさにあなたが探しているツールである密度ベースのクラスタリングアルゴリズムがいくつかあります。

DBSCANは、他のものが派生する主要なものです。OPTICSはDBSCANの拡張であり、それ自体はクラスタリングを生成しませんが、クラスターを抽出するために検査できるポイントのプロットを作成します（クラスターを自動的に抽出するアルゴリズムの別の部分もあります）。フレキシブル。これらは両方とも、Rツリーなどの適切なインデックス構造を使用すると改善されます。ELKI、scikit、WEKAなどのツールキットには実装があります。

（そして、j_random_hackerが言うように、このようにすることによってTSPのグローバルな最適性が保証されるわけではありません）