探索問題

探索問題 スタート地点からゴール地点までの経路を探索するような問題は探索問題と呼ばれている。解法を単純に考えると端からくまなく調べていくことになるが、いけるところまで深く進んで、だめなら少し戻って…を繰り返す深さ優先探索と、今いる場所から進める方向すべてに一歩だけ試す幅優先探索がある。 筋がいい？のは幅優先探索のほうであるが、これも結局なめて回る以上深くなるほど指数関数的に調べる経路が増えてしまう。そこで、今いる場所、一歩進んだ場所の良さ加減がわかる評価関数があると、ゴールに近そうな一歩を踏み出せるため効率が上がる。このような関数で評価しながら進む幅優先探索を最良優先探索という。 最短経路問題…