Dowiedziałem się, jak działają te algorytmy, ale do czego są one używane?Jaki jest cel BFS i DFS?
Czy używamy im:
?
Obydwaj po prostu odwiedzają wszystkie węzły i zaznaczają je odwiedzone, a ja nie widzę sensu tego.
Jestem trochę zagubiony, czego się uczę.
BFS i DFS to algorytmy wyszukiwania wykresów, które mogą być używane do różnych celów.
Jedną z powszechnych zastosowań dwóch technik wyszukiwania jest identyfikacja wszystkich węzłów, do których można uzyskać dostęp z danego węzła początkowego. Załóżmy na przykład, że masz kolekcję komputerów, z których każdy jest połączony w sieć z kilkoma innymi komputerami. Po uruchomieniu BFS lub DFS z danego węzła odkryjesz wszystkie inne komputery w sieci, z którymi oryginalny komputer może bezpośrednio lub pośrednio rozmawiać. Są to komputery, które wracają oznaczone.
BFS można użyć do znalezienia najkrótszej ścieżki między dwoma węzłami na nieważonym wykresie. Załóżmy na przykład, że chcesz wysłać pakiet z jednego komputera w sieci do drugiego i że komputery nie są bezpośrednio ze sobą połączone. Na jakiej trasie należy wysłać pakiet, aby jak najszybciej dotrzeć do celu? Jeśli uruchomisz system plików BFS iw każdej iteracji każdy węzeł będzie przechowywać wskaźnik do swojego "nadrzędnego" węzła, w końcu znajdziesz trasę od węzła początkowego do każdego innego węzła na wykresie, co zminimalizuje liczbę połączeń, które mają być wykonywane. aby dotrzeć do komputera docelowego.
DFS jest często stosowany jako podprogram w bardziej złożonych algorytmach. Na przykład algorytm Tarjana do obliczania silnie połączonych komponentów opiera się na pierwszym wyszukiwaniu. Wiele optymalizujących technik kompilacji uruchamia DFS na odpowiednio skonstruowanym wykresie w celu ustalenia, w jakiej kolejności zastosować określoną serię operacji. Wyszukiwanie w pierwszej kolejności może być również wykorzystane w generowaniu labiryntu: poprzez wykonanie siatki węzłów i powiązanie każdego węzła z sąsiadami można skonstruować wykres reprezentujący siatkę. Uruchamianie losowego pierwszego wyszukiwania w głąb nad tym wykresem powoduje powstanie labiryntu, który ma dokładnie jedno rozwiązanie.
W żadnym wypadku nie jest to wyczerpująca lista. Algorytmy te mają wiele różnych aplikacji, a gdy zaczniesz odkrywać bardziej zaawansowane algorytmy, często będziesz polegać na DFS i BFS jako elementach konstrukcyjnych. Jest podobny do sortowania - sortowanie samo w sobie nie jest aż tak interesujące, ale możliwość sortowania listy wartości jest niezwykle użyteczny jako podprocedura w bardziej złożonych algorytmach.
Mam nadzieję, że to pomoże!
Algorytmy wyszukiwania to tylko narzędzie, za pomocą którego można rozwiązywać inne problemy. To tak, jakby pytać, do czego służy dodatek. –