グラフにノードのセットを含むサイクルを見つける方法は？

Question

無向G =（v、e）とノードPのセットを指定してください。これらのノードを含むサイクル（最短の長さサイクルではない）を見つける必要がありますか？このサイクルを見つけるにはどうすればよいですか？

Answer 1

ハミルトニアンサイクル（p = vの場合）が含まれているため、決定の問題（そのようなことがあるかどうかを知るだけで）はnp完全です。したがって、p = npでない限り、効率的なアルゴリズムはありません。

Answer 2

おそらく、Pで最初のノードを選択してアルゴリズムの設計を開始し（P [0]）、P [0]から深さFirt検索を実行して、いつでもP [0]に注意してください。 P [0]を再測定するために取られたパスを保存する必要があります（または、少なくともPの他のノードに到達したかどうか）。私は、o（v + e）であると思われる深度最初の検索と同じです。

誰かがより良い解決策を考え出すことができ、特定のヒューリスティックが助けに適用されるかもしれませんが、それはあなたを始めさせるはずです。 （たとえば、P [0]から始めるのではなく、最小のエッジでPのノードから開始する必要があると結論付けることができます。）

編集：

もう1つ考えました...深さを備えた検索を介してPの別のノードに到達したとき、DFSが最初から「スタート」したり、これを新しく含めないパスを検討する必要はありません-Foundノード。このプロパティは、そのようなサイクルが存在しない場合に、アルゴリズムがより迅速に終了するのに役立ちます。

さらに編集：

最後の編集を気にしないでください - P [0]とPのノードに到達できないP [0]との間に別のパスにPにノードがないことを確認できる場合にのみ機能します。 DF全体を行わずにそれを確実に知ってください。

ハミルトニアンサイクルについての答えに関しては、手元の問題のサイクル検出がどのようにNP完全であるかはわかりません。はい、グラフ（すべての頂点とエッジ）全体を通過して、手元の問題の基準を満たすサイクルが存在するかどうかを判断するために、到達可能なグラフ（すべての頂点とエッジ）を通過する必要があります。さらに、以前に訪問された頂点と接触すると、頂点の「フォワードパス」が基準を満たすサイクルがあるかどうかを判断することを知る必要があります。しかし、私たちはそのようなサイクルが最も短いので気にしないので、私たちが必ずしもハミルトニアンのサイクルを見つけようとしているのかわかりません。啓発することを気にしますか？