迷路の探索まとめ

迷路の探索方法まとめ

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

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

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

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

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

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

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

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

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

http://www4.atwiki.jp/zero_one/pages/28.html
http://mmk.rulez.jp/technical/smart/adachi
http://blog.livedoor.jp/ctecun/archives/1041731.html

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

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

http://blog.livedoor.jp/k_yon/archives/50744669.html

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

1~5どれもパッとしないので
別の方法でいきたいところです.

未分類

Posted by tanitanin


PAGE TOP