拡張左手法の編集 - Micromouse_zero @Wiki - atwiki（アットウィキ）

拡張左手法の編集ワープロモード(改行はシフト＋エンター)

拡張左手法<hr />拡張左手法の欠点、及び、探索が終わった後の最短経路導出方法について述べる。 下の迷路を例に拡張左手法でゴールしてみる。 <img src="//www4.atwiki.jp/zero_one/?cmd=upload&act=open&pageid=25&file=%E6%8B%A1%E5%BC%B5%E5%B7%A6%E6%89%8B_1.png" alt="?cmd=upload&act=open&pageid=25&file=%E6%8B%A1%E5%BC%B5%E5%B7%A6%E6%89%8B_1.png" /> 　　　　　　　　　 ①まずは、左手法で迷路内を探索する。 <img src="//www4.atwiki.jp/zero_one/?cmd=upload&act=open&pageid=25&file=%E6%8B%A1%E5%BC%B5%E5%B7%A6%E6%89%8B_2.png" alt="?cmd=upload&act=open&pageid=25&file=%E6%8B%A1%E5%BC%B5%E5%B7%A6%E6%89%8B_2.png" /> ②次の区画が既知であった場合仮想壁を立てる。 <img src="//www4.atwiki.jp/zero_one/?cmd=upload&act=open&pageid=25&file=%E6%8B%A1%E5%BC%B5%E5%B7%A6%E6%89%8B_3.png" alt="?cmd=upload&act=open&pageid=25&file=%E6%8B%A1%E5%BC%B5%E5%B7%A6%E6%89%8B_3.png" />欠点１：このとき、次の分岐が来るまで仮想壁を立てないようにしないと、マウスが下図のようにはまってしまう。 <img src="//www4.atwiki.jp/zero_one/?cmd=upload&act=open&pageid=25&file=%E6%8B%A1%E5%BC%B5%E5%B7%A6%E6%89%8B_error_1.png" alt="?cmd=upload&act=open&pageid=25&file=%E6%8B%A1%E5%BC%B5%E5%B7%A6%E6%89%8B_error_1.png" /> ③これまでの道筋を歩数マップとして下図のように歩数を記録。 歩数のｶｳﾝﾄルールは、直進は＋１、方向転換は＋２ 袋小路に入ったら次の分岐までｶｳﾝﾄはなし。 <img src="//www4.atwiki.jp/zero_one/?cmd=upload&act=open&pageid=25&file=%E6%8B%A1%E5%BC%B5%E5%B7%A6%E6%89%8B_4.png" alt="?cmd=upload&act=open&pageid=25&file=%E6%8B%A1%E5%BC%B5%E5%B7%A6%E6%89%8B_4.png" /> ④ゴールからスタートへ番号の少ないほうへたどっていけば、それが最短経路となる。 このとき、大きい迷路だと同じ歩数の経路が２つ以上でる可能性があるが、 そのときは、直線が多いほうを選ぶといい。理由はマウスが直線のほうが安定して早く走れるから。 <img src="//www4.atwiki.jp/zero_one/?cmd=upload&act=open&pageid=25&file=%E6%8B%A1%E5%BC%B5%E5%B7%A6%E6%89%8B_5.png" alt="?cmd=upload&act=open&pageid=25&file=%E6%8B%A1%E5%BC%B5%E5%B7%A6%E6%89%8B_5.png" /> 欠点その２：下図の迷路の場合 <img src="//www4.atwiki.jp/zero_one/?cmd=upload&act=open&pageid=25&file=%E6%8B%A1%E5%BC%B5%E5%B7%A6%E6%89%8B1_1.png" alt="?cmd=upload&act=open&pageid=25&file=%E6%8B%A1%E5%BC%B5%E5%B7%A6%E6%89%8B1_1.png" /> ①仮想壁を立ててゴールすると <img src="//www4.atwiki.jp/zero_one/?cmd=upload&act=open&pageid=25&file=%E6%8B%A1%E5%BC%B5%E5%B7%A6%E6%89%8B2_1.png" alt="?cmd=upload&act=open&pageid=25&file=%E6%8B%A1%E5%BC%B5%E5%B7%A6%E6%89%8B2_1.png" /> ②仮想壁がある迷路を抜けようとすると最短経路ではない 経路を進んでしまう。 <img src="//www4.atwiki.jp/zero_one/?cmd=upload&act=open&pageid=25&file=%E6%8B%A1%E5%BC%B5%E5%B7%A6%E6%89%8B1-3.png" alt="?cmd=upload&act=open&pageid=25&file=%E6%8B%A1%E5%BC%B5%E5%B7%A6%E6%89%8B1-3.png" /> ③なので、仮想壁を使用していない迷路を作っておき、そっちで最短経路を割り出す必要がある。 <img src="//www4.atwiki.jp/zero_one/?cmd=upload&act=open&pageid=25&file=%E6%8B%A1%E5%BC%B5%E5%B7%A6%E6%89%8B1_4.png" alt="?cmd=upload&act=open&pageid=25&file=%E6%8B%A1%E5%BC%B5%E5%B7%A6%E6%89%8B1_4.png" /> おまけ 拡張左手はとにかく時間がかかるので、 封印壁（コの字型の区画を見つけたらそこに仮想壁を立て、無駄な探索を減らす） を追加した拡張左手法を先輩方は考えていたっぽい。

このサイトはreCAPTCHAによって保護されており、Googleのプライバシーポリシーと利用規約が適用されます。

>> タグ :

「拡張左手法」にアップロードされたファイル一覧

	ファイル名	更新日時
	拡張左手1-3.png	2005/07/15 (金) 14:45:42
	拡張左手1_1.png	2005/07/15 (金) 14:45:53
	拡張左手1_4.png	2005/07/15 (金) 14:55:17
	拡張左手2_1.png	2005/07/15 (金) 14:46:05
	拡張左手_1.png	2005/07/15 (金) 14:31:10
	拡張左手_2.png	2005/07/15 (金) 14:31:24
	拡張左手_3.png	2005/07/15 (金) 14:31:33
	拡張左手_4.png	2005/07/15 (金) 14:31:42
	拡張左手_5.png	2005/07/15 (金) 14:31:50
	拡張左手_error_1.png	2005/07/15 (金) 14:45:29

Micromouse_zero @Wiki

記事メニュー