こんばんはsejiです。

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

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

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

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

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

前回同様画像が多いですが、許してください。

まず、５ｘ５。テストデータが悪かったですね。最短かどうかわかりずらい・・・・。

次行きましょうｗ

１０ｘ１０・・・・。また、テストデータが悪いですね。前回のものを流用したので許してください

おっ、in8.txtは１８でゴールできています！

あと、前回はin10.txtは長すぎて強制終了したのですが、今回は一瞬で解が飛んできました。（１秒もかかってないです

最後１５ｘ１５

こちらもうまく解を出せているようです！

要素数がぐんと増えても幅優先のプログラムなら対応できそうです！！！！

振り替えって・・・。

プログラムは問題によって適切に選ぶべきだと改めて実感しました。

１つの手段しか知らないより、いくつもの手段の中から適切な手段を見つけ出すことができれば、よりいいものができると思います。

正直、幅優先探索は今回初めて書いたのでとっつきにくいような感じでしたが、いざ書いてみるとこれは強い！って思いました。ただ、使う用途は少ないかもしれません。

ソースコードは前回のところにあると思います。

では、失礼

Tweet