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

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?

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.

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ą.

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

Jeśli

• $b$
• $d$
• $h$$d\le h$

Następnie

• $O(b^h)$$O(h)$
• $O(b^d)$$O(b^d)$
• $O(b^d)$$O(d)$

Powody wyboru

• DFS
  • i tak musi zobaczyć całe drzewo
  • $d$
  • 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

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.

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.

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.

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.

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.