AIMA（Artificial Intelligence：A modernapproach）のNorvigによると、下降するサブツリーが無限大になる場合があるため、深さ優先アルゴリズムは完全ではありません（常に解が得られるとは限りません）。
一方、幅優先アプローチは、分岐係数が無限でない場合に完了したと言われます。しかし、それは、DFSでサブツリーが無限である場合と同じ「もの」ではないでしょうか。
ツリーの深さが有限である場合、DFSは完全であるとは言えませんか？BFSの完全性は分岐係数が有限であることに依存しているため、BFSは完全であり、DFSはそうではないのはどうしてですか。
分岐因子が無限になくても、ツリーは無限になる可能性があります。例として、ルービック キューブの状態ツリーを考えてみましょう。立方体の構成を考えると、動きの数は有限です (動きは 9 つの「平面」の 1 つを選択し、それを 2 つの可能な方向のいずれかに回転させることで構成されるため、18 回だと思います)。ただし、ツリーは無限に深いものです。たとえば、同じ平面を交互に前後に回転させることは完全に可能です (まったく進行しません)。DFS がこれを行うのを防ぐために、通常は訪問したすべての状態をキャッシュします (状態ツリーを効果的に剪定します) - おそらくご存知でしょう。ただし、状態空間が大きすぎる (または実際には無限である) 場合、これは役に立ちません。
私は AI について詳しく調べたわけではありませんが、BFS は完全であるのに DFS は完全ではない (完全性とは、結局のところ、どこかで定義された用語です) という論理的根拠は、無限の深いツリーが無限のツリーよりも頻繁に発生するためであると想定しています。分岐因子 (無限の分岐因子を持つということは、無限の数の選択肢があることを意味するため、これは一般的ではないと私は信じています - ゲームとシミュレーションは通常離散的です)。有限のツリーの場合でも、通常は BFS のパフォーマンスが向上します。これは、DFS が間違ったパスから開始し、ゴールに到達する前にツリーの大部分を探索する可能性が非常に高いためです。それでも、ご指摘のとおり、有限ツリーでは、DFSは、存在する場合、最終的に解決策を見つけます。
DFS はサイクルでスタックできません (開いた状態と閉じた状態のリストがある場合)。d解が無限よりはるかに低い深さであるにもかかわらず、無限空間で解を見つけられないため、アルゴリズムは完全ではありません。
各ノードがフィボナッチ数列の次の数と同じ数のサクセサーを持つ奇妙に定義された状態空間を想像してみてください。したがって、再帰的に定義されているため、無限です。ノード 2 を探しています (グラフで緑色でマークされています)。DFS がツリーの右のブランチから開始する場合、ノードがそこにないことを確認するために無限のステップが必要になります。したがって、完全ではありません (適切な時間内に終了しません)。BFS は 3 回目の繰り返しで解決策を見つけます。
ルービック キューブの状態空間は有限です。それは巨大ですが、有限です (人間はサイクルに行き詰まりますが、DFS は同じ動きを 2 回繰り返すことはありません)。DFS はそれを解決する方法として非常に非効率的な方法を見つけます。この種の解決策は実行不可能な場合があります。通常、最大深度は無限であると考えていますが、リソース (メモリ) は常に有限です。