Jaka jest różnica między cofaniem a pierwszym przeszukiwaniem w głąb?
Jaka jest różnica między cofaniem a pierwszym przeszukiwaniem w głąb?
Odpowiedzi:
Wycofywanie się jest algorytmem bardziej ogólnego przeznaczenia.
Przeszukiwanie w głąb jest specyficzną formą wycofywania się związaną z przeszukiwaniem struktur drzewiastych. Z Wikipedii:
Zaczyna się od korzenia (wybierając jakiś węzeł jako korzeń w przypadku wykresu) i eksploruje tak daleko, jak to możliwe, wzdłuż każdej gałęzi przed cofnięciem.
Wykorzystuje wycofywanie jako część swoich metod pracy z drzewem, ale ogranicza się do struktury drzewa.
Jednak cofanie może być używane w każdym typie struktury, w której można wyeliminować części domeny - niezależnie od tego, czy jest to drzewo logiczne. Przykład Wiki wykorzystuje szachownicę i konkretny problem - możesz przyjrzeć się konkretnemu ruchowi i go wyeliminować, a następnie cofnąć się do następnego możliwego ruchu, wyeliminować go itp.
Myślę, że ta odpowiedź na inne powiązane pytanie daje więcej informacji.
Dla mnie różnica między wycofywaniem a DFS polega na tym, że wycofywanie obsługuje niejawne drzewo, a DFS zajmuje się jawnym. Wydaje się to trywialne, ale wiele znaczy. Kiedy przestrzeń poszukiwań problemu jest odwiedzana przez cofanie się, niejawne drzewo jest przecinane i przycinane w środku. Jednak w przypadku DFS drzewo / wykres, którym się zajmuje, jest wyraźnie skonstruowane, a niedopuszczalne przypadki zostały już odrzucone, tj. Przycięte, przed wykonaniem jakiegokolwiek wyszukiwania.
Tak więc wycofywanie jest DFS dla niejawnego drzewa, podczas gdy DFS jest cofaniem bez przycinania.
Wycofywanie jest zwykle realizowane jako system plików DFS plus przycinanie wyszukiwania. Przechodzisz przez drzewo w głębi przestrzeni wyszukiwania, najpierw konstruując rozwiązania częściowe. Brute-force DFS może tworzyć wszystkie wyniki wyszukiwania, nawet te, które praktycznie nie mają sensu. Może to być również bardzo nieefektywne przy konstruowaniu wszystkich rozwiązań (n! Lub 2 ^ n). Tak więc w rzeczywistości, tak jak robisz DFS, musisz również przyciąć rozwiązania częściowe, które nie mają sensu w kontekście rzeczywistego zadania, i skupić się na rozwiązaniach częściowych, które mogą prowadzić do prawidłowych rozwiązań optymalnych. To jest właściwa technika wycofywania się - odrzucasz częściowe rozwiązania tak wcześnie, jak to możliwe, cofasz się o krok i ponownie próbujesz znaleźć lokalne optimum.
Nic nie zatrzymuje się, aby przejść przez drzewo przestrzeni wyszukiwania za pomocą BFS i wykonać strategię śledzenia wstecznego po drodze, ale w praktyce nie ma to sensu, ponieważ musiałbyś przechowywać stan wyszukiwania warstwa po warstwie w kolejce, a szerokość drzewa rośnie wykładniczo do wysokości, więc bardzo szybko stracilibyśmy dużo miejsca. Dlatego drzewa są zwykle pokonywane przy użyciu DFS. W tym przypadku stan wyszukiwania jest przechowywany na stosie (stos wywołań lub jawna struktura) i nie może przekraczać wysokości drzewa.
Według Donalda Knutha jest tak samo. Oto link w jego artykule na temat algorytmu Dancing Links, który jest używany do rozwiązywania problemów „niebędących drzewami”, takich jak N-queens i Sudoku.
Zwykle przeszukiwanie w głąb jest sposobem na iterację przez rzeczywistą strukturę wykresu / drzewa w poszukiwaniu wartości, podczas gdy cofanie się to iteracja w przestrzeni problemu w poszukiwaniu rozwiązania. Wycofywanie się to bardziej ogólny algorytm, który niekoniecznie musi odnosić się nawet do drzew.
Powiedziałbym, że DFS jest specjalną formą wycofywania; wycofywanie jest ogólną formą DFS.
Jeśli rozszerzymy DFS na ogólne problemy, możemy to nazwać cofaniem. Jeśli używamy cofania się do problemów związanych z drzewem / wykresem, możemy to nazwać DFS.
Niosą tę samą ideę w aspekcie algorytmicznym.
IMHO, większość odpowiedzi jest w dużej mierze nieprecyzyjna i / lub bez odniesienia do weryfikacji. Pozwólcie więc, że podzielę się bardzo jasnym wyjaśnieniem z odniesieniem .
Po pierwsze, DFS jest ogólnym algorytmem przechodzenia (i wyszukiwania) grafu. Więc można go zastosować do dowolnego wykresu (lub nawet lasu). Drzewo to specjalny rodzaj wykresu, więc DFS działa również dla drzewa. Krótko mówiąc, przestańmy mówić, że działa tylko na drzewo lub coś podobnego.
Opierając się na [1], Backtracking jest specjalnym rodzajem DFS używanym głównie do oszczędzania miejsca (pamięci). Rozróżnienie, o którym mam zamiar wspomnieć, może wydawać się zagmatwane, ponieważ w algorytmach Graph tego rodzaju jesteśmy tak przyzwyczajeni do posiadania reprezentacji list przylegania i korzystania z iteracyjnego wzorca do odwiedzania wszystkich bezpośrednich sąsiadów (w przypadku drzewa są to bezpośrednie dzieci ) węzła , często ignorujemy, że zła implementacja get_all_immediate_neighbors może powodować różnice w wykorzystaniu pamięci przez bazowy algorytm.
Ponadto, jeśli węzeł wykresu ma współczynnik rozgałęzienia b i średnicę h ( dla drzewa jest to wysokość drzewa ), jeśli przechowujemy wszystkich bezpośrednich sąsiadów na każdym etapie odwiedzania węzła, wymagania dotyczące pamięci będą duże-O (bh) . Jeśli jednak weźmiemy tylko jednego (bezpośredniego) sąsiada na raz i rozszerzymy go, wówczas złożoność pamięci zmniejszy się do dużego-O (h) . Podczas gdy pierwszy rodzaj implementacji jest określany jako DFS , drugi typ nazywa się Backtracking .
Teraz widzisz, jeśli pracujesz z językami wysokiego poziomu, najprawdopodobniej używasz cofania pod postacią DFS. Ponadto śledzenie odwiedzonych węzłów dla bardzo dużego zestawu problemów może wymagać naprawdę dużej ilości pamięci; wzywając do starannego zaprojektowania get_all_immediate_neighbors (lub algorytmów, które mogą obsługiwać ponowne odwiedzanie węzła bez wchodzenia w nieskończoną pętlę).
[1] Stuart Russell i Peter Norvig, Artificial Intelligence: A Modern Approach, 3rd Ed
Najpierw głębokość to algorytm przechodzenia lub przeszukiwania drzewa. Zobacz tutaj . Wycofywanie się to znacznie szerszy termin, który jest używany za każdym razem, gdy tworzy się kandydat na rozwiązanie, a następnie jest odrzucany przez powrót do poprzedniego stanu. Zobacz tutaj . Wyszukiwanie wgłębne najpierw wykorzystuje śledzenie wstecz, aby najpierw przeszukać gałąź (kandydat na rozwiązanie), a jeśli nie powiedzie się, przeszukać inne gałęzie.
IMO, w dowolnym węźle cofania, próbujesz najpierw zagłębić rozgałęzienie do każdego z jego elementów podrzędnych, ale zanim rozwiniesz którykolwiek z węzłów potomnych, musisz "wymazać" stan poprzedniego dziecka (ten krok jest równoważny z powrotem iść do węzła nadrzędnego). Innymi słowy, stan każdego rodzeństwa nie powinien na siebie wpływać.
Wręcz przeciwnie, podczas normalnego algorytmu DFS zwykle nie masz tego ograniczenia, nie musisz wymazywać (wstecznego) stanu poprzedniego rodzeństwa, aby zbudować następny węzeł rodzeństwa.
DFS opisuje sposób, w jaki chcesz eksplorować lub przechodzić przez wykres. Koncentruje się na koncepcji zagłębiania się tak głęboko, jak to możliwe, mając wybór.
Wycofywanie, choć zwykle realizowane przez DFS, koncentruje się bardziej na koncepcji jak najwcześniejszego przycinania niepomyślnych podprzestrzeni wyszukiwania.
W przeszukiwaniu wgłębnym zaczynasz od korzenia drzewa, a następnie eksplorujesz każdą gałąź, a następnie cofasz się do każdego kolejnego węzła nadrzędnego i przechodzisz przez jego dzieci
Wycofywanie się to uogólniony termin rozpoczynający się na końcu celu i stopniowo cofający się, stopniowo budując rozwiązanie.
Pomysł - Zacznij od dowolnego punktu, sprawdź, czy jest to pożądany punkt końcowy, jeśli tak, to znaleźliśmy rozwiązanie, które prowadzi do wszystkich następnych możliwych pozycji, a jeśli nie możemy iść dalej, wróć do poprzedniej pozycji i poszukaj innych alternatyw oznaczających ten bieżący ścieżka nie doprowadzi nas do rozwiązania.
Teraz cofanie i DFS to dwie różne nazwy nadane tej samej idei, zastosowane do 2 różnych abstrakcyjnych typów danych.
Jeśli idea zostanie zastosowana na macierzowej strukturze danych, nazywamy to cofaniem.
Jeśli ten sam pomysł zostanie zastosowany na drzewie lub wykresie, nazywamy to DFS.
Frazes jest taki, że macierz można przekształcić w wykres, a wykres można przekształcić w macierz. Więc faktycznie stosujemy ten pomysł. Jeśli na wykresie nazywamy to DFS, a jeśli na macierzy, to nazywamy to śledzeniem wstecznym.
Pomysł w obu algorytmach jest taki sam.
Wycofywanie się to tylko pierwsze przeszukiwanie w głąb z określonymi warunkami zakończenia.
Zastanów się nad przejściem przez labirynt, w którym na każdym kroku podejmujesz decyzję, ta decyzja jest wezwaniem do stosu wywołań (który przeprowadza pierwsze wyszukiwanie głębokości) ... jeśli dotrzesz do końca, możesz zawrócić swoją ścieżką. Jeśli jednak dojdziesz do martwego punktu, chcesz powrócić z pewnej decyzji, w istocie powracając z funkcji na swoim stosie wywołań.
Więc kiedy myślę o wycofaniu się, obchodzi mnie
Wyjaśniam to w moim filmie o cofaniu się tutaj .
Poniżej znajduje się analiza kodu cofania. W tym kodzie cofania chcę znaleźć wszystkie kombinacje, które spowodują określoną sumę lub cel. Dlatego mam 3 decyzje, które wywołują mój stos wywołań, przy każdej decyzji mogę albo wybrać numer jako część mojej ścieżki, aby osiągnąć docelowy numer, pominąć ten numer lub wybrać go i wybrać ponownie. A jeśli osiągnę stan zakończenia, moim krokiem wstecz jest po prostu powrót . Powrót jest krokiem wycofywania, ponieważ wychodzi z tego wywołania na stosie wywołań.
class Solution:
"""
Approach: Backtracking
State
-candidates
-index
-target
Decisions
-pick one --> call func changing state: index + 1, target - candidates[index], path + [candidates[index]]
-pick one again --> call func changing state: index, target - candidates[index], path + [candidates[index]]
-skip one --> call func changing state: index + 1, target, path
Base Cases (Termination Conditions)
-if target == 0 and path not in ret
append path to ret
-if target < 0:
return # backtrack
"""
def combinationSum(self, candidates: List[int], target: int) -> List[List[int]]:
"""
@desc find all unique combos summing to target
@args
@arg1 candidates, list of ints
@arg2 target, an int
@ret ret, list of lists
"""
if not candidates or min(candidates) > target: return []
ret = []
self.dfs(candidates, 0, target, [], ret)
return ret
def dfs(self, nums, index, target, path, ret):
if target == 0 and path not in ret:
ret.append(path)
return #backtracking
elif target < 0 or index >= len(nums):
return #backtracking
# for i in range(index, len(nums)):
# self.dfs(nums, i, target-nums[i], path+[nums[i]], ret)
pick_one = self.dfs(nums, index + 1, target - nums[index], path + [nums[index]], ret)
pick_one_again = self.dfs(nums, index, target - nums[index], path + [nums[index]], ret)
skip_one = self.dfs(nums, index + 1, target, path, ret)