DFS、BFS、BackTracking

深度優先ナビゲーション

:ツリー資料構造でよく使われる探索方法.
ルートノード(または他の任意のノード)では、まずサブノードを完全にナビゲートします.すなわち,広範な探索を行う前に,まず深い探索を行う.
単純探索速度自体は幅優先探索(BFS)よりも遅いが,この方法ですべてのノードにアクセスできる.
DFSは再帰的に実現できる.今回の復帰を通じて、昨日と今日はN-Queens問題を理解し、解答しました.
写真でもっと詳しく見てみましょう.

この図は、ルートノード1号が呼び出されたときです.この絵の右側にはスタックが表現されています.1番を呼ぶと、1番はスタックに積み上げられます.

次は子供を見ることです.2番の子供を見てから、2番が山のように積まれているのを見ることができます.

次はもちろん3番スタックです.しかし、3日にはもう子供がいません.これで3番スタックが消え、2番スタックが再確認されます.2番も巡回できる子がいないので、2番スタックも削除できます.その結果を下図に示します.


2番と3番の子供がいないので、1番のスタックしか残っていません.1番のもう一人の子供は4番で、4番のスタックが1番のスタックに積み上げられます.


その後、上記の手順を繰り返し、5番と6番がスタックに積み上げられます.

6番には子供がいないので、6番スタックは消え、5番スタックは巡回しますが、5番にも子供がいないので、5番スタックも消えます.だから5番の下の4番のスタックの中ですでに5番を巡視したので、他の子供の7番を巡視して、7番のスタックがあります.
このプロセス全体を繰り返すと、次の図で終わります.

幅優先ナビゲーション

:BFSメソッドはDFSと同じですが、隣接ノードへの順次アクセスを実現します.つまり、同じレベルのノードに先にアクセスします.この場合、スタックではなくキューを使用して実装できます.

BFSを使用してキューを実装します。

:実はこのコードは私が書いたものではありません.私たちのCodeStatesのKing God Mincheolはテンプレートのように使えばいいとコード説明を書いています.理解して暗記すればいい.

function bfs() {
  let Q = [
    [0, 0],
    [0, 1],
    [0, 2],
    [0, 3],
  ];
  function enQ(ele) {
    Q.push(ele)
  }
  function deQ() {
    let head = Q[0];
    Q = Q.slice(1);
    return head;
  }
  // 4 X 4
  while (Q.length > 0) {
    // [0, 0]
    let choice = deQ();
    // [0, 1], [0, 2], [0, 3],
    let row = choice[0];
    let col = choice[1];
    for (let col = 0; col < N; col++){
      if (map[row + 1][col]에 놓을 수 있냐?) {
        enQ([row + 1, col])
      }
    }
  }
}

詳細

BackTracking

: