c++ - 無向グラフで最大数のノードを通過するパスをどのように見つけますか？

Question

無向グラフとグラフ内の2つの任意のノード（AとB）が与えられた場合、ノードAとBの間を移動するために、最も多くの一意のノードを通過するパスを見つけるにはどうすればよいですか？

深さ検索してすべての長さを比較できることは知っていますが、もっと良い方法はありますか？

Answer 1

これはNP完全問題です。あなたが本当にできることは、あらゆる可能性を試すことです。

Answer 2

この問題は、非巡回グラフについて話している場合にのみ意味があるので、あなたがそれを意味していると思います。

可能なすべてのパスを総当たり攻撃する必要があります。

理由を理解するために、2つのノードの最長パスがわかっていて、1つのノードを追加するグラフを想像してみてください。ノードが何らかの方法でそれらに接続している場合は、すでにテストしたパスを含め、新しいノードを含むすべてのパスをテストする必要があります。