「拡張左手法」(2005/07/15 (金) 15:01:11) の最新版変更点
追加された行は緑色になります。
削除された行は赤色になります。
<p><font color="#993300"><strong>拡張左手法</strong></font></p>
<hr>
<p><font color="#993300"><font color=
"#663333">拡張左手法の欠点、及び、探索が終わった後の最短経路導出方法について述べる。<br>
下の迷路を例に拡張左手法でゴールしてみる。<br>
<img src=
"http://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">
<br>
<br>
①まずは、左手法で迷路内を探索する。<br>
<img src=
"http://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">
<br>
<br>
②次の区画が既知であった場合仮想壁を立てる。<br>
<img src=
"http://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">
</font></font></p>
<p><font color="#993300"><font color=
"#663333">欠点１：このとき、次の分岐が来るまで仮想壁を立てないようにしないと、マウスが下図のようにはまってしまう。<br>
<img src=
"http://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">
<br>
<br>
③これまでの道筋を歩数マップとして下図のように歩数を記録。<br>
歩数のｶｳﾝﾄルールは、直進は＋１、方向転換は＋２<br>
袋小路に入ったら次の分岐までｶｳﾝﾄはなし。<br>
<img src=
"http://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">
<br>
<br>
④ゴールからスタートへ番号の少ないほうへたどっていけば、それが最短経路となる。<br>
このとき、大きい迷路だと同じ歩数の経路が２つ以上でる可能性があるが、<br>
そのときは、直線が多いほうを選ぶといい。理由はマウスが直線のほうが安定して早く走れるから。<br>
<img src=
"http://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">
<br>
<br>
欠点その２：下図の迷路の場合<br>
<img src=
"http://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">
<br>
<br>
①仮想壁を立ててゴールすると<br>
<img src=
"http://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">
<br>
<br>
②仮想壁がある迷路を抜けようとすると最短経路ではない<br>
経路を進んでしまう。<br>
<img src=
"http://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">
<br>
<br>
③なので、仮想壁を使用していない迷路を作っておき、そっちで最短経路を割り出す必要がある。<br>
<img src=
"http://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">
<br>
<br>
<strong>おまけ</strong><br>
拡張左手はとにかく時間がかかるので、<br>
封印壁（コの字型の区画を見つけたらそこに仮想壁を立て、無駄な探索を減らす）<br>
を追加した拡張左手法を先輩方は考えていたっぽい。<br>
<br>
<br>
<br>
<br>
<br>
<br>
<br>
<br>
<br>
<br>
<br>
<br>
</font></font></p>
<font color="#993300"><strong>拡張左手法</strong></font>
<hr>
<p><font color="#993300"><font color=
"#663333">拡張左手法の欠点、及び、探索が終わった後の最短経路導出方法について述べる。<br>
下の迷路を例に拡張左手法でゴールしてみる。<br>
<img src=
"http://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">
<br>
<br>
①まずは、左手法で迷路内を探索する。<br>
<img src=
"http://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">
<br>
<br>
②次の区画が既知であった場合仮想壁を立てる。<br>
<img src=
"http://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">
</font></font></p>
<p><font color="#993300"><font color=
"#663333">欠点１：このとき、次の分岐が来るまで仮想壁を立てないようにしないと、マウスが下図のようにはまってしまう。<br>
<img src=
"http://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">
<br>
<br>
③これまでの道筋を歩数マップとして下図のように歩数を記録。<br>
歩数のｶｳﾝﾄルールは、直進は＋１、方向転換は＋２<br>
袋小路に入ったら次の分岐までｶｳﾝﾄはなし。<br>
<img src=
"http://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">
<br>
<br>
④ゴールからスタートへ番号の少ないほうへたどっていけば、それが最短経路となる。<br>
このとき、大きい迷路だと同じ歩数の経路が２つ以上でる可能性があるが、<br>
そのときは、直線が多いほうを選ぶといい。理由はマウスが直線のほうが安定して早く走れるから。<br>
<img src=
"http://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">
<br>
<br>
欠点その２：下図の迷路の場合<br>
<img src=
"http://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">
<br>
<br>
①仮想壁を立ててゴールすると<br>
<img src=
"http://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">
<br>
<br>
②仮想壁がある迷路を抜けようとすると最短経路ではない<br>
経路を進んでしまう。<br>
<img src=
"http://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">
<br>
<br>
③なので、仮想壁を使用していない迷路を作っておき、そっちで最短経路を割り出す必要がある。<br>
<img src=
"http://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">
<br>
<br>
<strong>おまけ</strong><br>
拡張左手はとにかく時間がかかるので、<br>
封印壁（コの字型の区画を見つけたらそこに仮想壁を立て、無駄な探索を減らす）<br>
を追加した拡張左手法を先輩方は考えていたっぽい。<br>
<br>
<br>
<br>
<br>
<br>
<br>
<br>
<br>
<br>
<br>
<br>
<br>
</font></font></p>
表示オプション
横に並べて表示：
変化行の前後のみ表示：
