深度優先ナビゲーション

3620 ワード
TIL DFS アルゴリズム#アルゴリズム# テキストリンク


DFS


ルートノード(または他の任意のノード)から開始し、次のブランチ(ブランチ)の前にブランチを完全にナビゲートして移行する方法.
広く探求する前に,まず深く探求する.
このメソッドは、すべてのノードにアクセスする場合に使用します.DFSはBFSより簡単です.
単純探索速度自体はBFSより遅い.
スタックまたは再帰関数で実現でき、再帰関数は容易に実現できるため、ほとんどが再帰関数で実現される.
  • を実装する際に注意すべき事項:グラフィックナビゲーションでは、ノードにアクセスしたかどうかを確認する必要があります.
  • をチェックしないと無限ループに陥る危険があります.

    • DFSアルゴリズムの実現方式


  • aノードへのアクセス(開始ノード)
  • アクセスしたノードがアクセスしたことを確認します!
  • aに隣接するノードを順番に巡回する
  • aに隣接するノードがない場合、
    • を終了する.
  • aおよび隣接ノードbにアクセスした場合、aに隣接する他のノードにアクセスする前に、bのすべての隣接ノードにアクセスする必要がある.
  • bを起点としてDFSを再起動し、bの隣接ノードにアクセスする.
  • bのすべてのブランチを完璧に探索すれば、aに近い頂点の中でまだアクセスしていない頂点を探す.
  • 、すなわち、bのブランチを全面的に探索した後にのみ、aの他の隣接ノードにアクセスすることができる.
  • まだ頂点にアクセスしていない場合は、
    • を終了します.
  • があれば、再びその頂点を起点にDFSでスタート!
    • void search(Node root) {
  if (root == null) return;

  // 1. root 노드 방문
  visit(root);
  root.visited = true; // 1-1. 방문한 노드를 표시

  // 2. root 노드와 인접한 정점을 모두 방문
  for each (Node n in root.adjacent) {
    if (n.visited == false) { // 4. 방문하지 않은 정점을 찾는다.
      search(n); // 3. root 노드와 인접한 정점 정점을 시작 정점으로 DFS를 시작
    }
  }
}

    DFSのメリット

  • 現在のパス上のノードを記憶するだけで、記憶領域の需要は相対的に少ない
    • である.
  • ターゲットノードが深い段階にある場合、海
    • を迅速に得ることができる.
  • は、幅優先ナビゲーション(BFS)よりも簡単な
    • を実施する.

    DFSの欠点

  • 単純探索速度は幅優先探索(BFS)より
    • 遅い.
  • 年がなければ苦境に陥る可能性があります
    (任意の深さを予め指定してからナビゲートし、ターゲットノードが見つからない場合は以下のパスにナビゲートする)
    • .
  • 深さ優先探索は解法時に終了し、解法が最短経路であることは保証されない
    (ターゲットに到達するパスが複数ある場合、解は最適ではない可能性がある)

    • DFSの時間的複雑さ

  • DFSクエリーグラフィック(頂点数:N、幹線数:E)のすべての幹線.
  • 隣接表:O(N+E)
  • の隣接行列で表されるパターン:O(N^2)
    • Jetson TX 1およびTX 2手動ブラシ/バックアップ/ミラー・リカバリ
    TIL 48:論理回帰