ハミルトン経路を決定する巡回セールスマンソルバーを使用して

Question

これは、私は巡回セールスマン最適化問題ともハミルトン経路またはサイクル決定問題のためのヒューリスティックを実装するように求めていたプロジェクトのためです。私は、実装自体のヘルプが必要ですが、私は行くよ方向に疑問を持っていません。

私はすでに、遺伝的アルゴリズムに基づいてTSPヒューリスティックを持っている：それは集団として、ランダムなソリューションのセットで開始し、世代数の母集団を向上させるために働き、完全グラフを前提としています。私はまた、ハミルトン経路またはサイクルの問題を解決するためにそれを使用することはできますか？代わりに最短経路を得るために最適化する、私はパスがあるかどうかを確認したいです。

これですべての完全グラフはそれにハミルトン経路を持っていますので、TSPヒューリスティックは、任意のグラフに拡張しなければならないであろう。これは、2つの都市間のパスがない場合は、いくつかの無限大値にエッジを設定し、有効なハミルトンパスで最初のパスを返すことで行うことができる。

は、正しい方法でそれに近づくということですか？または私はハミルトン経路に異なるヒューリスティックを使用する必要がありますか？私の主な関心事は、（あなたが解決策を開始し、それらを改善するため）ハミルトン経路決定者が世代の一定数の任意のパスを見つけるならば、私はなく、TSPの最適化が機能することを多少確認することができますので、それは実行可能なアプローチだかどうかである。

私は最善のアプローチは、それを自分自身をテストするだろうと仮定したが、私は、時間によって制約と私は/ <（私が代わりにハミルトン経路ごとに異なるヒューリスティックを見つけることができる）...このルートを下って行く前にお願いしたいと思っていますP>

Answer 1

あなたはこの答えを持っているかどうかを知るしないでください。簡単なトリックは、すべての他のポイントへのゼロの距離を持つつのダミーポイントを追加することです。 TSPを解決し、ダミーの点を取り除く - どのような残っているのはハミルトン経路です。シンプル！

Answer 2

あなたが入力を変換し、同じアルゴリズムを使用することができます定義によるように、

両方、NP完全問題であり、 - ）

しかし、基本的な考え方は動作するはずです。もちろん、あなたが新しいパスと成功基準の生成を変更する必要があります。

編集： ところで： 無作為化アルゴリズムの提案があります： http://en.wikipedia.org/wiki/Hamiltonian_path_problemする