knagai幅優先探索とは?幅優先探索は、探索にツリー構造を用いるアルゴリズムで、スタート位置から近い順に探索することが特徴的です(参考:「幅優先探索」)。スタート位置は下図の(1)です。これをツリーのルート(根)と言います。下図で示す円はそれぞれノードと言います。幅優先探索は、(1)からこれに隣接するノードを探索し((2),(3),(4))、そこからさらに隣接するノードを探索し((5),(6),(7),(8))、目的のノード(12)が見つかるまでこれを繰り返します。探索はこのように、ツリーの横向きに進むので幅優先と呼ばれます。幅優先探索では、ノードを近い順に探索するので、データの出し入れをFIFOと呼ばれる方法で行います。FIFOとは「先入れ先出し」の意味で、先に並んだ人から先にお金がおろせる、ATMの待ち行列にたとえられます。幅優先探索にはまた、次の特徴もあります。最悪の場合、全経路を探索する可能性があるので、時間がかかる場合がある見つかった経路を全部覚えておく必要がある(消費メモリの問題)正解が存在する場合は必ず解決できる(正解がない問題には対処できない)アルゴリズム開始のノードをキューに追加するキューにノードがあれば取り出す。導入」のサンプルの場合、下図の黄色の正方形(0,0)が開始ノードで、赤い正方形(2,2)が目的のノードです。このサンプルでは、これらに加え、通過できない障害物のノード、黒い正方形(1,1)、(1,2)..があります。隣接ノードを調べるときにはそのノードの上下左右を調べますが、実はそこはグリッドの範囲外かも知れません。実際開始ノードの上と左は範囲外です。したがって、隣接ノードがあると思っているそこがグリッドの範囲内かどうかを調べ、範囲内なら、それが目的のノードかどうかや、障害物かどうか、前に調べたものかどうかなどをチェックすることになります。コメントをキャンセルメールアドレスが公開されることはありません。*サイト上に表示された文字を入力してください。WAAPIに関する注意WAAPIを利用するにはブラウザに特別な設定が必要です。ブラウザの実験的な機能を有効化する方法に書いているので、必ずお読みください。楕円(円)、円弧を描く。APIやTensorFlow.jsについて調べたことを書いています。freebiescafe.com。