巡回セールスマン問題を解決するためのヒューリスティックス/近似値を見つけようとしています。そのために、いくつかの「難しい」TSP インスタンスを (最もよく知られている解決策と共に) 探しています。それらを見て、私がどれだけうまくやれるか見てください。
理想的には、それらは単に隣接行列または隣接リストのテキストベースのリストです (私は解析を扱いたくありません。アルゴリズムだけを扱いたいのです)。
「難しい」とは、ブルートフォースを使用して解決または近似することが事実上不可能であることを意味します。
(これは、最もよく知られている答えに近い答えを見つけた場合、単に幸運になるだけでなく、実際に何か正しいことをしていると合理的に確信できるようにするためです。)
この目的のために機能するリストはありますか? 私は少し周りを検索しましたが、何も見つかりませんでした。
SEに関する別の質問があなたの問題に部分的に答えています（問題がリストされていますが、これらのほとんどは解決策が提供されていないようですが、とにかくリンクを確認する方が良いです-状況が変わった可能性があります）。
それらが見つからない場合は、ノードのセットとそれらを接続するパスをランダムに生成し、パスの長さを「最小」として保存し（2つのノード間の最長接続がXを超えないようにします）、次にこれらがすべて>Xであることを確認する他のパスの束？
このようにして（何かが足りない場合を除いて）、「必要なだけ複雑な」接続ノードのセットがあり、最初から実際の最短接続パスを知っています...
補遺-既存のツールとの比較を本当に知りたい場合は、生成された問題に対してこれらを実行する必要があります。無料でアクセスできるのは（しかし、それがどれほど「効率的」であるかはわかりませんが）、R用のTSPライブラリです。
ウィキペディアには、このための他の無料のswパッケージのリストがあります。
たぶん、他のTSPツールを入手する方法を尋ねる別のSE質問を作成することができます。
TSP gatech サイトは、TSP 情報の標準的なサイトのようです。
利用可能なデータセットのリストは次のとおりです: http://www.tsp.gatech.edu/data/index.html
最適なソリューションは、10,000 を超える都市を含む一部のデータセットで利用できます。また、1 000 000 を超える都市の利用可能なデータセットがあります。
最適なTSPソリューションを見つけるためのよく知られたアルゴリズムがあります-それはブルートフォースと呼ばれます。
したがって、2つのアルゴリズムを比較できる唯一の実際の方法は、ソリューションの品質と他のいくつかの基準（通常は実行時間）にある必要があります。
ここでも問題が発生します。多くのアルゴリズムは効果的に検索アルゴリズムであり、検索が長ければ長いほど、より多くの可能な解決策が評価されます。アルゴリズムはすでに品質と実行時間をトレードオフしています。それらは、一部またはすべてのグラフに対して正しい（最良の）答えをもたらす場合とそうでない場合があります。
自分のアルゴリズムを他のアルゴリズムと比較できる唯一の実際の方法は、他のアルゴリズムを実装してから、自分とそれらに同じ難しい問題を投げかけることです（他の人が特定しているように、少なくともいくつかの種類の難しい問題を簡単に作成できます） ）。これらの既存のアルゴリズムを実装すると、アルゴリズムを改善する方法が提案される場合があります。http://en.wikipedia.org/wiki/Travelling_salesman_problemにはたくさんのアルゴリズムがあり、少なくともいくつかはコーディングが非常に簡単に見えます。アルゴリズムの最初のベンチマークとしてそれらを実装してみませんか？