DFS vs BFS

DFSとBFSはデータ構造時にグラフィックとツリーを比較して整理したことがある.
詳細はDFSとBFSを参照してください.
しかし、定義と比較図を簡単に理解してから行きましょう.

DFSの定義(深度優先ナビゲーション)

ルートノード(または他の任意のノード)から始まり,次のブランチ(ブランチ)の前にそのブランチを全面的に探索し,広範な探索を行う前に深い探索を行う.

BFSの定義(幅優先ナビゲーション)

ルートノード(または他の任意のノード)から、まず隣接ノードをブラウズする方法であり、深くブラウズする前にブラウズする(wide).

DFSとBFSの原理比較

追跡(遡及)とは?

希望がなければ,除外して親ノードに戻り,解法時間を短縮することができる.

Backtrackingの原理とその概略図

深さ優先探索法を実行する.

ノードの潜在力を確認します.

ノードに希望がなければ枝を排除する.

種の稚気をそのノードの親ノードに戻した後,他の子ノードを探索して解法時間を短縮した.

Backstracking用語のクリーンアップ

希望がある:答えになる可能性がある.
枝切り:希望のないノードに行く必要がなく、次のノードを検索します(答えではありません).

BackTrackingコードの例

勤務時間の授業のコードを少し変えて、例を挙げます.

let code = ['A', 'B', 'C'];
// find all permutations

// but what if u want to find where B cant sit in the middle seat?
// backtrack

let result1 = [];
function permutation(usedArray, unusedArray) {
  if (usedArray.length === 3) {
    return result1.push(usedArray);
  }

  for (let i = 0; i < unusedArray.length; i++) {
    permutation(
      usedArray.concat(unusedArray[i]),
      unusedArray.filter((el, idx) => i !== idx)
    );
  }
}

permutation([], code);
console.log(result1);

let result2 = [];
function backtrackingPermutation(usedArray, unusedArray) {
  if (usedArray[1] === 'A' || usedArray[1] === 'B') {
    return;
  }

  if (usedArray.length === 3) {
    return result2.push(usedArray);
  }

  for (let i = 0; i < unusedArray.length; i++) {
    backtrackingPermutation(
      usedArray.concat(unusedArray[i]),
      unusedArray.filter((el, idx) => i !== idx)
    );
  }
}

backtrackingPermutation([], code);
console.log(result2);