探索、推論

Searching
AI

探索木

探索木とは、簡単に言えば場合分けである。場合分けの問題を考える手法の一つに樹形図というものがあったが、それとよく似ている。場合分けを続けて行うことにより、いずれは目的の条件に合致するモノにたどり着けるという考え方である。場合分けという単純な作業の繰り返しはまさにコンピュータの得意とする所だろう。
しかし、ただやみくもに場合分けを行うのはあまりにも効率が悪い。人間も1~100の番号において一つずつ場合分けを行う場合、1や100から順番に行うのが普通だろう。コンピュータの場合、探索を行う方法は二つ存在する。

AI

幅優先探索

この方法では、あるノードからつながっている隣のノードをすべて探索し、続いてさらにつながっている隣のノードの探索を行う。この方法では無駄なく最短距離でゴールに到達することができる反面、途中の結果をすべて記録する必要があるため、多くのメモリを必要とする。

AI

深さ優先探索

この方法ではあるノードから行き止まりのノードまでを探索し、行き止まりにたどり着いたら一つ前のノードまで引きかえし、次の行き止まりまで探索するという作業を繰り返し行う。幅優先探索と違い、結果を記録する必要がないためメモリはあまり必要とはしない。しかし最短距離でゴールを見つけることはできない。運がよければいち早くゴールにたどり着くことができるが、運が悪ければ時間がかかってしまう