[解決済み] 深さ優先探索（DFS）と幅優先探索（BFS）の使い分けはいつが実用的か？[クローズド］

質問

DFSとBFSの違いは理解していますが、どのような場合に使い分けるのが現実的なのか知りたいです。

DFSがBFSに勝る例、逆にBFSがDFSに勝る例をどなたか教えてください。

解決方法は？

それは、サーチツリーの構造、ソリューション（別名：検索されたアイテム）の数と位置に大きく依存します。

• 解がツリーのルートからそれほど離れていないことが分かっている場合は 幅優先探索(BFS)の方がよいかもしれません。

• ツリーが非常に深く、解が稀である場合、深さ優先探索 (DFS)は非常に長い時間がかかるかもしれませんが、BFSはより速くなる可能性があります。

• ツリーが非常に広い場合、BFSはメモリを大量に必要とするため は全く実用的でないかもしれません。

• 解が頻繁に現れるが、ツリーの奥深くにある場合、BFSの可能性がある。 非実用的である。

• 検索ツリーが非常に深い場合は、検索を制限する必要があります。 深さ優先探索(DFS)の深さは、いずれにしても(たとえば 反復深化)。

しかし、これらはあくまでも経験則であり、実際に試してみる必要があるでしょう。

実際には、これらのアルゴリズムをそのまま使うことはほとんどないと思います。探索空間の有望な部分を最初に探索するのに役立つヒューリスティックがあるかもしれませんし、探索アルゴリズムを効率的に並列化できるように修正したいかもしれません。