algorithm - どの TSP ヒューリスティック アルゴリズムを採用する必要がありますか?

Question

TSP ヒューリスティック アルゴリズムに関連する膨大な量の論文があり、それぞれがさまざまな種類の TSP 問題に焦点を当てている可能性があります。次のように説明されているプロパティの下で、適切に実行されたTSPヒューリスティックアルゴリズムをいくつか推奨できますか? TSP問題の「都市サイズ」は30に等しい.

Answer 1

空間充填曲線を使用すると、非常に高速に解決できます。次に、k-opt などを使用してエッジを改善できます。Gebweb tsp ソルバーなどの Ant Colony Optimization もあります。また、ブルートフォースと動的ソリューションもあります。

Answer 2

巡回セールスマンがメトリック (三角形の不等式を尊重する) である場合は、多項式であり、常に最適解よりも最大で X 倍悪い解を返す近似アルゴリズムを使用することを検討する可能性があります。たとえば、Christofides アルゴリズムは、パスが最適なパスより最大で 1.5 長くなることを保証します。