幅最初のまたは深さ最初の検索

Question

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

あるガイドラインは、他のガイドラインや考慮事項よりも優れたパフォーマンスがありますか？

どうもありがとう。

Answer 1

ステップ数が最も短いソリューションを見つけたい場合、またはツリーに無限の高さ（または非常に大きな）がある場合は、最初に幅を使用する必要があります。

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

あなたがプレイするために最高のチェスの動きを探しているならあなたは使用することができます 反復的な深化 両方の組み合わせです。

IDDFSは、深度ファースト検索の空間効率と幅広い検索の完全性（分岐係数が有限の場合）を組み合わせています。

Answer 2

BFSは、グラフに意味のある「自然層」（例えば、より近いノードが「より近い」結果を表す）がある場合に一般的に役立ち、目標結果は出発点に近いか、出発点が「検索する方が安い」と思われます。 "。

最短パスを見つけたい場合、BFSは自然な選択です。

グラフが無限であるか、文法的に生成されている場合、より近いノードに到達する前にリモートノードを探索するコストは法外にあるため、アフィアを冒険する前により近いレイヤーを検索することをお勧めします。

メモリ/ディスク/ローカリティの問題により、よりリモートノードにアクセスする方が高価になる場合、BFSが再び優れている可能性があります。

Answer 3

使用する方法は通常、アプリケーションに依存します（つまり、グラフを検索する必要がある理由） - たとえば、トポロジーソートには深さfirst検索が必要ですが、最大フローを見つけるためのFord-Fulkersonアルゴリズムには幅広い最初の検索が必要です。

Answer 4

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

ただし、一般的なグラフを横断するためにこれを行わないでください。スタックオーバーフローを引き起こす可能性があります。固定されていないツリーまたは一般的なグラフの場合、入力ノードの数に比例したサイズに拡張できる、何らかの補助ストレージが必要です。この場合、幅最初のトラバーサルはシンプルで便利です。

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