幅優先探索

こんばんはsejiです。

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

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

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

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

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

 

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

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

次行きましょうw

5bfs

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

10.1bfs

おっ、in8.txtは18でゴールできています!

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

10.2bfs

最後15x15

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

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

15.1bfs

15.2bfs


振り替えって・・・。

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

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

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

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

では、失礼

 


コメントを残す

メールアドレスが公開されることはありません。