3

ハミルトン閉路問題を解こうとしています。すべての頂点を含むパスを見つけることはできますが、サイクルを完了することができません。

誰かが私にサイクルを見つけるためのアルゴリズムを提供できますか？

4

4 に答える 4

16

グラフにハミルトン閉路があるかどうかを判断することは、NP完全問題です。これは、与えられたパスが多項式時間のハミルトンサイクルであるかどうかを確認できることを意味しますが、それを見つけることができる多項式時間アルゴリズムはわかりません。

ハミルトン閉路を見つけるために使用できる唯一のアルゴリズムは、指数時間アルゴリズムです。それらのいくつかは

  • ブルートフォース検索
  • 動的計画法
  • あなたがここで見つけることができる他の指数関数的であるにもかかわらずより速いアルゴリズム
于 2012-10-28T09:24:57.437 に答える
2

これはコンピュータサイエンスの最も基本的な問題の1つであり、必要なものに応じて多くの解決策があります。ここから開始http://en.wikipedia.org/wiki/Hamiltonian_path_problem#Algorithms

関連するSOの回答もあります： ここ とここ

于 2012-10-28T09:04:09.873 に答える
2

私が見つけた以下のリンクが明確な説明であなたに大いに役立つことを願っています...... http：//www.geeksforgeeks.org/archives/19092

于 2012-10-28T09:07:09.263 に答える
0

可能であればSATソルバーを使用してください。ウィキペディアの記事にあるアルゴリズムの理論的な時間制限はありませんが、実際には、驚くほど迅速に解決できることがよくあります。

于 2017-09-21T10:46:59.700 に答える