［アルゴリズム］DFS/BFS

1710 ワード
DFS/BFS アルゴリズム#アルゴリズム# テキストリンク

Depth First Search(DFS):深度優先ナビゲーション


ツリーまたはグラフで、1つのパスから最後に進み、別のパスに戻るプロセスです.
1つのパスのナビゲーションが完了すると、前のプロシージャに戻り、別のパスに繰り返しナビゲートするため、スタックまたは再帰を使用して実装されます.
현 경로상의 노드만을 기억하면 되므로 저장 공간의 수요가 비교적 적지만, 한 경로가 무한히 깊을 경우 오버플로우가 발생할 수 있다. 이를 방지하기 위해 깊이에 제한을 두고 구현한다.

깊이 제한에 도달할 때까지 목표 노드가 발견되지 않으면 가장 최근의 부모 노드로 돌아가(Backtraking) 다른 경로를 선택해 진행한다.

또한 목표 노드에 도달하지 못할 가능성이 존재하며, 도달한다 해도 해당 경로가 최단 경로라는 보장이 없다.

모든 노드를 방문하고자 하는 경우에 이 방법을 선택한다.

깊이 우선 탐색(DFS)이 너비 우선 탐색(BFS)보다 좀 더 간단하다.

검색 속도 자체는 너비 우선 탐색(BFS)에 비해서 느리다.

Breadth First Search(BFS):まず幅をブラウズ


これは、ツリーまたはグラフのルートノードから探索を開始し、隣接するすべてのノードを探索する方法です.
通常は、ブラウズが必要なノードを格納し、1つずつブラウズして削除する方法でキューを使用して実現されます.
해가 존재한다면 무조건 찾을 수 있는 방법이지만
경로가 긴 경우 저장 공간의 수요가 매우 커지게 되며 해가 존재하지 않는 경우 모든 노드의 탐색을 마친 후에 실패로 끝나게 된다.

주로 두 노드 사이의 최단 경로를 찾고 싶을 때 BFS를 선택한다.

整理する


両方の方法で条件内のすべてのノードを検索し、時間の複雑さは同じです.
DFSおよびBFSは、次のノードがアクセスされたかどうかを決定する時間と、各ノードにアクセスする時間とを加算することができる.
DFS、BFSは、その特徴により、より使いやすい問題タイプがある.
主な問題は、
  • グラフィックのすべての頂点にアクセスすることです.
    すべての頂点にのみアクセスする重要な問題については、DFSとBFSの2つの方法のいずれかを使用することができます.
  • パスフィーチャーを格納する必要がある問題
    たとえば,各頂点に数字が書かれており,aからbへの経路を解く際に経路に同じ数字がないなどの問題があり,各経路に特徴を格納する必要がある場合はDFSを用いる.(BFSは経路の特徴を持たない.)
  • 最短距離の問題
    迷路など最短距離を探す必要がある場合はBFSが有利です.
    深度優先検索パスを使用すると、最初に発見された答えは最短距離ではない可能性があります.
    幅優先検索は、現在のノードに近い場所から検索を開始するので、パスを検索するときに最初に見つける答えは最短距離です.
    • それ以外は、
    検索するグラフィックが非常に大きい場合は、DFSを考慮してください.
    検索対象の規模が大きくなく、検索開始点から遠くない場合はBFSなどを使用できます.
    HTML 3. LIST
    Python 3のURL符号化復号