Różnica między BF i DFS

BFS vs DFS

Pierwsze wyszukiwanie szerokości (znane również jako BFS) to metoda wyszukiwania stosowana do poszerzenia wszystkich węzłów określonego wykresu. Wykonuje to zadanie, przeszukując każde rozwiązanie w celu zbadania i rozszerzenia tych węzłów (lub kombinacji sekwencji). Jako taki, BFS nie używa algorytmu heurystycznego (ani algorytmu, który wyszukuje rozwiązanie przez wiele scenariuszy). Po uzyskaniu wszystkich węzłów są one dodawane do kolejki znanej jako pierwsza, pierwsza kolejka. Te węzły, które nie zostały zbadane, są „przechowywane” w pojemniku oznaczonym „otwarte”; Po zbadaniu zostaną przetransportowane do pojemnika oznaczonego „zamkniętym”.

Pierwsze wyszukiwanie głębokości (znane również jako DFS) to metoda wyszukiwania, która zagłębia się w węzeł dziecięcy wyszukiwania, dopóki cel nie zostanie osiągnięty (lub do momentu, gdy będzie węzeł bez żadnych innych permutacji lub „dzieci”). Po znalezieniu jednego celu wyszukiwanie wynika z poprzedniego węzła, który poszedł z rozwiązaniem, powtarzając proces, dopóki wszystkie węzły nie zostaną pomyślnie przeszukane. W związku z tym węzły są odkładane na bok w celu dalszej eksploracji - nazywa się to rekursywnymi wdrożeniem.

Cechy BFS to złożoność przestrzeni i czasu, kompletność, dowód kompletności i optymalność. Złożoność przestrzeni odnosi się do odsetka liczby węzłów na najgłębszym poziomie wyszukiwania. Złożoność czasu odnosi się do faktycznej ilości „czasu” używanego do rozważenia każdej ścieżki, którą węzeł podejmie w poszukiwaniu. Kompletność jest zasadniczo wyszukiwaniem, które znajduje rozwiązanie na wykresie, niezależnie od tego, jaki to jest wykres. Dowodem kompletności jest najtrudniejszy poziom, na którym cel znajduje się w węźle na określonej głębokości. Wreszcie optymalność odnosi się do BFS, który nie jest ważony - to wykres wykorzystywany do kosztu jednostkowego.

DFS jest najbardziej naturalnym wyjściem przy użyciu drzewa spinka - które jest drzewem złożonym ze wszystkich wierzchołków i niektórych krawędzi na niekierowanym wykresie. W tej formacji wykres jest podzielony na trzy klasy: krawędzie do przodu, wskazujące z węzła do węzła dziecięcego; tylne krawędzie, wskazujące z węzła do wcześniejszego węzła; i krzyżowe krawędzie, które nie robią żadnego z nich.

Streszczenie:

1. BFS przeszukuje każde rozwiązanie na wykresie, aby rozszerzyć węzły; DFS Burrows głęboko w węźle dziecięce, aż do osiągnięcia celu.

2. Cechy BFS to złożoność przestrzeni i czasu, kompletność, dowód kompletności i optymalność; Najbardziej naturalnym wyjściem dla DFS jest drzewo spinka z trzema klasami: krawędzie do przodu, tylne krawędzie i krawędzie krzyżowe.