特定のノードにアクセスする単純なパスが存在するかどうかを判断しますか？

Question

グラフ<V, E>、開始ノードst、終了ノードedおよび特定のノードセットMが必要です。私の質問は、すべてを訪問している単純なパスを見つけることですM。また、私は知りたいです：

1パスは存在しますか？

2存在する場合は、できるだけ早く見つける方法はありますか？

Answer 1

セットMのため、問題はNP完全であることが知られているハミルトニアンパスに縮小することができます。

パスが存在するかどうかを確認する方法は、1つを見つけて、最も速いものを見つけることはNです！ノードの数で。

パスが存在しない場合（パスを完了するために複数回渡す必要がある切断されたコンポーネントまたは重要なノード）、再帰の早期に停止するスマートヒューリスティック（そのような経路が完了できないことが明らかになったとき）、またはより良いノード順序を選択することができます。