Według tych notatek , DFS jest uważany za złożoność przestrzeń, gdzie jest współczynnik rozgałęzienia drzewa i jest maksymalna długość każdej ścieżki w przestrzeni stanów.
To samo zostało powiedziane na tej stronie Wikibook w Search Uninformed Search .
Teraz „infobox” artykułu Wikipedii na temat DFS przedstawia następujące aspekty złożoności algorytmu:
, jeśli cały wykres jest przemieszczany bez powtórzeń, najdłuższa szukana długość ścieżki dla ukrytych wykresów bez eliminacji duplikatów węzłów
co jest bardziej podobne do tego, co myślałem, o złożoności przestrzeni DFS, tj. , gdzie jest maksymalną długością osiągniętą przez algorytm.
Dlaczego tak myślę?
Cóż, w zasadzie nie musimy przechowywać żadnych innych węzłów niż węzły ścieżki, na którą obecnie patrzymy, więc nie ma sensu mnożenie przez analizie dostarczonej zarówno przez Wikibook, jak i notatki, które ci poleciłem do.
Ponadto, zgodnie z tym papieru na IDA * przez Richard Korf złożoność przestrzeń DFS , gdzie jest uważany za „głębokość odcięcia”.
Jaka jest poprawna złożoność przestrzeni DFS?
Myślę, że może to zależeć od implementacji, dlatego doceniłbym wyjaśnienie złożoności przestrzeni dla różnych znanych implementacji.
DFS is considered to […] of the tree
Nie każdy wykres ruch głębokość pierwszy to drzewo .example where a depth-first traversal on a graph would not result in a tree
bez zastanowienia: parsowanie. (Czekaj: co masz na myśliresult in a tree
Odpowiedzi:
To zależy od tego, co dokładnie nazywasz DFS. Rozważmy na przykład algorytm iteracyjny DFS opisany w Wikipedii i załóżmy, że uruchamiasz go na drzewie, abyś nie musiał śledzić, które węzły już odwiedziłeś. Załóżmy, że uruchamiasz go na pełnym -drzewku o głębokości . Możemy zidentyfikować węzły w ich drzewie słowami o długości co najwyżej . Algorytm działa w następujący sposób:b m [b] m
Zacznij od katalogu głównego. Wciśnij na stos (w odwrotnej kolejności).1,2,…,b
Pop i pchnij na stos.1 11,12,…,1b
Pop i pchnij na stos.11 111,112,…,11b
Pop i pchnij na stos.1m−1 1m,1m−12,…,1m−1b
W tym momencie stos zawiera
dla łącznie węzłów. Możesz sprawdzić, czy jest to pół kwarty w czasie, w którym maksymalny jest rozmiar stosu.(b−1)m+1
źródło
Są tutaj dwa punkty:
W przypadku wprowadzenia do stosu wszystkich potomków bieżącego węzła, wówczas złożoność przestrzeni wynosi gdzie jest współczynnikiem rozgałęzienia, a jest maksymalną długością. Odpowiedź Yuvala Filmusa rzeczywiście odnosi się do tej sprawy. Należy jednak pamiętać, że ogólnie jest znacznie większe niż . Co więcej, w wielu domenach, takich jak układanka z przesuwanymi kafelkami, jest górne ograniczone stałą (w tym konkretnym przypadku 4), a zatem możemy śmiało powiedzieć, że DFS ma złożoność przestrzenną, którą jest .O(bd) b d d b b O(d)
Trzeba jednak przyznać, że nie zawsze tak jest. Na przykład w układance Pancake współczynnik rozgałęzienia rośnie wraz z długością optymalnego rozwiązania i oba mają podobne wartości. Mimo to złożoność przestrzeni wynosi . Aby to zobaczyć, po prostu popraw procedurę ekspansji dowolnego węzła: Zamiast wstawiać wszystkich potomków bieżącego węzła (jak sugeruje Yuval Filmus) wstaw je w kolejności. Najpierw generujesz pierwszego potomka, a natychmiast po przejściu do pierwszej kolejności głębokości - w rzeczywistości nie potrzebujesz w tym momencie wszystkich innych potomkówO(d) . W przypadku powrotu do tego węzła jego potomek został usunięty ze stosu. Następnie wygeneruj drugiego potomka i kontynuuj ponownie w pierwszej kolejności w głębokości. W przypadku powrotu do tego węzła, wygeneruj trzeci i tak dalej, aż nie będzie już potomków. Postępując w ten sposób, będziesz mieć tylko węzłów na swoim stosie, bez względu na czynnik rozgałęziający, .d b
Podsumowując, nigdy nie powiedziałbym, że DFS ma złożoność przestrzeni, która wynosi a zamiast tego twierdzę, że jego złożoność przestrzeni wynosi .O(bd) O(d)
Mam nadzieję że to pomoże,
źródło