|新しいページ|検索|ページ一覧|RSS|@ウィキご利用ガイド | 管理者にお問合せ
|ログイン|

拡張左手法

※上記の広告は60日以上更新のないWIKIに表示されています。更新することで広告が下部へ移動します。

拡張左手法

拡張左手法の欠点、及び、探索が終わった後の最短経路導出方法について述べる。
下の迷路を例に拡張左手法でゴールしてみる。

         
①まずは、左手法で迷路内を探索する。


②次の区画が既知であった場合仮想壁を立てる。

欠点1:このとき、次の分岐が来るまで仮想壁を立てないようにしないと、マウスが下図のようにはまってしまう。


③これまでの道筋を歩数マップとして下図のように歩数を記録。
歩数のカウントルールは、直進は+1、方向転換は+2
袋小路に入ったら次の分岐までカウントはなし。


④ゴールからスタートへ番号の少ないほうへたどっていけば、それが最短経路となる。
このとき、大きい迷路だと同じ歩数の経路が2つ以上でる可能性があるが、
そのときは、直線が多いほうを選ぶといい。理由はマウスが直線のほうが安定して早く走れるから。


欠点その2:下図の迷路の場合


①仮想壁を立ててゴールすると


②仮想壁がある迷路を抜けようとすると最短経路ではない
経路を進んでしまう。


③なので、仮想壁を使用していない迷路を作っておき、そっちで最短経路を割り出す必要がある。


おまけ
拡張左手はとにかく時間がかかるので、
封印壁(コの字型の区画を見つけたらそこに仮想壁を立て、無駄な探索を減らす)
を追加した拡張左手法を先輩方は考えていたっぽい。










    
                              

Menu

更新履歴

取得中です。