Dlaczego uważa się, że DFS ma złożoność przestrzeni ?

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.$O(bm)$$b$$m$

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:

$O(|V|)$ , 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$O($$)$

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.$O(m)$$m$

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.$b$

Ponadto, zgodnie z tym papieru na IDA * przez Richard Korf złożoność przestrzeń DFS , gdzie jest uważany za „głębokość odcięcia”.$O(d)$$d$

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.

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$

1. Zacznij od katalogu głównego. Wciśnij na stos (w odwrotnej kolejności).$1,2,\ldots,b$

2. Pop i pchnij na stos.$1$$11,12,\ldots,1b$

3. Pop i pchnij na stos.$11$$111,112,\ldots,11b$

4. $\ldots$

5. Pop i pchnij na stos.$1^{m-1}$$1^m,1^{m-1}2,\ldots,1^{m-1}b$

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$

Są tutaj dwa punkty:

1. 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)$

2. 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ów$O(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,