探索アルゴリズム - (2005/07/12 (火) 18:24:23) の編集履歴(バックアップ)
探索アルゴリズムについて
探索アルゴリズムの代表的なものとして、左手法がある。
洞窟の中に入ったときに左手（右手でもかまわない）にそって
道を進むことで必ずゴールにつけるというものだ。
しかし、マウスの大会のルールで、ゴールは中央４マスとなっているので
左手法ではゴールに着くことはできない。
そのため、拡張左手法が、初心者が大会ルールでゴールにたどり着くための
アルゴリズムとして一般的だ。（詳しくは、芝浦のHPでも見てください。）
とはいえ、拡張左手法では、ゴールまでの最短経路を求めるのに時間がかかるため、
足立法というアルゴリズムがマイクロマウス界では最短ルートを求める方法としては一般的である。
足立法
足立法とは、ゴールまでの最短経路をあらかじめ設定しておき、壁にぶつかるごとに
最短経路を求めなおすというものである。その際、歩数マップを作成し、
ゴールまでの歩数を計測していき、ゴールしたら歩数の少ないほうへと
走ることで、最短経路を走れます。
求心法
ゴールに近くなるほど評価値が低くなっていき、分岐路の判断基準がその評価値の低いほう
へと進むアルゴリズム。
くわしくは芝浦をみて。
と、まぁこんな感じのがメインで、足立法または求心法あたりは大体コースを１分前後で探索が終わり、
拡張左手だと３分前後、で探索が終わります。（ちゃんとコースを走れるのが前提だけど…）
