有向グラフのすべての頂点を1回以上訪れるパスを見つけるアルゴリズム

私は有向グラフのSCCを持っています。頂点sから始めて、このSCCのすべての頂点を少なくとも1回訪れるパスを見つけたいと思います。私はこれがNP問題かもしれないことを知っています。それにもかかわらず、どうすればこの問題を解決できますか？有向グラフのすべての頂点を1回以上訪れるパスを見つけるアルゴリズム

出典

2017-11-08 Amitesh Srivastava

ハミルトニアンパス（https://en.wikipedia.org/wiki/Hamiltonian_path）は、各頂点*を正確に1回訪問し、存在するかどうかをNPCで判断します。しかし、少なくとも*一度訪れたほうが簡単です - それ以上のパスではないかもしれないことを除いて... – gilleain

_any_ path（必要ではない単純なもの）が必要な場合は_some_ pathを1から2、_some_ path 2から3までのように（1、2、3、...はあなたのSCCの頂点の数です）。単純なパスが必要な場合、@ gilleainはNP完全ハミルトニアンパスの問題であることに気付きました。 –

@IvanSmirnovありがとう！私はいくつかの道が必要でした（歩いてください）。単純な経路ではありません。これは助けになりました。 –

パスが必要な場合（シンプルでは必要ありません）、1から2までのパス、2から3までのパスを見つけることができます（1,2,3、...はあなたのSCCの頂点）。そして、単純なパスが必要な場合は、gilleainがNP完全ハミルトニアンパス問題であることが正しく認識されています。

出典

2017-11-11 14:46:27

有向グラフのすべての頂点を1回以上訪れるパスを見つけるアルゴリズム

答えて

関連する問題