Algorytmy i struktury danych · Senior · Pytanie 62 z 75
Dlaczego dla niektórych łamigłówek DFS jest lepszy od BFS, choć BFS znajduje najkrótsze rozwiązania?
- 1BFS nie radzi sobie z grafami zawierającymi cykle
- ✓Poprawna odpowiedź: DFS trzyma jedną ścieżkę, a BFS cały front
- 3DFS zawsze znajduje rozwiązanie w mniejszej liczbie kroków
Wyjaśnienie
Przy współczynniku rozgałęzienia b i głębokości d BFS trzyma w kolejce do bᵈ stanów. DFS z iteracyjnym pogłębianiem bierze to, co najlepsze z obu: najkrótsze rozwiązania przy O(d) pamięci, kosztem powtarzania płytkich poziomów.