こんにちは、 私はTSPの問題を解決する必要があるプロジェクトに取り組んでいます。私がここで必要とするのは、グラフのハミルトニアン回路をどのように見つけることができるかということです。実際に私は現実世界でこれを行う方法を知っています。しかし、実装とソースコードでは、これをどのように行うことができるのかわかりません。私はいくつかのネストされたループを使用するインターネット上の記事を読んだが、私はそれぞれが何をしているのか、どのように全体の話が進むのか分からなかった。誰かが私を助けることができたら、私は感謝しています。そして、これを実装する方法の簡単な例を私に教えてください。私は実用的なモデルは必要ありません。ちょうど私たちが頂点の配列とパスの配列を持っていると仮定します(パスによって、パスの開始と終了の頂点を意味します)。この問題をどのように解決できるかTSP問題のハミルトニアン回路を見つける際の問題
0
A
答えて
1
TSPの正確な解を見つけるより効率的な方法の1つは、O(n^2 * 2^n)で実行される動的プログラミングアルゴリズムを使用することです。これは、線形プログラミングの選択肢のいくつかと比較してむしろ単純です。 「TSP動的プログラミング」を検索すれば、多くの例が見つかります。
O(n!)で実行されるブルートフォースのようなもっと単純なアプローチがあります。あなたがforループをたくさん見た場合(つまり、2つ以上の場合)、これはおそらくあなたが以前見たアルゴリズムのタイプでしょう。これらは仕事を完了します(グラフのサイズに応じて、この生涯ではないかもしれません)。
関連する問題
- 1. ListViewのAdapterでの位置を見つける際の問題
- 2. ACSXコントロール内のマスターページを見つける際の問題
- 3. 円の交点を見つける際の問題
- 4. 2回の違いを見つけるときの問題
- 5. GPSを見つける際の奇妙な問題
- 6. 正規表現ミスを見つける際の問題
- 7. Excelを見つけて置き換える際の問題C#
- 8. 問題を見つける - iphone sdk
- 9. 問題を見つけるには
- 10. 初心者の質問 - データの問題を見つける
- 11. ビジュアルプロローグ - 迷路問題
- 12. 航路コントローラの問題
- 13. Pythonのセットアップ経路問題
- 14. 通路/道路敷設の問題
- 15. イメージの重複ブロックのHuモーメントを見つける際のパフォーマンス上の問題
- 16. ジオコーダを使用して地名を見つける際の問題
- 17. jQueryの/( ':目に見える')です見つける問題
- 18. 最大経路問題
- 19. 回転問題
- 20. Cのポーカーソフトウェアのプロトタイプ、ストレートを見つける機能の問題
- 21. solrのパフォーマンスの問題を見つけるためのツール
- 22. どのようにアプリケーションのクラッシュの問題を見つける
- 23. JavaScriptの構文の問題 - それを見つける
- 24. Vbaセレニウムは要素を見つける際に問題に直面します
- 25. アニメーションのあるダイアログを回転させる際の問題
- 26. セットカバー問題の最小サイズセットカバーを見つけるアルゴリズム
- 27. 処分とメモリの問題を見つけるには? C#
- 28. 適切なoptaplannerドメインモデルの問題を見つける
- 29. win cmdのフォルダを見つける問題
- 30. Greasemonkeyがテキストの問題を見つける
私はあなたが望むものを理解するのではなく、最寄りの隣人、2-opt、3-opt、antアルゴリズムなど、異なるアルゴリズムを組み合わせる必要がある最速の方法でTSPを解決することはできません。プログラミングの最善の方法でそれらを組み合わせることです。 – Pietro
私の問題は、速い方法を見つけることができません、それはちょうどそれの実装についてです。私はどのステップでグラフを見ることができますか?次に、サイクルを比較して、どのノードがすべてのノードにアクセスしているかを確認し、最小ツアーを探したいとします。私はそれが良いアルゴリズムではないことを知っているが、私はちょうどこれを実装したい。そして、私はどのようにグラフでサイクルを見つけるためのプログラミングアルゴリズムがわかりません。 – user435245
グラフライブラリは物事を少し簡単にするので、生の頂点/エッジ/サブグラフ/パス表現を混乱させる必要はありません。私はhttp://jgrapht.org/を使用します。 – andersoj