トラベリングセールスマン（TSP）のパフォーマンス

TSPの最適化と経験則をどのように比較できますか？私はTSPを実装しましたが、どうすればそれらを比較できるのか分かりません。実際、TSPの最適コストをどのように見つけることができますか？任意の方法または推測？最適にTSPを解くトラベリングセールスマン（TSP）のパフォーマンス

おかげ

どの程度... *距離*を使用してソリューションを比較しますか？ –

@GregHewgill：私はTSPプログラムの入力としてマトリックスを与えましたが、明らかに短いカットを行いますが、マトリックスには短いカット距離はなく、最適なコストアルゴリズムはありません。 –

はNP困難な問題です。

は、他のアルゴリズムによって生成さヒューリスティックソリューションと比較：
はヒューリスティックソリューションの品質を評価するために、あなたはいくつかのオプションがあります。これにより、特定のインスタンスでどのヒューリスティックがよりうまく機能するかを知ることができますが、最適なソリューションにどのくらい近づいているかについては何も教えてくれません。
最適なソリューションと比較してください。おそらくこれを計算するのに、Concordeが最適です。
TSPインスタンスの下限を計算し、そのヒューリスティック解を比較します。 2つの標準的なアプローチは、Held-Karp下限と割り当て問題の緩和です。
TSPLIBなどの既知の最適解を持つインスタンスを使用します。

2011-12-04 08:42:22 NPE

チェック、よく知られたベンチマークの事例で最適なソリューション：

がTSPLIB hereからデータをダウンロードして、最適な値here

2011-12-04 08:42:57

答えて