AIと探索木 - 幅優先探索と深さ優先探索

AIの基本ともいえる、探索と推論の中で、探索木について復習してみましょう。

 

幅優先探索

幅優先探索とは、ノードから繋がっている隣のノードを順番に全て探索を行ってから、後続のノードの探索を開始して、探索すべきノードが見つかるまで処理を行う、というものです。

 幅優先探索のメリットは、

• 最短距離でゴールにたどり着くことができる

 ですが、一方で、デメリットも存在し、

• 探索したノードを記憶するために、複雑な探索木になればなるほど、多量のメモリを要する

ということもあります。

深さ優先探索

深さ優先探索とは、あるノードの末端まで探索をしてから、ノードを遡って、隣のノードを同様に末端まで探索を行いながら、探索を行っていく方法です。

 

深さ優先探索のメリットとしては、

• 目的のノードがなくても、1つ手前のノードに戻って探索し直すだけなので、辿ったノードを記憶する必要がなく多くのメモリを必要としない

一方でデメリットとしては、

• 一般的に、幅優先探索より目的のノードに辿り着くまでに時間を要する

ということがあげられます。

これらのメリット、デメリットは、あくまで一般論であり、目的とするもののケースによっては、それぞれのメリット、デメリットに関係なく、解を得られることもあります。
いずれも一長一短の性質であるため、一概にどちらが優れているとも言い切ることができません。
また、両方を組み合わせた探索、という使い方も研究が続いています。