無向グラフ G = (V,E) と一連のノード P が与えられた場合、これらのノードを含むサイクル (最短の長さのサイクルではない) を見つける必要がありますか? このサイクルを見つけるにはどうすればよいですか？
1947 次
2 に答える
4
おそらく、Pの最初のノードを選択して（P [0]と呼びましょう）、P [0]から深さ優先探索を実行し、P[0]に再び到達したときに注意してアルゴリズムの設計を開始します。P [0]に到達するためにたどったパス（または少なくともPの他のノードに到達したかどうか）を保存して、見つかったサイクルにPのすべてのノードが含まれていることを確認する必要があります。実行時間は次のようになります。 O（V + E）であると私が信じている深さ優先探索の場合と同じです。
誰かがより良い解決策を思い付くかもしれません、そして特定のヒューリスティックが助けに適用されるかもしれません、しかしそれはあなたが始めるはずです。（たとえば、P [0]から開始するのではなく、エッジが最も少ないPのノードから開始する必要があると結論付けることができます。）
編集：
私が考えたもう1つのこと...深さ優先探索を介してPの別のノードに到達した場合、DFSが最初から「最初からやり直す」必要はなく、これを新たに含まないパスを検討する必要もありません。 -ノードが見つかりました。このプロパティは、そのようなサイクルが存在しない場合に、アルゴリズムをより迅速に終了するのに役立ちます。
さらに編集：
最後の編集を気にしないでください-P[0]と到達したPのノードとの間の異なるパス上に、別の方法では到達できないノードがPにないことが確認できる場合にのみ機能し、私たちは到達しませんDFS全体を実行せずに確実にそれを知っています。
ハミルトン閉路についての答えについては、目前の問題での循環検出がどのようにNP完全であるかわかりません。はい、開始点から到達可能なグラフ全体（すべての頂点とエッジ）をトラバースして、目前の問題の基準を満たすサイクルが存在するかどうかを判断する必要があります。さらに、以前にアクセスした頂点と接触したときに、基準を満たすサイクルがあるかどうかを判断するために、頂点の「順方向パス」が何であるかを知る必要があります。ただし、このような最短のサイクルは気にしないので、ハミルトン閉路をどのように見つけようとしているのかわかりません。啓発する気ですか？
于 2010-10-11T17:17:52.973 に答える
2
ハミルトニアン サイクル (P = V の場合) が含まれているため、決定問題 (そのようなものがあるかどうかを知るだけ) は NP 完全です。したがって、P = NP でない限り、効率的なアルゴリズムはありません。
于 2010-10-11T18:46:08.970 に答える