Micromouse_zero @Wiki

足立法

最終更新:

匿名ユーザー

- view
だれでも歓迎! 編集
足立法(歩数マップ)

足立法とは、最短経路を求めながら迷路を探索していく探索アルゴリズムである。
しかし、最短経路を求める方法について、具体的に解説しているサイトはないので
ここでは、歩数マップを使用して最短経路を求めてみた。
尚、等高線マップを使用したものは、足立法と同じと考えて問題ない。

歩数マップを使うには、歩数マップ作成のルールを決める必要がある。
歩数マップルール
1、 直進は+1、旋回は+2 (180度旋回は考えない。)
2、 ゴール地点を0とし、マウスは北を向いているものとする。
3、 すでに歩数が入っていた場合、新しい歩数が小さかった時に、更新する。

足立法について、下の迷路を実際に足立法で探索しながら、説明していく。


①スタート地点までの歩数マップを作成する。


②スタート地点から、数字の少ないほうに進む。
ただし、壁があったらそこで止まり、再び歩数マップを考える。


③壁を考慮して、再び歩数マップを作成する。


④ ②で止まったところから、壁に阻まれるまで進んでいく。


⑤再びマップを作成する。


⑥ゴールまで進んで、終わり。



拡張左手に比べ、大きい迷路ではゴールに向かって一直線に進んでいく足立法だが、
全ての区画を探索するわけではないので、時として、一番短い道を選んでいるわけではない場合もある。
それを克服するためには、ゴールに到着した後、未探索の区画を選んで探索する必要などがある。


タグ:

+ タグ編集
  • タグ:

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

記事メニュー
人気記事ランキング
目安箱バナー