
http://www.suzukisoft.co.jp/products/robochart/
以下は、とあるクラスの授業記録です。
08:30 二人一組になります。前回はかめを進ませましたが、今回はねずみです。
今日はフローチャートを用いて順番を考えながら出口へ導いて
08:38 レベル1「はい、やってみよう!」
今日は保存しますか。
08:41 レベル2「ノーヒントでやってもらいましょうか」
08:83 繰り返し記号の説明。「10回繰り返す」。
これが一番シンプル。アルゴリズムは同じ動作ならできるだけシンプルなものが良い。
08:44 レベル3。行ってみよう。
08:50 レベル4
08:52 「出口か?」がいいえの間であればどちらでもいいよ。
「汎用性」のあるものがよいアルゴリズム。
08:53 レベル5に行きましょう
08:56 レベル6
条件分岐が必要になります。
09:06 「右前は壁か?」って何のためかわかる?巨大迷路の抜け方知っている人いる?「右手の法則」どんな迷路でも抜けられるプログラムも作れるよ。サンプル見せる。
09:10 終了
自分もこのソフトを持っているのですが、どんな迷路でも抜けられるプログラムと書いてあったのがとても興味深く、コメントをさせていただきました。
もしよろしければ、ご教授してはいただけないでしょうか。
いきなりで失礼とは重々承知しておりますが、よろしくお願いいたします。
右手法というものはご存じでしょうか。
> 右手法
>
> 右側の壁に手を付いて、ひたすら壁沿いに進むという方法である(右側の壁の代わりに左側の壁に手をついても本質的には同じ)。
>
> 壁の切れ目は迷路の入口と出口にしかないので、右手法を使うと最終的には、入口に戻ってしまうか出口に到達するかのいずれかになる。
>
> 最短経路でゴールにたどりつけるとは限らないが、最悪でも壁の長さ分だけ歩けば終了する。
http://ja.wikipedia.org/wiki/%E8%BF%B7%E8%B7%AF
つまり、「右は壁か」、「右前は壁か」を判断して、壁でなかったら通路なわけですから、角にそってぐるりと廻るアルゴリズムを作れば、ずっと壁に沿って進んでいくことができます。
ひたすら壁づたいに歩いていけば、いつかは出口にたどり着くわけです。
引用元を見ていただければ、それだけではたどり着かない迷路(無限ループになるもの)があります。そこで、例えば89回(大きな奇数であれば良い)歩いたら逆向きに進むようにしておくと、左壁が右壁に変わりますので、出口にたどり着きます。
よくよく考えて見てください。
引用していただいたURLも参考にさせていただきながら、最短距離にこだわらず、壁づたいで気長に試してみたいと思います。
本当にありがとうございました。