Przeszukiwanie wykresów: Najpierw szerokość kontra najpierw głębokość


78

Podczas poszukiwania wykresy istnieją dwa proste algorytmy: szerokość pierwszego i głębokość pierwszego (zazwyczaj przez dodanie wszystkich węzłów adjactent wykres w kolejce (wszerz) lub stosu (głębokość pierwszego)).

Czy są jakieś zalety jednego nad drugim?

Te, o których mogłem myśleć:

  • Jeśli spodziewasz się, że Twoje dane będą znajdować się dość głęboko na wykresie, najpierw głębokość może je znaleźć wcześniej, ponieważ bardzo szybko schodzisz do głębszych części wykresu.
  • I odwrotnie, jeśli spodziewasz się, że twoje dane będą dość wysoko na wykresie, szerokość w pierwszej kolejności może dać wynik wcześniej.

Czy coś mi umknęło, czy sprowadza się to głównie do osobistych preferencji?

Odpowiedzi:


43

Chciałbym zacytować odpowiedź z Stack Overflow autorstwa hstoerr, która ładnie obejmuje problem:

To w dużej mierze zależy od struktury drzewa wyszukiwania oraz liczby i lokalizacji rozwiązań .
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 zakorzenić się na zawsze, 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, 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ć.

Rafał Dowgird zauważa również:

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.


5
Nie rozumiem, dlaczego ta odpowiedź ma 27 pozytywnych opinii i jest to dokładnie połączenie 2 innych odpowiedzi, które, nawiasem mówiąc, są po prostu ogólnymi przemyśleniami na temat ...
nbro

37

Jeden punkt, który jest ważny w naszym świecie wielordzeniowym: BFS jest znacznie łatwiejszy do zrównoleglenia. Jest to intuicyjnie uzasadnione (wysyłaj wątki dla każdego dziecka) i można to udowodnić. Więc jeśli masz scenariusz, w którym możesz skorzystać z równoległości, to BFS jest właściwą drogą.


8
Jeśli DFS jest poza tym korzystny w danym ustawieniu, możesz zastosować BFS, dopóki nie utworzysz wystarczającej liczby wątków i kontynuujesz pracę z DFS. Mówiąc dokładniej, możesz wykonać DFS, a gdy schodzisz i nie ma wystarczającej liczby wątków, spawnuj jeden dla następnego rodzeństwa.
Raphael

Ta odpowiedź nie zasługuje na 20 pozytywnych opinii. Pytanie dotyczy ogólnego zastosowania 2 algorytmów, a nie konkretnego zastosowania.
nbro

31

(Stworzyłem to wiki społeczności. Możesz je edytować.)

Jeśli

  • b
  • re
  • hreh

Następnie

  • O(bh)O(h)
  • O(bre)O(bre)
  • O(bre)O(re)

Powody wyboru

  • DFS
    • i tak musi zobaczyć całe drzewo
    • re
    • nie obchodzi mnie, czy odpowiedź jest najbliższa rootowi
  • BFS
    • odpowiedź jest blisko źródła
    • chcesz odpowiedzi najbliżej rdzenia
    • mieć wiele rdzeni / procesorów
  • IDDFS
    • chcesz BFS, nie masz wystarczającej ilości pamięci, ale akceptowalne jest nieco wolniejsze

IDDFS = iteracyjne pogłębianie pierwsze wyszukiwanie głębokości


1
To doskonała odpowiedź. Zauważam jednak, że choć pytanie dotyczy grafów, ta odpowiedź dotyczy drzew. Drzewo jest oczywiście wykresem i może to być słowo, które można zastąpić ... ale co powiesz hna „wysokość drzewa”. Czy to przekłada się bezpośrednio na „wysokość wykresu”?
user2023370 26.04.16

Innym powodem korzystania z IDDFS jest to, że w zależności od tego, jak chcesz go używać, po każdej iteracji możesz uzyskać możliwą odpowiedź (jeśli szukasz, powiedzmy, maksimum lub minimum). Oznacza to, że możesz wyjść z algorytmu wcześniej, jeśli twoja odpowiedź jest „wystarczająco dobra” lub możesz wyjść z wprowadzania danych przez użytkownika (np. Silnik szachowy używający IDDFS w celu znalezienia optymalnego rozwiązania, ale przerywany przez gracza przenoszącego pionek).
jedd.ahyoung

Kolejną kwestią, którą należy dodać, jest to, że DFS używa stosu, podczas gdy BFS używa kolejki.
Karthik Balaguru

17

Jeden ze scenariuszy (inny niż znalezienie najkrótszej ścieżki, o której już wspomniano), w którym konieczne może być wybranie jednego z drugiego, aby uzyskać poprawny program, byłby nieskończonymi wykresami:

Jeśli weźmiemy na przykład drzewo, w którym każdy węzeł ma skończoną liczbę dzieci, ale wysokość drzewa jest nieskończona, DFS może nigdy nie znaleźć poszukiwanego węzła - po prostu odwiedza pierwsze dziecko każdego węzła widzi, więc jeśli ten, którego szukasz, nie jest pierwszym dzieckiem jego rodzica, nigdy się tam nie dostanie. BFS ma jednak gwarancję znalezienia go w skończonym czasie.

Podobnie, jeśli weźmiemy pod uwagę drzewo, w którym każdy węzeł ma nieskończoną liczbę dzieci, ale drzewo ma skończoną wysokość, BFS może nie zostać zakończony. Odwiedzą tylko dzieci węzła głównego, a jeśli szukany węzeł jest dzieckiem innego węzła, nie zostanie osiągnięty. W takim przypadku DFS gwarantuje, że znajdzie go w skończonym czasie.


7
Warto zauważyć, że oba dają tylko algorytmy półdecydowania dla nieskończonych grafów; nie możesz zdecydować w skończonym czasie, że elementu nie ma w drzewie (oczywiście). Jeśli chodzi o praktyczne zastosowania, należy pamiętać, że (koncepcyjnie) można zdefiniować nieskończone struktury danych (patrz akapit 3.4)!
Raphael

15

Najpierw szerokość i pierwsza głębokość z pewnością zachowują się w najgorszym przypadku (pożądany węzeł jest ostatnim znalezionym). Podejrzewam, że dotyczy to również przypadku średniego, jeśli nie masz informacji o swoich wykresach.

Jedną z miłych zalet pierwszego wyszukiwania jest to, że znajduje najkrótsze ścieżki (w sensie najmniejszej liczby krawędzi), które mogą lub nie mogą być interesujące.

Jeśli średnia ranga węzła (liczba sąsiadów) jest wysoka w stosunku do liczby węzłów (tj. Wykres jest gęsty), szerokość-pierwsze będą miały ogromne kolejki, a pierwsze-głębokie będą mieć małe stosy. Na rzadkich wykresach sytuacja jest odwrócona. Dlatego, jeśli pamięć jest czynnikiem ograniczającym, kształt wykresu może być niezbędny do wyboru strategii wyszukiwania.


Długość kolejki w bfs i wysokość stosu w dfs zależy w dużej mierze od implementacji. Jeśli w przypadku dfs zawsze rozszerzasz cały neighbouroud na stosie, wtedy rośnie on dużo, szczególnie gdy wykres jest gęsty. Pchanie tylko referencji, która mówi, gdzie kontynuować, gdy dfs wraca z rekurencji, oszczędza dużo miejsca.
uli

3

Wszystkie powyższe informacje są poprawne, ale warto zauważyć, że BFS i DFS tworzą własne drzewa, w oparciu o kolejność, w jakiej używają drzewa do przejścia. Każde z tych drzew ma swoją własność, która może być przydatna w niektórych problemach.

Na przykład wszystkie krawędzie oryginalnego wykresu, które nie znajdują się w drzewie BFS, są poprzecznymi krawędziami; krawędzie, które znajdują się między dwiema gałęziami drzewa BFS. Wszystkie krawędzie oryginalnego wykresu, które nie znajdują się w drzewie DFS, są tylnymi krawędziami; krawędzie łączące dwa wierzchołki w gałęzi drzewa DFS. Takie właściwości mogą być przydatne w przypadku problemów, takich jak specjalne zabarwienie itp.


1

Zarówno drzewa DFS, jak i BFS mają swoje unikalne właściwości, które mogą dostarczyć bardziej przydatnych informacji o wykresie. Na przykład za pomocą pojedynczego systemu plików DFS można wykonać następujące czynności:

  • Znajdź mosty i punkty artykulacji (dla niekierowanych wykresów)
  • Wykrywanie cyklu
  • Znajdź silnie połączone komponenty (algorytm Tarjana)

Dzięki BFS można znaleźć najkrótsze ścieżki między węzłem źródłowym a dowolnymi innymi węzłami na wykresie.

Rozdział Algorytmy grafów w CLRS bardzo ładnie podsumowuje te właściwości DFS i BFS.


-2

Myślę, że byłoby interesujące napisać oba z nich w taki sposób, że tylko zmiana niektórych linii kodu dałaby ci jeden algorytm lub drugi, abyś zobaczył, że twój dillema nie jest tak silny, jak się wydaje na początku .

Osobiście podoba mi się interpretacja BFS jako zalania krajobrazu: obszary o małej wysokości zostaną najpierw zalane, a dopiero potem nadejdą obszary o dużej wysokości. Jeśli wyobrażasz sobie, że wysokości krajobrazu są tak izolyniczne, jak widzimy w książkach geograficznych, łatwo zauważyć, że BFS wypełnia cały obszar pod tą samą izolacją w tym samym czasie, tak jak byłoby to w przypadku fizyki. Tak więc interpretacja wysokości jako odległości lub skalowanego kosztu daje całkiem intuicyjne wyobrażenie o algorytmie.

Mając to na uwadze, możesz łatwo dostosować ideę leżącą u podstaw pierwszego wyszukiwania, aby łatwo znaleźć minimalne drzewo opinające, najkrótszą ścieżkę, a także wiele innych algorytmów minimalizacji.

Nie widziałem jeszcze żadnej intuicyjnej interpretacji DFS (tylko standardowa w labiryncie, ale nie jest tak potężna jak BFS i powódź), więc dla mnie wydaje się, że BFS wydaje się lepiej korelować ze zjawiskami fizycznymi, jak opisano powyżej, podczas gdy DFS lepiej koreluje z wyborami dillema w racjonalnych systemach (tj. Ludzie lub komputery decydują, który ruch wybrać w szachy lub wyjść z labiryntu).

Tak więc dla mnie różnica między kłamstwami, na których zjawisko naturalne najlepiej odpowiada ich modelowi propagacji (transwersacji) w prawdziwym życiu.


2
Witamy na stronie! Jednak tak naprawdę nie rozumiem, jak to odpowiada na pytanie. Wydaje się, że to twoje ogólne odczucia i intuicje dotyczące BFS i DFS, ale pytanie nie dotyczy uczuć i intuicji: chodzi o zalety i wady. Twoja odpowiedź wcale na to nie odpowiada.
David Richerby,

Część najbardziej związana z pytaniem dotyczy dostosowania algorytmu w celu znalezienia minimalnego drzewa opinającego, najkrótszej ścieżki itd.
Oraz

1
Pytanie nie dotyczy pytania o BFS i DFS. Nie chodzi o znalezienie drzew opinających lub najkrótszych ścieżek, ani o „odtworzenie zjawisk naturalnych”.
David Richerby,

Prosi o zalety. Jeśli można modelować zjawiska fizyczne, podczas gdy inne nie mogą, jego zaletą jest konieczność modelowania tych zjawisk. Myślę, że trzymasz się standardowych pojęć podręcznika algorytmów, interpretując słowo „korzyść”, podczas gdy ja nie jestem
user5193682,
Korzystając z naszej strony potwierdzasz, że przeczytałeś(-aś) i rozumiesz nasze zasady używania plików cookie i zasady ochrony prywatności.
Licensed under cc by-sa 3.0 with attribution required.