java - TSP問題のハミルトニアン閉路を求める問題

Question

こんにちは、私は TSP 問題を解決する必要があるプロジェクトに取り組んでいます。ここで必要なのは、グラフでハミルトニアン回路を見つける方法です。実際、私は現実の世界でこれを行う方法を知っています。しかし、実装とソースコードでは、これを行う方法がわかりません。ネストされたループを使用するインターネット上の記事を読んだことがありますが、それぞれが何をしているのか、ストーリー全体がどのように進んでいるのかはわかりませんでした。誰かがこれについて私を助けることができれば幸いです。そして、これを実装する方法の簡単な例を教えてください。ワーキングモデルは必要ありません。頂点の配列とパスの配列があると仮定してください (パスとは、パスの始点と終点の頂点を意味します)。この問題をどのように解決できるか。

Answer 1

TSP の正確な解を見つけるより効率的な方法の 1 つは、O(n^2*2^n) で実行される動的計画法アルゴリズムを使用することです。いくつかの線形計画法に比べてかなり単純です。「TSP 動的プログラミング」で検索すると、たくさんの例が見つかるはずです。

O(n!) で実行されるブルート フォースなど、より素朴なアプローチがあります。多くの for ループ (つまり、2 つ以上) を見た場合、これは以前に見たタイプのアルゴリズムである可能性があります。これらは仕事を成し遂げます（グラフのサイズによっては、この寿命ではないかもしれません）。