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

11

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)bm

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łówO()

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.

nbro
źródło
DFS is considered to […] of the treeNie każdy wykres ruch głębokość pierwszy to drzewo .
siwobrody
Istnieje różnica między powiedzeniem „tutaj implementacja DFS kosztuje X”, a „DFS można wdrożyć, aby kosztować X”. Wydaje się więc, że kłócą się o różne stwierdzenia drugiego rodzaju, które wcale nie muszą być ze sobą sprzeczne. (Zauważ, że w ogóle nie ma sprzeczności, ponieważ , jeśli ma w ogóle coś znaczyć).O(bm)O(m)O(bm)
Raphael
@greybeard Czy możesz mi powiedzieć przykład, w którym przejście przez głębokość na wykresie nie dałoby drzewa?
nro
example where a depth-first traversal on a graph would not result in a treebez zastanowienia: parsowanie. (Czekaj: co masz na myśli result in a tree
:?
1
@greybeard Zgodnie ze wszystkimi definicjami, które znalazłem do tej pory. Znajdź mi definicję, w której ponownie odwiedza węzły, a następnie możemy o tym porozmawiać.
nro

Odpowiedzi:

7

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:bm[b]m

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

  2. Pop i pchnij na stos.111,12,,1b

  3. Pop i pchnij na stos.11111,112,,11b

  4. Pop i pchnij na stos.1m11m,1m12,,1m1b

W tym momencie stos zawiera

1m,1m12,,1m1b,,112,,11b,12,,1b,2,,b,

dla łącznie węzłów. Możesz sprawdzić, czy jest to pół kwarty w czasie, w którym maksymalny jest rozmiar stosu.(b1)m+1

Yuval Filmus
źródło
2
Kufel czasu powstrzymuje lekarza.
greybeard
3

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)bddbbO(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ó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, .db

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,

Carlos Linares López
źródło