TSP問題のハミルトニアン回路を見つける際の問題

Question

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

Answer 1

TSPの正確な解を見つけるより効率的な方法の1つは、O（n^2 * 2^n）で実行される動的プログラミングアルゴリズムを使用することです。これは、線形プログラミングの選択肢のいくつかと比較してむしろ単純です。 「TSP動的プログラミング」を検索すれば、多くの例が見つかります。

O（n！）で実行されるブルートフォースのようなもっと単純なアプローチがあります。あなたがforループをたくさん見た場合（つまり、2つ以上の場合）、これはおそらくあなたが以前見たアルゴリズムのタイプでしょう。これらは仕事を完了します（グラフのサイズに応じて、この生涯ではないかもしれません）。