Kiedy jest to praktyczne, aby używać głębokość-pierwsze wyszukiwanie (DFS) vs Szerokość-pierwsze wyszukiwanie (BFS)?

Ładne 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 trawersu drzewa kolejności poziomów, gdzie będziemy używać QUEUE z podejściem iteracyjnym (głównie rekurencja zakończy się DFS). Liczby reprezentują kolejność, w jakiej węzły są dostępne w BFS:

W głębszym pierwszym poszukiwaniu, zaczynasz od korzenia i podążaj za jedną z gałęzi drzewa tak daleko, jak to możliwe, aż albo węzeł, którego szukasz, zostanie znaleziony, albo trafisz w węzeł liściowy (węzeł bez dzieci). Jeśli trafisz w węzeł liścia, kontynuujesz poszukiwania najbliższego przodka z niezbadanymi dziećmi.

Przykład DFS

Oto przykład jak wyglądałby DFS. Myślę, że post order traversal w binary tree rozpocznie pracę od poziomu liścia. Liczby reprezentują kolejność w którym węzły są dostępne w DFS:

Różnice między DFS i BFS

Porównując BFS i DFS, dużą zaletą DFS jest to, że ma znacznie niższe wymagania pamięci 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, DFS lub BFS mogą być korzystne.

Na przykład, jeśli ktoś szuka na drzewie kogoś, kto nadal żyje, więc można 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. DFS, jednak znajdzie cel szybciej. Ale gdyby ktoś szukał członka rodziny, który zmarł bardzo dawno temu, to ta osoba byłaby bliżej wierzchołka drzewa. Następnie 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 jeden przykładem jest Facebook; Sugestia na znajomych znajomych. Potrzebujemy natychmiastowych przyjaciół do sugestii, 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.

Depth - pierwsze wyszukiwanie

Na przykład w grach takich jak szachy, tic-tac-toe kiedy decydujesz, jaki ruch wykonać, możesz mentalnie wyobraź sobie ruch, potem możliwe odpowiedzi przeciwnika, potem twoje odpowiedzi i tak dalej. Możesz zdecydować, co zrobić, widzą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, gdy osiągniesz takie zakończenie, musisz wykonać kopię zapasową lub cofnąć się do poprzedniego węzła i spróbować innej ścieżki. W ten sposób odkrywasz drzewo, aż znajdziesz ścieżkę z pomyślnym zakończeniem. Następnie wykonaj pierwszy ruch wzdłuż tego / align = "left" /

Szerokość-pierwsze wyszukiwanie

Szerokość-pierwsze wyszukiwanie ma interesującą właściwość: najpierw znajduje wszystkie wierzchołki, które są o jedną krawędź od punktu początkowego, potem wszystkie wierzchołki, które są o dwie krawędzie dalej, i tak dalej. Jest to przydatne, jeśli próbujesz znaleźć najkrótszą ścieżkę od początkowego wierzchołka do danego wierzchołka. Uruchamiasz BFS, a kiedy znajdziesz określony wierzchołek, wiesz, że ścieżka, którą do tej pory wyśledziłeś, jest najkrótszą ścieżką do węzła. Gdyby było krótsza ścieżka, BFS już by ją znalazł.

Szerokość-pierwsze wyszukiwanie może być używane do wyszukiwania węzłów sąsiadujących w sieciach peer to peer, takich jak BitTorrent, systemy GPS, aby znaleźć pobliskie lokalizacje, serwisy społecznościowe, aby znaleźć ludzi w określonej odległości i tym podobne.

Szerokość pierwsze wyszukiwanie jest zazwyczaj najlepszym podejściem, gdy głębokość drzewa może się różnić, a wystarczy przeszukać tylko część drzewa w celu znalezienia rozwiązania. Na przykład znalezienie najkrótszej ścieżki od wartości początkowej do wartości końcowej jest dobrym miejscem do użycia BFS.

Głębia pierwsze wyszukiwanie jest powszechnie używane, gdy trzeba przeszukać całe drzewo. Jest to łatwiejsze do zaimplementowania (używając rekurencji) niż BFS i wymaga mniej stanu: podczas gdy BFS wymaga przechowywania całej "granicy", DFS wymaga tylko przechowujesz listę węzłów nadrzędnych bieżącego elementu.

DFS jest bardziej przestrzenny niż BFS, ale może przejść do niepotrzebnych głębokości.

Ich nazwy są odkrywcze: jeśli istnieje duża szerokość (tj. duży współczynnik rozgałęzienia), ale bardzo ograniczona głębokość (np. ograniczona liczba "ruchów"), to DFS może być bardziej preferowany od BFS.

Na IDDFS

Należy wspomnieć, że istnieje mniej znany wariant, który łączy w sobie wydajność przestrzeni DFS, ale (kumulacyjnie) odwiedziny rzędu poziomów BFS, to iteracyjne pogłębienie głębokość - pierwsze wyszukiwanie . Algorytm ten sprawdza niektóre węzły, ale wnosi tylko stały czynnik asymptotycznej różnicy.

Ważną zaletą BFS byłoby to, że może być używany do znalezienia najkrótszej ścieżki między dowolnymi dwoma węzłami w nieważonym wykresie. Natomiast nie możemy używać DFS dla tego samego .

Kiedy podchodzisz do tego pytania jako programista, wyróżnia się jeden czynnik: jeśli używasz rekurencji, to wyszukiwanie na początku głębi jest prostsze do zaimplementowania, ponieważ nie musisz utrzymywać dodatkowej struktury danych zawierającej węzły, które jeszcze nie zostały zbadane.

Najpierw poszukaj nie zorientowanego wykresu, jeśli przechowujesz informacje "już odwiedzone" 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

W przypadku przechowywania informacji" już odwiedzonych " w osobnych danych struktura:

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 wyszukiwaniem szerokościowym, w którym musisz zachować oddzielną strukturę danych dla listy węzłów, które jeszcze nie odwiedziły, bez względu na wszystko.

Dla BFS, możemy rozważyć przykład Facebook. Otrzymujemy propozycję dodania znajomych z profilu na 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 opiera się bardziej 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. Raz mam inny tutaj jest, uważam, że DFS powinny być używane do najkrótsza ścieżka, ponieważ DFS najpierw pokryje całą ścieżkę, wtedy możemy wybrać najlepszą. Ale jak BFS będzie używać podejście chciwy więc może być to wygląda na jego najkrótszą ścieżkę, ale wynik końcowy może się różnić. Daj mi znać, czy moje rozumienie jest złe.

Niektóre algorytmy zależą od konkretnych właściwości DFS (lub BFS) do działania. Na przykład algorytm Hopcrofta i Tarjana 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.

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

Ponieważ wyszukiwanie w pierwszej głębi używa stosu podczas przetwarzania węzłów, backtracking jest dostarczany z DFS. Ponieważ wyszukiwanie w pierwszej kolejności używa kolejki, a nie stosu, aby śledzić, które węzły są przetwarzane, funkcja backtracking nie jest dostarczana z systemem BFS.

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, a głębokość jest bardzo duża do trawersowania drzewa.

Jest to dobry przykład, aby wykazać, że BFS jest lepszy niż DFS w pewnym przypadku. 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 O(n*n) złożoności.

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,

To zależy od sytuacji, w której jest używany. Ilekroć mamy problem z przejściem wykresu, robimy to w jakimś celu. Gdy pojawia się problem ze znalezieniem najkrótszej ścieżki w grafie nieważonym lub znalezieniem, czy Graf jest dwudzielny, możemy użyć BFS. W przypadku problemów z wykrywaniem cyklu lub dowolnej logiki wymagającej cofania, możemy użyć DFS.

To pytanie jest nieco stare, ale świetnym przykładem jest współczesna gra wideo "Bit Heroes". W typowym lochu z bossem twoim celem jest pokonanie bossa, po czym masz możliwość opuszczenia danego lochu lub kontynuowania eksploracji go w celu zdobycia łupów. Ale ogólnie rzecz biorąc, bossowie są daleko od Twojego punktu odrodzenia. Gra oferuje funkcję automatycznego przechodzenia przez lochy, która w zasadzie przenosi twoją postać przez lochy, napotykając wrogów. Jest to realizowane za pomocą Głębia-pierwszy algorytm wyszukiwania, ponieważ celem jest jak najgłębsze wejście do lochu, jak to możliwe, przed cofnięciem.