三角不等式のないTSPソルバ

（小）グリッドグラフのTSPを解くことに興味があります。どんな種類の図書館が私のためにするのですが、これは予想以上に難しいようです。私はそこで見つけたいくつかのソルバー（コンコードを含む）を試しましたが、三角不等式が成り立たないときにはすべて問題があるようです。三角不等式のないTSPソルバ

例えば

、私はツアーを出力するソルバを希望（0、1、2、1、4、3）以下（単位エッジ重みを持つ）グラフのこの特に

0-1-2 
| | 
3-4

私はconcordeにエッジ（2,4）のウェイトが1000であり、concordeがコスト1004のツアー（0,1,2,4,3）を速やかに作り出したと言った。これは私が探しているものではない。

理想的には、Javaで単純な（場合によってはブルートフォース）実装がありますが、実際には何かが実際に実行されます。誰かが私にいくつかのコードを教えてもらえますか、それとも私自身が実際に実装する必要がありますか？

編集：また、近似ではなく正確な解を得ることが重要です。

Edit2：確かに、これはTSPではないようです。私が見つけようとしているのは、すべての頂点を訪れる最短の閉じた散歩です。

2012-02-28 Dino

Concordeを正しく適用してもよろしいですか？対称TSP問題のための正確なソルバーであるはずです。 –

@ Li-aungYip：Concordeは実際に最適なTSP解を与えています。問題は、OPが有効なTSPツアーではないソリューションを期待していることです。詳細は私の答えを見てください。 – NPE

私は参照してください。実際、グラフを考えると、すべてのノードを訪問する他の閉サイクルがないとは思わない。（キーワード：closed。2-1-0-3-4は重み4で、すべてのノードにアクセスしますが、閉じていません） –

あなたの難しさは、三角不等式ではありません。難しさは、あなたが期待している解決策が有効なTSPツアーではないという事実と関係しています。

TSPは、Hamiltonian cycleを探します。つまり、各頂点を一度正確に訪れるサイクルです。あなたの解答(0, 1, 2, 1, 4, 3)は、頂点1を2回訪問します。

あなたが探している解決策なら、あなたが解決しようとしている問題は旅行セールスマン問題ではありません。

2012-02-28 09:00:07 NPE

これを指摘してくれてありがとう！だから私は最初に私のグラフ内のすべての頂点間の距離行列を計算してからTSPを解くべきだと思います。それは私のグリッドに最適なツアーの長さを与えるはずです。正しい？ – Dino

@Duh：率直に言って、それがあなたの問題をTSPに変換するのに役立つかどうか分かりません。いずれにせよ、私は有用な第一歩は、あなたが探しているものが何であるかを知ることです（各頂点を訪れる最短サイクル*少なくとも1回ですか？） – NPE

はい、それはまさに私が探しているものです。この場合、正確な距離で完全なグラフに問題を移動すると、問題が解決しました。 - 最適解の長さが等しいことを示すのは簡単です - 最適な状態から自分の視点でツアーを構築するのは簡単ですか完全なグラフのTSPツアー – Dino

答えて