第２７回　『探索』

皆様こんにちは，同志社大学の土屋誠司です．人工知能の第２７回目の今回は，探索について書いてみたいと思います．

『探索』も第一次人工知能ブームの時に開発された技術です．『探索』とは，いろいろな組み合わせの中から答えを見つけ出す，問題を解く方法です．

我々人間も，探すモノや探す場所によって探し方を変えています．例えば、机の引き出しの中に大事にしまっておいた物がなくなった時には，ひとまずその机の引き出しを調べてみます．そして，その想定していた引き出しに探している物がなかったら，今度は別の引き出し、それでもなかったら同じ部屋の本棚・・・というように探していくかと思います．

また，家の中で鍵をなくした時には、家のどこに置いたのかがよく思い出せないので、とりあえずザーッと見て回ります．そして，それでもなかったら、今度は，玄関の下駄箱とかリビングの棚とかを一つひとつ詳しく見ていくという探し方をするのではないでしょうか．

コンピュータでも同じように、まずは広くザーッっと調べて、徐々により詳しく調べていって答えを見つけるという方法があります。これを『横型探索』、『幅優先探索』と呼びます。また逆に、一つのことを詳しく、さらにより詳しく調べて、答えが見つからなかったら別のことをまた詳しく調べていくという方法があります。これを先ほどの「横」、「幅」に対応させて『縦型探索』、『深さ優先探索』と呼びます。

どちらの答えの探し方が良いのかは、実はやってみないとわかりません。先ほどの大事な物や鍵の場合であれば、何を探すのか、どこで探せばよいのかがわかっていますので、どちらの探し方の方が良いのかは想像できます。しかし例えば、「小さい子供が大きくなったときに偉い人になるためには、どう勉強すればよいか」などの疑問の答えはよくわかりません。

そのため、義務教育では、算数や国語、理科や社会、体育、音楽、図工などたくさんのことを勉強しています。しかも、小学校1年生、２年生と同じ科目だけれど徐々に難しい内容になっていきます。つまり、『横型探索』をしていることになります。

でも、それだけではいけません。特に興味のある、面白いと思うもの、好きなものについては、もっともっと自分で自由に勉強して、人よりも詳しく知ることもできます．これは『縦型探索』をするということになります。

次回は，より知的な探索方法である遺伝的アルゴリズム（GA）についてについて書いてみたいと思います．