迷路の探索まとめ

2014年8月4日

迷路の探索方法まとめ

１．左手法
いちばん一般的
左手を壁についてゴールまで向かう

利点：
コードが簡単，省メモリ
欠点：
ゴールへの道が2本あったときに，たどり着かないことがある．

２．拡張左手法
1の改良版．未探索のマスを優先して通るようにしたもの．

http://www.ftech-net.co.jp/robot/howto/micromouse03.html

利点：
コードが簡単，ゴールにちゃんとたどりつく，省メモリ
欠点：
探索時間がかかる

３．求心法
これも左手法と並んでよく迷路パズルで使われるもの．
中心からの距離を評価値としてA*探索するもの．

http://www.yitjc.ac.jp/info/yamasita/kichinose.html

利点：
コードが簡単，左手法より速くゴールに着ける
欠点：
最近の迷路だと対策されていて探索時間が長くなる傾向．
評価値の分のメモリ(?)・計算が増える

４．足立法
よく使われている．左手法よりはルールがちょっとむずかしい．
探索と最短を一気に求められる？（ホントか不明）

利点：
比較的単純でコードが書きやすい．
欠点：
最短経路を求めながら進むので計算が増える

５．ベクトルマップ法
過去の迷路を参考に，マスに対して向かうと良い方向をあらかじめ持っておく．

利点：
マップさえあれば計算は少ない．求心法対策などを回避しやすい．
欠点：
ベクトルマップの作成をどうすればいいか（テキトーだと求心や左手と変わらないような）

１～５どれもパッとしないので
別の方法でいきたいところです．

まだ、コメントがありません