Rozumiem różnice między DFS i BFS, ale chcę wiedzieć, kiedy bardziej praktyczne jest używanie jednego nad drugim?

Czy ktokolwiek mógłby podać jakieś przykłady tego, jak DFS przebije BFS i odwrotnie?

Zależy to w dużej mierze od struktury drzewa wyszukiwania oraz liczby i lokalizacji rozwiązań (czyli szukanych pozycji).

• Jeśli wiesz, że rozwiązanie nie jest daleko od katalogu głównego drzewa, lepsze może być pierwsze wyszukiwanie szerokości (BFS).

• Jeśli drzewo jest bardzo głębokie, a rozwiązania są rzadkie, pierwsze wyszukiwanie głębokości (DFS) może zająć bardzo dużo czasu, ale BFS może być szybszy.

• Jeśli drzewo jest bardzo szerokie, BFS może wymagać zbyt dużo pamięci, więc może być całkowicie niepraktyczne.

• Jeśli rozwiązania są częste, ale znajdują się głęboko w drzewie, BFS może być niepraktyczne.

• Jeśli drzewo wyszukiwania jest bardzo głębokie, i tak musisz ograniczyć głębokość wyszukiwania dla pierwszego wyszukiwania głębokości (DFS) (na przykład z iteracyjnym pogłębianiem).

Ale to tylko podstawowe zasady; prawdopodobnie będziesz musiał eksperymentować.

Wyszukiwanie w pierwszej kolejności

Wyszukiwanie wgłębne jest często stosowane w symulacjach gier (i podobnych do rzeczywistych sytuacjach w świecie rzeczywistym). W typowej grze możesz wybrać jedną z kilku możliwych akcji. Każdy wybór prowadzi do dalszych wyborów, z których każdy prowadzi do dalszych wyborów, i tak dalej, do ciągle powiększającego się wykresu możliwości w kształcie drzewa.

Na przykład w grach takich jak szachy, kółko i krzyżyk, kiedy decydujesz, jaki ruch wykonać, możesz mentalnie wyobrazić sobie ruch, następnie możliwe reakcje przeciwnika, a następnie twoje odpowiedzi i tak dalej. Możesz zdecydować, co robić, sprawdzając, który ruch prowadzi do najlepszego wyniku.

Tylko niektóre ścieżki w drzewie gry prowadzą do twojej wygranej. Niektóre prowadzą do zwycięstwa przeciwnika, kiedy osiągniesz takie zakończenie, musisz cofnąć się lub wrócić do poprzedniego węzła i spróbować innej ścieżki. W ten sposób eksplorujesz drzewo, aż znajdziesz ścieżkę z pomyślnym zakończeniem. Następnie wykonujesz pierwszy ruch tą ścieżką.

Pierwsze wyszukiwanie szerokości

Przeszukiwanie pierwszego szerokości ma interesującą właściwość: najpierw znajduje wszystkie wierzchołki znajdujące się o jedną krawędź od punktu początkowego, a następnie wszystkie wierzchołki znajdujące się o dwie krawędzie itd. Jest to przydatne, jeśli próbujesz znaleźć najkrótszą ścieżkę od wierzchołka początkowego do danego wierzchołka. Zaczynasz BFS, a kiedy znajdziesz określony wierzchołek, wiesz, że ścieżka, którą do tej pory namierzałeś, jest najkrótszą ścieżką do węzła. Gdyby istniała krótsza ścieżka, BFS już by ją znalazł.

Przeszukiwanie pierwszego zakresu może być wykorzystywane do znajdowania sąsiednich węzłów w sieciach peer-to-peer, takich jak BitTorrent, systemów GPS do znajdowania pobliskich lokalizacji, witryn sieci społecznościowych do znajdowania osób w określonej odległości i tym podobnych.

Niezłe wyjaśnienie z http://www.programmerinterview.com/index.php/data-structures/dfs-vs-bfs/

Przykład BFS

Oto przykład, jak wyglądałby BFS. Jest to coś w rodzaju przemierzania drzewa zlecenia poziomu, w którym użyjemy KOLEJKI z podejściem ITERATYWNYM (przeważnie RECURSION kończy się na DFS). Liczby reprezentują kolejność dostępu do węzłów w systemie BFS:

W głębokim pierwszym wyszukiwaniu zaczynasz od korzenia i podążasz za jedną z gałęzi drzewa tak daleko, jak to możliwe, dopóki nie znajdziesz poszukiwanego węzła lub trafisz na węzeł liścia (węzeł bez dzieci). Jeśli uderzysz w węzeł liścia, kontynuujesz wyszukiwanie u najbliższego przodka z niezbadanymi dziećmi.

Przykład DFS

Oto przykład, jak wyglądałby DFS. Myślę, że przejście po zamówieniu w drzewie binarnym rozpocznie pracę od poziomu Liścia. Liczby reprezentują kolejność dostępu do węzłów w systemie plików DFS:

Różnice między DFS i BFS

Porównując BFS i DFS, dużą zaletą DFS jest to, że ma on znacznie mniejsze wymagania pamięciowe niż BFS, ponieważ nie jest konieczne przechowywanie wszystkich wskaźników potomnych na każdym poziomie. W zależności od danych i tego, czego szukasz, korzystny może być DFS lub BFS.

Na przykład, biorąc pod uwagę drzewo genealogiczne, jeśli ktoś szukałby kogoś na drzewie, który jeszcze żyje, można bezpiecznie założyć, że ta osoba będzie na dnie drzewa. Oznacza to, że BFS zajęłoby bardzo dużo czasu, aby osiągnąć ten ostatni poziom. Jednak DFS szybciej znalazłby cel. Ale gdyby ktoś szukał członka rodziny, który zmarł bardzo dawno temu, byłby bliżej szczytu drzewa. Wtedy BFS byłby zwykle szybszy niż DFS. Tak więc zalety obu różnią się w zależności od danych i tego, czego szukasz.

Jeszcze jednym przykładem jest Facebook; Sugestia dotycząca znajomych przyjaciół. Potrzebujemy natychmiastowych przyjaciół, którzy zasugerują, gdzie możemy użyć BFS. Może być znalezienie najkrótszej ścieżki lub wykrycie cyklu (za pomocą rekurencji) możemy użyć DFS.

Szerokość Pierwsze wyszukiwanie jest zasadniczo najlepszym podejściem, gdy głębokość drzewa może się różnić, i wystarczy przeszukać część drzewa, aby znaleźć rozwiązanie. Na przykład znalezienie najkrótszej ścieżki od wartości początkowej do wartości końcowej jest dobrym miejscem do korzystania z BFS.

Głębokie pierwsze wyszukiwanie jest powszechnie używane, gdy trzeba przeszukać całe drzewo. Łatwiej jest zaimplementować (przy użyciu rekurencji) niż BFS i wymaga mniejszego stanu: Podczas gdy BFS wymaga przechowywania całej „granicy”, DFS wymaga jedynie przechowywania listy węzłów nadrzędnych bieżącego elementu.

DFS zajmuje więcej miejsca niż BFS, ale może sięgać niepotrzebnych głębi.

Ich nazwy ujawniają: jeśli istnieje duży zasięg (tj. Duży czynnik rozgałęziający), ale bardzo ograniczona głębokość (np. Ograniczona liczba „ruchów”), wówczas DFS może być bardziej preferowany niż BFS.

Na IDDFS

Należy wspomnieć, że istnieje mniej znany wariant, który łączy efektywność przestrzenną DFS, ale (w ujęciu kumulatywnym) odwiedzanie BFS w rzędach poziomów jest iteracyjnym pogłębiającym wyszukiwaniem w pierwszej kolejności . Algorytm ten weryfikuje niektóre węzły, ale wnosi jedynie stały współczynnik asymptotycznej różnicy.

Kiedy podchodzisz do tego pytania jako programista, wyróżnia się jeden czynnik: jeśli używasz rekurencji, wyszukiwanie w pierwszej kolejności jest łatwiejsze do wdrożenia, ponieważ nie musisz utrzymywać dodatkowej struktury danych zawierającej węzły do ​​zbadania.

Oto pierwsze wyszukiwanie dogłębnego wykresu niezorientowanego, jeśli przechowujesz informacje o „już odwiedzonych” w węzłach:

def dfs(origin):                               # DFS from origin:
    origin.visited = True                      # Mark the origin as visited
    for neighbor in origin.neighbors:          # Loop over the neighbors
        if not neighbor.visited: dfs(next)     # Visit each neighbor if not already visited

Jeśli przechowujesz informacje „już odwiedzone” w oddzielnej strukturze danych:

def dfs(node, visited):                        # DFS from origin, with already-visited set:
    visited.add(node)                          # Mark the origin as visited
    for neighbor in node.neighbors:            # Loop over the neighbors
        if not neighbor in visited:            # If the neighbor hasn't been visited yet,
            dfs(node, visited)                 # then visit the neighbor
dfs(origin, set())

Porównaj to z szerokim wyszukiwaniem, w którym musisz zachować osobną strukturę danych dla listy węzłów, które jeszcze nie odwiedzasz, bez względu na wszystko.

Jedną ważną zaletą BFS byłoby to, że można go użyć do znalezienia najkrótszej ścieżki między dowolnymi dwoma węzłami na nieważonym wykresie. Podczas gdy nie możemy używać DFS do tego samego .

W przypadku BFS możemy rozważyć przykład na Facebooku. Otrzymujemy propozycję dodania znajomych z profilu FB z profilu innych znajomych. Załóżmy, że A-> B, podczas gdy B-> E i B-> F, więc A otrzyma sugestię dla E i F. Muszą używać BFS do odczytu do drugiego poziomu. DFS jest bardziej oparty na scenariuszach, w których chcemy prognozować coś na podstawie danych, które mamy od źródła do miejsca docelowego. Jak już wspomniano o szachach lub sudoku. Kiedy już coś mi się różni, uważam, że DFS powinien być użyty do najkrótszej ścieżki, ponieważ DFS najpierw obejmie całą ścieżkę, a następnie możemy wybrać najlepszą. Ale ponieważ BFS zastosuje podejście chciwości, może to wyglądać na najkrótszą ścieżkę, ale końcowy wynik może się różnić. Daj mi znać, czy moje rozumienie jest błędne.

Niektóre algorytmy zależą od określonych właściwości DFS (lub BFS) do działania. Na przykład algorytm Hopcroft i Tarjan do znajdowania 2 połączonych komponentów wykorzystuje fakt, że każdy już odwiedzony węzeł napotkany przez DFS znajduje się na ścieżce od korzenia do aktualnie badanego węzła.

Poniżej znajduje się wyczerpująca odpowiedź na to, o co pytasz.

W prostych słowach:

Algorytm szerokości pierwszego wyszukiwania (BFS), od nazwy „szerokość”, odkrywa wszystkich sąsiadów węzła przez zewnętrzne krawędzie węzła, a następnie odkrywa niewidzianych sąsiadów wcześniej wymienionych sąsiadów przez ich zewnętrzne krawędzie i tak dalej, aż wszyscy odwiedzane są węzły osiągalne ze źródła źródłowego (możemy kontynuować i wziąć inne źródło źródłowe, jeśli pozostaną nie odwiedzone węzły i tak dalej). Dlatego można go użyć do znalezienia najkrótszej ścieżki (jeśli istnieje) od węzła (źródła źródłowego) do innego węzła, jeśli masy krawędzi są jednolite.

Algorytm głębokiego pierwszego wyszukiwania (DFS), od nazwy „Głębokość”, odkrywa niewidzianych sąsiadów ostatnio odkrytego węzła x przez jego zewnętrzne krawędzie. Jeśli nie ma niewidzianego sąsiada z węzła x, algorytm cofa się, aby odkryć niewidzianych sąsiadów węzła (poprzez jego zewnętrzne krawędzie), z których odkryto węzeł x, i tak dalej, aż odwiedzone zostaną wszystkie węzły osiągalne ze źródła źródłowego (możemy kontynuować i pobrać inne źródło źródłowe, jeśli pozostaną nie odwiedzone węzły itp.).

Zarówno BFS, jak i DFS mogą być niekompletne. Na przykład, jeśli czynnik rozgałęzienia węzła jest nieskończony lub bardzo duży, aby obsłużyć zasoby (pamięć) (np. Podczas przechowywania węzłów, które mają zostać odkryte w następnej kolejności), BFS nie jest kompletny, nawet jeśli szukany klucz może znajdować się na odległość kilku krawędzi od pierwotnego źródła. Ten nieskończony czynnik rozgałęziający może wynikać z nieskończonych wyborów (sąsiednich węzłów) z danego węzła do wykrycia. Jeśli głębokość jest nieskończona lub bardzo duża dla zasobów (pamięci) do obsługi (np. Przy przechowywaniu węzłów, które mają zostać odkryte w następnej kolejności), DFS nie jest kompletny, nawet jeśli szukany klucz może być trzecim sąsiadem pierwotnego źródła. Ta nieskończona głębokość może wynikać z sytuacji, w której algorytm odkrywa dla każdego węzła przynajmniej nowy wybór (węzeł sąsiedni), którego wcześniej nie odwiedzono.

Dlatego możemy stwierdzić, kiedy użyć BFS i DFS. Załóżmy, że mamy do czynienia z możliwym do zarządzania ograniczonym czynnikiem rozgałęzienia i możliwą do zarządzania ograniczoną głębokością. Jeśli szukany węzeł jest płytki, tzn. Osiągalny po niektórych krawędziach ze źródła źródłowego, lepiej użyć BFS. Z drugiej strony, jeśli szukany węzeł jest głęboki, tj. Osiągalny po wielu krawędziach ze źródła źródłowego, lepiej jest użyć DFS.

Na przykład w sieci społecznościowej, jeśli chcemy szukać osób o podobnych zainteresowaniach konkretnej osoby, możemy zastosować BFS od tej osoby jako źródła źródłowego, ponieważ w większości osoby te będą jego bezpośrednimi przyjaciółmi lub przyjaciółmi znajomych, tj. lub dwie krawędzie daleko. Z drugiej strony, jeśli chcemy szukać osób, które mają zupełnie inne zainteresowania konkretnej osoby, możemy zastosować DFS od tej osoby jako źródła źródłowego, ponieważ głównie ci ludzie będą bardzo daleko od niego, tj. Przyjaciel przyjaciela przyjaciela .... tj. za dużo krawędzi.

Aplikacje BFS i DFS mogą się różnić również ze względu na mechanizm wyszukiwania w każdym z nich. Na przykład możemy użyć BFS (zakładając, że współczynnik rozgałęzienia jest zarządzalny) lub DFS (zakładając, że głębokość jest zarządzalna), gdy chcemy po prostu sprawdzić osiągalność z jednego węzła do drugiego bez informacji, gdzie ten węzeł może być. Oba mogą również rozwiązać te same zadania, jak topologiczne sortowanie wykresu (jeśli tak jest). BFS można wykorzystać do znalezienia najkrótszej ścieżki z krawędziami masy jednostkowej od węzła (źródła pierwotnego) do drugiego. Podczas gdy DFS może być wykorzystany do wyczerpania wszystkich wyborów ze względu na jego charakter zagłębiania się, jak odkrywanie najdłuższej ścieżki między dwoma węzłami na acyklicznym grafie. Również DFS może być wykorzystywany do wykrywania cyklu na wykresie.

Na koniec, jeśli mamy nieskończoną głębokość i nieskończony współczynnik rozgałęziania, możemy użyć Iteracyjnego pogłębiania wyszukiwania (IDS).

Według właściwości DFS i BFS. Na przykład, gdy chcemy znaleźć najkrótszą ścieżkę. zwykle używamy bfs, może to zagwarantować „najkrótszy”. ale tylko dfs może zagwarantować, że możemy pochodzić z tego punktu, może osiągnąć ten punkt, nie może zagwarantować „najkrótszego”.

Myślę, że to zależy od problemów, z którymi się borykasz.

1. najkrótsza ścieżka na prostym wykresie -> bfs
2. wszystkie możliwe wyniki -> dfs
3. szukaj na wykresie (traktuj drzewo, martix jak również wykres) -> dfs ....

Ponieważ przeszukiwania w pierwszej kolejności używają stosu podczas przetwarzania węzłów, system DFS zapewnia powrót do poprzedniego stanu. Ponieważ przeszukiwania szerokość-pierwsza używają kolejki, a nie stosu, do śledzenia przetwarzanych węzłów, BFS nie zapewnia śledzenia wstecznego.

Gdy szerokość drzewa jest bardzo duża, a głębokość jest niska, użyj DFS, ponieważ stos rekurencyjny nie przepełni się. Użyj BFS, gdy szerokość jest niska i głębokość jest bardzo duża, aby przejść przez drzewo.

Jest to dobry przykład do wykazania, że ​​BFS jest lepszy niż DFS w niektórych przypadkach. https://leetcode.com/problems/01-matrix/

Po prawidłowym wdrożeniu oba rozwiązania powinny odwiedzić komórki, które mają większą odległość niż obecna komórka +1. Ale DFS jest nieefektywny i wielokrotnie odwiedzał tę samą komórkę, co powoduje złożoność O (n * n).

Na przykład,

1,1,1,1,1,1,1,1, 
1,1,1,1,1,1,1,1, 
1,1,1,1,1,1,1,1, 
0,0,0,0,0,0,0,0,

Zależy to od sytuacji, w której jest używany. Ilekroć mamy problem z przechodzeniem przez wykres, robimy to w jakimś celu. Gdy pojawia się problem ze znalezieniem najkrótszej ścieżki na nieważonym wykresie lub znalezieniem wykresu dwustronnego, możemy użyć BFS. W przypadku problemów związanych z wykrywaniem cyklu lub logiką wymagającą powrotu, możemy użyć DFS.