幅優先探索の実装例


本稿では最短経路の求め方|最も簡単な例の実装例を紹介する.

以下の迷路を考える.
ゴールは白四角部分とする.

[[ファイル:最短経路サンプル迷路.JPG]]

本記事では,以下のような仮定を満たすロボットを考える.

  • ロボットは隣接する区画にいつも同じ時間コストで到達する

この迷路・ロボットは,最短経路の求め方|最も簡単な例で紹介したグラフ構造としてモデル化できる.

この問題に対して幅優先探索法を実装し,最短経路を求める.

maze.datの内容は次のとおり.迷路の表現は座標系・迷路表現の定義#迷路表現の例で解説しているものを採用している.

実装その1は以下のとおり

実行結果は以下のとおり

あとは現在地点から見て壁がなく(この条件は重要),かつ,コストが最も低いほうへ移動すれば(ここでモデル化した範囲で)最短で目的地へ到達することができる.

実装その2:同じ幅優先サーチだが,リングリストを活用すると高速化をはかることができる.電通大マイクロマウスブログの記事と主張していることは同じである.

実行結果は実装その1と同じ.計算速度がはやい.経験上,迷路が16x16であっても,実装その1だと秒単位の計算時間がかかることがあるが,実装その2だと,人間が認識できない程度にははやくなる.