グラフのはなし・その6
さて, 今日からは探索やソートの話をしていきます.
探索やソートについては以前も触れましたが, ここで簡単におさらいをしておきます.
ソート (sort) とは
ソートは日本語に訳すと「並びかえ」になります. 文字通りなんらかの順序でものを並べかえる作業のことです.
人間が並びかえることもありますが, ソートと専門用語っぽく言ったときはコンピュータ (計算機) が並びかえる作業を指します.
探索 (search) とは
探索とは文字通り何かを探すことです. これもソートと同様コンピュータが何かを探す作業のことを指します.
人間とコンピュータ
人間がソートや探索をする場合には, 全体を見てなんとなく並びかえたり, だいたいここらへんにあるだろうと当たりを付けたりします. 人間 (生物) の脳が素晴しいのはこういった曖昧な処理や直感的な決定, 判断が行えることです.
それに比べコンピュータは (良く言われることですが) はっきり決めないと動いてくれません. なんせ中の仕組み (CPU やメモリ) がすごくシンプルなため, そのような処理はコンピュータにとっては高度で難しいことなのです.
深さ優先探索 (DFS)
さて, 何の話から始めようかと考えましたが, トポロジカルソートの話をするには深さ優先探索が必要なのでこれから話していきます.
迷路を進む
まず「深さ優先」って何? となると思いますが, これは探索の戦略を表しています. 巨大な迷路を進むことを考えてみましょう. イメージはこんな感じ. 迷路のゴールが探索のゴールとします
何も道具を使わないのは厳しいので, ヘンゼルとグレーテルを見習ってたくさん小石を地面に置く目印に使っていいことにしましょう.
さて, ではこの小石をどう使いましょうか?
ヘンゼルのように歩きながら小石を道に落としていきましょうか?
でもそれでどうやってゴールを探し出せば良いのでしょうか?
闇雲に歩きながら目印を落としても, 一度辿ったところは分かるのですが次にどこを探せば良いのか分からないですね.
おっと言い忘れましたが, この迷路は立体迷路なので右の壁づたいに進むとスタートに戻る可能性があります. 頭の良い人はこの方法を思い付いたかもしれませんが, それは平面の迷路でしか使えない手段です.
さっきちょっと書いた「次にどこを探せば良いのか」というのがヒントです.
さて思い付きましたか? (あ, 引っ張りすぎ??)
答えはこうです.
ゴールの探し方
歩きながら小石を落としていくことはするのですが, 一本道を歩いているときはもったいないので小石は落としません. 分かれ道に来たときに初めて小石を使います.
まず道がいくつかに分かれているところに来たら, 一番右の分かれ道に小石を 1 つ置いてその先へ進んでいきます. 分かれ道にくるたびに同じことをします.
するとゴールへ辿り着くか, どこかで行き止まりになるか, 小石が置かれた分かれ道に出るか, になりますね. ゴールならそこを出て迷路はクリアです.
行き止まりなら, 来た道を引き返して直前に小石を置いたところまで戻ります. その小石から行き止まりまでは一本道だったので, もうその道は探索しなくて良いですね? ここがポイントです.「もうその道は探索しなくて良い」ということが言えることが重要です.
小石が置かれていた分かれ道に出たなら, その分かれ道にはすでに一度来たことがあるはずです. 引き返す前に「もうこの分かれ道は辿ったよ」という印を置いて, 元来た道を帰りましょう.
さて分かれ道に戻って何をしましょう. 戻ってきた道が一番右の分かれ道だったので, その 1 つ左の道を同じく小石を置いて進みましょう. こんなふうに,
- 分かれ道に来たら右端の分かれ道に小石を置いて進む.
- 行き止まりか小石が置かれている分かれ道に出たら引き返して小石を置いたところまで戻る.
- 小石を置いた道の 1 つ左の道を進む.
以下, 道を選んで, 進んで, 戻って, また道を選ぶの繰り返しになります.
この方法でゴールが見付かる保証はちゃんとあります. (当然ちゃんとゴールがあれば, ですが...) しかも同じ道を 2 回探索しないで済む保証もあります.
なぜかと言うと, 分かれ道に来たときに全ての分岐を 1 回だけ探索しています. そして一度探索した道には小石を置いて 2 回以上探索しないようにしています. なのでこの方法でゴールが探し出せることになります.
あとがき
昨日は疲れで休んでしまいました. すみません.
この連載が更新されなかったときは仕事が忙しいんだな, と思ってくださいm(_ _)m
さて, 今日は探索戦略の 1 つ深さ優先探索のお話をしました. どう感じたでしょうか? いちいち事細かにやるのは煩わしいと思ったでしょうか? 本当にこれでゴールに辿り着けるのか不思議に思ったでしょうか? なるほどこういう方法もあったのか, と感心されたでしょうか?
それぞれ思うことはあるでしょうが, この方法はコンピュータだからできる, もしくはコンピュータだからせざるを得ない方法です. コンピュータは「今いるところが分かれ道かどうか」と「道を 1 つ進む」と「道を 1 つ戻る」の 3 つしかできません. その 3 つしかない方法を組み合わせてなんとか迷路を解くためには, こういった方法になります.
まずは,「コンピュータはできることを減らしたかわりに, 高速で作業ができるようになった」ということを感覚として持っておいてください. 今後も繰り返し言っていくと思います.
それでは.
