トラベリングセールスマンのヒント

Question

私は旅行セールスマンの問題に直面しなければならないアプリケーションを開発しています。私は自分の試行をしましたが、私が得る時は本当に悪いです。私はいくつかの最適化ソリューションを探していましたが、何も明らかになっていません。

このプロセスまたはalgorythmsの最適化を開始するためのヒントはありますか？私の現在のアルゴリズムは基本的なバックトラッキングアルゴリズムです。

私のグラフは、あなたのメトリックが三角不等式を満たす場合は私が見てあなたをお勧めすることができます... TSPグラフ（無指向性、simetric、コネックス）に

おかげ

Answer 1

をすべての典型的な条件を満たしてchristofidesアルゴリズム。最適なソリューションの範囲内にあることが保証されています。 IMOクリストファーデスアルゴリズムの難しい部分は完璧なマッチングです。保証について気にしない場合は、Googleマップのtspソルバーを探すことができます。大規模なルートのためにAnt Colony Optimizationを使用します。あなたが本当に速い解決と精度の低いものを望むなら、ヒルベルト曲線やムーア曲線のようなモンスター曲線を探すことができます。