幅優先探索

こんばんはsejiです。

第2回目、幅優先探索をやってきました。

幅優先探索は最短路を求めるプログラムに向いています。(初心者なので確かなことは言えませんが、

実際に再帰で書いたプログラムよりも早くなっていることは確かだと思います。

迷路に関しては幅優先が圧倒的に早いと感じました。再帰は解が見つかるまで、行ったり来たりー

幅優先は一度きたところは目印して次に進みます。だから戻る必要がないのでその分、早くなりました。

続きを読む »

パソコン甲子園の準備

おはようございます。

午前中から記事を書いていきたいと思います。

今回記事は、パソコン甲子園本選出場が決まっていたのですが、今まで競技に対して準備する期間がありませんでした。

プロコンやら弥生祭やら・・・。まあ、それは置いておいて、後1週間弱あるので、できることをやっていこうと思います。

今日、ごにょごにょしたのは、迷路の解を見つけるプログラムです。

少し長くなると思い、2回に分けたいと思います。

解説をするとかなり長くなってしまいそうなので、アルゴリズムに関しては結果だけにさせてもらいます。

まず、第1は再帰による解を見つける、第2は幅優先探索による探索で最短距離を求めたいと思います。

再帰でも求められないこともないですが、迷路が大きくなってくると帰ってこなくなるので、やめましょうw

続きを読む »