巡回セールスマン問題のためにPythonでミームアルゴリズムを作成しました。ただし、私が遭遇したすべてのテストデータ（都市間の距離のリスト）には、最適なソリューションの情報が不足しているため、アルゴリズムがグローバル最適にどれだけ近いかを知ることができません。
既知の最良の解決策でいくつかのtspテストデータ（できればマトリックス形式ですが、何か良いもの）をどこで見つけることができるか誰かが知っていますか？
4752 次
3 に答える
9
于 2010-06-02T13:37:16.087 に答える
1
おそらく、独自のテストデータを生成できますか？
これは間違いなく包括的なテストではありませんが、役立つかもしれません。注：以下はハミルトン経路に関するものであり、サイクルを探している場合は、同様のことが機能します。
次のことができます。
n個のノードを持つ無向グラフGが与えられたとしましょう。
ここで、Gのエッジの重みを1に設定し、Gにないエッジを追加し、ランダムな重み> 1を指定して、重み付きグラフG'を作成します。つまり、G'はすべてに重みが割り当てられた完全グラフです。そのエッジ。
ここで、G'で有効なTSPアルゴリズムを実行し、サイズn-1のパスを生成すると、Gはハミルトンパスを持ちます。それ以外の場合、Gにはハミルトン経路がありません。
これで、ハミルトンパスがある/ないことがわかっているグラフを使用して（たとえば、Hypercubeにハミルトンパスがある）、TSPアルゴリズムのテストデータを生成できます。
このページには、ハミルトン経路を持つグラフを生成するのに役立つ可能性のあるいくつかの十分条件があります：http ://www-math.cudenver.edu/~wcherowi/courses/m4408/gtln12.html
ハミルトンパスがある場合とない場合のグラフでデータを見つけるのに苦労することはないと思います。
それが役に立てば幸い。幸運を！
于 2010-06-02T16:33:06.330 に答える
0
TSPLIBは、さまざまなソースおよびさまざまなタイプのTSP（および関連する問題）のサンプルインスタンスのライブラリです。
于 2010-07-30T15:45:28.237 に答える