足立法 - (2005/07/20 (水) 18:50:54) の最新版との変更点
追加された行は緑色になります。
削除された行は赤色になります。
<strong><font color=
"#993300">足立法(歩数マップ)<br></font></strong>
<hr>
<font color=
"#993300">足立法とは、最短経路を求めながら迷路を探索していく探索アルゴリズムである。<br>
しかし、最短経路を求める方法について、具体的に解説しているサイトはないので<br>
ここでは、歩数マップを使用して最短経路を求めてみた。<br>
<br>
歩数マップを使うには、歩数マップ作成のルールを決める必要がある。<br>
<u>歩数マップルール</u><br>
1、 直進は+1、旋回は+2 (180度旋回は考えない。)<br>
2、 ゴール地点を0とし、マウスは北を向いているものとする。<br>
↑の歩数マップルールに従って下の迷路を実際に足立法で探索しながら、説明していく。<br>
<img src=
"http://www4.atwiki.jp/zero_one/?cmd=upload&act=open&pageid=28&file=%E6%8B%A1%E5%BC%B5%E5%B7%A6%E6%89%8Berror_1.png">
<br>
<br>
①スタート地点までの歩数マップを作成する。<br>
<img src=
"http://www4.atwiki.jp/zero_one/?cmd=upload&act=open&pageid=28&file=%E8%B6%B3%E7%AB%8B1.png">
<br>
<br>
②スタート地点から、数字の少ないほうに進む。<br>
ただし、壁があったらそこで止まり、再び歩数マップを考える。<br>
<img src=
"http://www4.atwiki.jp/zero_one/?cmd=upload&act=open&pageid=28&file=%E8%B6%B3%E7%AB%8B_%E5%AE%9F%E9%9A%9B_1.png">
<br>
<br>
③壁を考慮して、再び歩数マップを作成する。<br>
<img src=
"http://www4.atwiki.jp/zero_one/?cmd=upload&act=open&pageid=28&file=%E8%B6%B3%E7%AB%8B2.png">
<br>
<br>
④ ②で止まったところから、壁に阻まれるまで進んでいく。<br>
<img src=
"http://www4.atwiki.jp/zero_one/?cmd=upload&act=open&pageid=28&file=%E8%B6%B3%E7%AB%8B_%E5%AE%9F%E9%9A%9B_2.png">
<br>
<br>
⑤再びマップを作成する。<br>
<img src=
"http://www4.atwiki.jp/zero_one/?cmd=upload&act=open&pageid=28&file=%E8%B6%B3%E7%AB%8B3.png">
<br>
<br>
⑥ゴールまで進んで、終わり。<br>
<img src=
"http://www4.atwiki.jp/zero_one/?cmd=upload&act=open&pageid=28&file=%E8%B6%B3%E7%AB%8B_%E5%AE%9F%E9%9A%9B_3.png">
<br>
<br>
<br>
拡張左手に比べ、大きい迷路ではゴールに向かって一直線に進んでいく足立法だが、<br>
全ての区画を探索するわけではないので、時として、一番短い道を選んでいるわけではない場合もある。<br>
それを克服するためには、ゴールに到着した後、未探索の区画を選んで探索する必要などがある。<br>
<br>
<br></font>
<strong><font color=
"#993300">足立法(歩数マップ)<br></font></strong>
<hr>
<font color=
"#993300">足立法とは、最短経路を求めながら迷路を探索していく探索アルゴリズムである。<br>
しかし、最短経路を求める方法について、具体的に解説しているサイトはないので<br>
ここでは、歩数マップを使用して最短経路を求めてみた。<br>
尚、等高線マップを使用したものは、足立法と同じと考えて問題ない。<br>
<br>
歩数マップを使うには、歩数マップ作成のルールを決める必要がある。<br>
<u>歩数マップルール</u><br>
1、 直進は+1、旋回は+2 (180度旋回は考えない。)<br>
2、 ゴール地点を0とし、マウスは北を向いているものとする。<br>
3、 すでに歩数が入っていた場合、新しい歩数が小さかった時に、更新する。<br>
<br>
足立法について、下の迷路を実際に足立法で探索しながら、説明していく。<br>
<img src=
"http://www4.atwiki.jp/zero_one/?cmd=upload&act=open&pageid=28&file=%E6%8B%A1%E5%BC%B5%E5%B7%A6%E6%89%8Berror_1.png">
<br>
<br>
①スタート地点までの歩数マップを作成する。<br>
<img src=
"http://www4.atwiki.jp/zero_one/?cmd=upload&act=open&pageid=28&file=%E8%B6%B3%E7%AB%8B1.png">
<br>
<br>
②スタート地点から、数字の少ないほうに進む。<br>
ただし、壁があったらそこで止まり、再び歩数マップを考える。<br>
<img src=
"http://www4.atwiki.jp/zero_one/?cmd=upload&act=open&pageid=28&file=%E8%B6%B3%E7%AB%8B_%E5%AE%9F%E9%9A%9B_1.png">
<br>
<br>
③壁を考慮して、再び歩数マップを作成する。<br>
<img src=
"http://www4.atwiki.jp/zero_one/?cmd=upload&act=open&pageid=28&file=%E8%B6%B3%E7%AB%8B2.png">
<br>
<br>
④ ②で止まったところから、壁に阻まれるまで進んでいく。<br>
<img src=
"http://www4.atwiki.jp/zero_one/?cmd=upload&act=open&pageid=28&file=%E8%B6%B3%E7%AB%8B_%E5%AE%9F%E9%9A%9B_2.png">
<br>
<br>
⑤再びマップを作成する。<br>
<img src=
"http://www4.atwiki.jp/zero_one/?cmd=upload&act=open&pageid=28&file=%E8%B6%B3%E7%AB%8B3.png">
<br>
<br>
⑥ゴールまで進んで、終わり。<br>
<img src=
"http://www4.atwiki.jp/zero_one/?cmd=upload&act=open&pageid=28&file=%E8%B6%B3%E7%AB%8B_%E5%AE%9F%E9%9A%9B_3.png">
<br>
<br>
<br>
拡張左手に比べ、大きい迷路ではゴールに向かって一直線に進んでいく足立法だが、<br>
全ての区画を探索するわけではないので、時として、一番短い道を選んでいるわけではない場合もある。<br>
それを克服するためには、ゴールに到着した後、未探索の区画を選んで探索する必要などがある。<br>
<br>
<br></font>
表示オプション
横に並べて表示:
変化行の前後のみ表示: