2: Pathfinding(経路探索) Breadth-First Search(幅優先探索) アルゴリズム p5.js – 解説

幅優先探索とは?

幅優先探索は、探索にツリー構造を用いるアルゴリズムで、スタート位置から近い順に探索することが特徴的です(参考:「幅優先探索」)。

スタート位置は下図の(1)です。これをツリーのルート(根)と言います。下図で示す円はそれぞれノードと言います。幅優先探索は、(1)からこれに隣接するノードを探索し((2),(3),(4))、そこからさらに隣接するノードを探索し((5),(6),(7),(8))、目的のノード(12)が見つかるまでこれを繰り返します。探索はこのように、ツリーの横向きに進むので幅優先と呼ばれます。

幅優先探索では、ノードを近い順に探索するので、データの出し入れをFIFOと呼ばれる方法で行います。FIFOとは「先入れ先出し」の意味で、先に並んだ人から先にお金がおろせる、ATMの待ち行列にたとえられます。

幅優先探索にはまた、次の特徴もあります。

  • 最悪の場合、全経路を探索する可能性があるので、時間がかかる場合がある
  • 見つかった経路を全部覚えておく必要がある(消費メモリの問題)
  • 正解が存在する場合は必ず解決できる(正解がない問題には対処できない)
アルゴリズム
  1. 開始のノードをキューに追加する
  2. キューにノードがあれば取り出す。なければ全ノードの探索は終わった
  3. 取り出したノードが目的のノードであれば探索終わり
  4. 取り出したノードに隣接するノードの中で、未探索のノードをキューに追加する
  5. (2)に戻り、以降を繰り返す
サンプルのグリッドの場合

1: Pathfinding(経路探索) Breadth-First Search(幅優先探索) アルゴリズム p5.js – 導入」のサンプルの場合、下図の黄色の正方形(0,0)が開始ノードで、赤い正方形(2,2)が目的のノードです。このサンプルでは、これらに加え、通過できない障害物のノード、黒い正方形(1,1)、(1,2)..があります。

隣接ノードを調べるときにはそのノードの上下左右を調べますが、実はそこはグリッドの範囲外かも知れません。実際開始ノードの上と左は範囲外です。したがって、隣接ノードがあると思っているそこがグリッドの範囲内かどうかを調べ、範囲内なら、それが目的のノードかどうかや、障害物かどうか、前に調べたものかどうかなどをチェックすることになります。

コメントを残す

メールアドレスが公開されることはありません。 * が付いている欄は必須項目です

CAPTCHA