graph - 有向グラフ内の 2 つのノード間のパス上のすべてのノードを効率的に見つける

Question

私は現在、有向グラフ内の 2 つのノード (たとえば、と)の間のパスにあるすべてのノードを見つける効率的な方法を見つけようとしています。XY

私が最初に考えたのは、X から BFS を実行し、Y から BFS を実行し、訪問したノードの交差点を取ることでした。X と Y の間のすべてのパスを列挙する必要はなく、X から Y へのパス上にあるすべてのノードを見つけるだけであることに注意してください。

私の質問は、これを行うためのより最適化された方法はありますか?

Answer 1

最適化は、実行時間を短縮する、メモリの使用量を減らす、または適切な解を見つけるという観点から実行できます (極大値で問題ない場合もあります)。

A* 検索を見て、これが問題に適用できるかどうかを確認できます。これを適用できれば、メモリを節約し、実行時間を短縮できます。