左手法
探索アルゴリズムの代表的なものとして、左手法がある。
洞窟の中に入ったときに左手(右手でもかまわない)にそって
道を進むことで必ずゴールにつけるというものだ。
しかし、マウスの大会のルールで、ゴールは中央4マスとなっているので
左手法ではゴールに着くことはできない。
そのため、拡張左手法が、初心者が大会ルールでゴールにたどり着くための
アルゴリズムとして一般的だ。(詳しくは、芝浦のHPでも見てください。)
とはいえ、拡張左手法では、ゴールまでの最短経路を求めるのに時間がかかるため、
足立法というアルゴリズムがマイクロマウス界では最短ルートを求める方法としては一般的である。
拡張左手法
拡張左手法とは、左手法では迷路の真ん中にゴールがあった場合に
ゴールに到達できないといった問題を解決するものです。
具体的には、迷路の分岐点で左側に壁がなく、また一度入ったことがある区画に
ぶつかった際、左側に仮想壁を立て、既知の区画に戻らないようにする方法です。
気をつけるべきは、袋小路に入った際に、分岐点までもどり、再度袋小路に入らないように
自分の後ろに仮想壁を立てる必要があることです。分岐点までもどれるようにしておかないと、
袋小路に入った際に反転して、戻るときに戻ろうとした区画が既知であるために仮想壁を立ててしまい
その区画からでられなくなるといったことがおきるからです。
足立法
足立法とは、ゴールまでの最短経路をあらかじめ設定しておき、壁にぶつかるごとに
最短経路を求めなおすというものである。その際、歩数マップを作成し、
ゴールまでの歩数を計測していき、ゴールしたら歩数の少ないほうへと
走ることで、最短経路を走れます。
ちなみに現在は医師である足立芳彦氏が福山マイコンクラブ時代(1984年、当時高校生)に発表したものです。
だから足立法。
求心法
ゴールに近くなるほど評価値が低くなっていき、分岐路の判断基準が
その評価値の低いほうへと進むアルゴリズム。
くわしくは芝浦をみて。