探索アルゴリズム

探索問題

スタート地点からゴール地点までの経路を探索するような問題は探索問題と呼ばれている。解法を単純に考えると端からくまなく調べていくことになるが、いけるところまで深く進んで、だめなら少し戻って…を繰り返す深さ優先探索と、今いる場所から進める方向すべてに一歩だけ試す幅優先探索がある。

筋がいい？のは幅優先探索のほうであるが、これも結局なめて回る以上深くなるほど指数関数的に調べる経路が増えてしまう。そこで、今いる場所、一歩進んだ場所の良さ加減がわかる評価関数があると、ゴールに近そうな一歩を踏み出せるため効率が上がる。このような関数で評価しながら進む幅優先探索を最良優先探索という。

最短経路問題

例えば、スタート地点からゴール地点までの距離を最短にする経路を見つける問題を考える。これは一般には最短経路問題とよばれるが、このとき、評価関数としてスタート地点からその場所までの距離（コスト関数）をとる方法がダイクストラ法で、最短経路問題の基本アルゴリズムである。この改良版として、ゴールまでの近さ加減を何らかの関数（ヒューリスティック関数という）で表しコスト関数に加えたものを評価関数にする方法がA*アルゴリズムである。

次回

将棋や囲碁などのゲームの場合は相手がいたりしてもう少し込み入った話になる。次回はそのあたりを勉強したい。