拡張左手法の欠点、及び、探索が終わった後の最短経路導出方法について述べる。
下の迷路を例に拡張左手法でゴールしてみる。
①まずは、左手法で迷路内を探索する。
②次の区画が既知であった場合仮想壁を立てる。
欠点1:このとき、次の分岐が来るまで仮想壁を立てないようにしないと、マウスが下図のようにはまってしまう。
③これまでの道筋を歩数マップとして下図のように歩数を記録。
歩数のカウントルールは、直進は+1、方向転換は+2
袋小路に入ったら次の分岐までカウントはなし。
④ゴールからスタートへ番号の少ないほうへたどっていけば、それが最短経路となる。
このとき、大きい迷路だと同じ歩数の経路が2つ以上でる可能性があるが、
そのときは、直線が多いほうを選ぶといい。理由はマウスが直線のほうが安定して早く走れるから。
欠点その2:下図の迷路の場合
①仮想壁を立ててゴールすると
②仮想壁がある迷路を抜けようとすると最短経路ではない
経路を進んでしまう。
③なので、仮想壁を使用していない迷路を作っておき、そっちで最短経路を割り出す必要がある。
おまけ
拡張左手はとにかく時間がかかるので、
封印壁(コの字型の区画を見つけたらそこに仮想壁を立て、無駄な探索を減らす)
を追加した拡張左手法を先輩方は考えていたっぽい。