Tip:
Highlight text to annotate it
X
深さ優先探索が最適でないとするなら、
何故それを使うのでしょうか?
答えは、容量の問題にあります。
ここにあるのは、非常に巨大な、というか無限大の
二分木から構成される状態空間です。
1から n のレベルまで降りていくに従って
木はどんどん大きくなっていきます。
ではそこで、それぞれの探索アルゴリズムについて、フロンティアの状態がどうなるか考えてみましょう。
幅優先探索においては、フロンティアはこのような状態になります。
従って、n のレベルまで到達したときに、必要な容量空間は、
2から n に到達する課程で、幅優先探索が見つけるノード総数となります。
最低コスト優先では、フロンティアはもっと複雑な状態になります。
こんな感じのコスト等高線のようになりますが、
幅優先の場合と同じくらいの総ノード数となります。
しかし深さ優先探索では、木の探索は、この枝から始まります。
そして終端まで行き着いたら戻るわけですが、そのどの時点でも、フロンティアは n ノード分しかありません。
2から n ノードまでの探索ノード総数ではないので、深さ優先探索では、非常に大きな節約が可能です。
ただ、もし探索済みノードを保持していくなら、
それほど節約ができるわけではありません。
それでも、探索済みノードを保持しないなら、節約できる容量という点において、
深さ優先探索に大きなアドバンテージがあることになります。
アルゴリズムを考える上で、もう一点考慮しなければならないのは、
完全性です、つまり、もし終状態がどこかに存在するなら、
当該アルゴリズムは、それを見つけ出せるでしょうか?
それでは、大きな木から、無限大の木に移ってみましょう。
そして、その木の奥深くのどこかに終状態が隠されているものとします。
そこで質問ですが、これらのアルゴリズムはそれぞれ、完全と言えますか?
すなわち、アルゴリズムは確実に終状態を見つけ出すことができるでしょうか?
この意味において、完全だと思うアルゴリズムのチェックボックスに、印をつけてみてください。