c++ - 幅優先または深さ優先検索

Question

このアルゴリズムがどのように機能するかは知っていますが、どのアルゴリズムをいつ使用するかを決めることはできませんか?

他の考慮事項よりも優れたパフォーマンスを発揮するガイドラインはありますか?

どうもありがとう。

Answer 1

最短のステップ数で解を見つけたい場合、またはツリーの高さが無限 (または非常に大きい) の場合は、最初に幅を使用する必要があります。

有限ツリーがあり、最小量のメモリを使用してすべての可能なソリューションをトラバースしたい場合は、最初に深さを使用する必要があります。

プレイするのに最適なチェスの動きを探している場合は、両方の組み合わせである反復深化を使用できます。

IDDFS は、深さ優先検索のスペース効率と幅優先検索の完全性 (分岐係数が有限の場合) を組み合わせます。

Answer 2

BFS は通常、グラフに意味のある「自然な階層化」があり (たとえば、より近いノードは「より近い」結果を表す)、目標結果が開始点の近くに配置される可能性が高い場合、または開始点が「検索が安価である」場合に役立ちます。 "。

最短経路を見つけたい場合は、BFS を選択するのが自然です。

グラフが無限であるか、プログラムで生成されている場合は、より近いノードに到達する前にリモート ノードを探索するコストが法外に高くなるため、遠出を試みる前に、おそらくより近いレイヤーを検索することをお勧めします。

メモリ/ディスク/局所性の問題により、より多くのリモート ノードにアクセスするとコストが高くなる場合は、BFS の方が優れている可能性があります。

Answer 3

通常、どちらの方法を使用するかはアプリケーション (つまり、グラフを検索する必要がある理由) によって異なります。たとえば、トポロジカル ソートには深さ優先検索が必要ですが、最大フローを見つけるための Ford-Fulkerson アルゴリズムには幅優先検索が必要です。

Answer 4

ツリーをトラバースする場合、深さ優先はその深さに比例したメモリを使用します。ツリーが適度にバランスが取れている場合（またはその深さに他の制限がある場合）、再帰的な深さ優先トラバーサルを使用すると便利な場合があります。

ただし、一般的なグラフをトラバースする場合はこれを行わないでください。スタックオーバーフローが発生する可能性があります。制限のないツリーまたは一般的なグラフの場合、入力ノードの数に比例したサイズに拡張できる、ある種の補助ストレージが必要になります。この場合、幅優先探索は単純で便利です。

問題が1つのノードを別のノードよりも選択する理由を提供する場合は、スタック（深さ優先の場合）またはFIFO（幅優先の場合）の代わりに優先キューの使用を検討できます。優先度キューは、各ステップで最適なノードを見つけるためにO（log K）時間（Kは異なる優先度の現在の数）を要しますが、最適化はそれだけの価値があるかもしれません。