Przeszukiwanie w głąb (DFS) w sztucznej inteligencji

Wprowadzenie

Przeszukiwanie w głąb (ang. Depth-First Search, DFS) to jeden z fundamentalnych algorytmów przeszukiwania grafów i drzew, szeroko wykorzystywany w dziedzinie sztucznej inteligencji. Jego głównym celem jest systematyczne eksplorowanie wierzchołków grafu poprzez zagłębianie się wzdłuż każdej możliwej ścieżki tak daleko, jak to możliwe, zanim nastąpi powrót i eksploracja innych gałęzi. Jest to technika szczególnie przydatna w problemach, gdzie celem jest znalezienie jakiejkolwiek ścieżki do rozwiązania, a niekoniecznie najkrótszej. W kontekście AI, DFS znajduje zastosowanie w rozwiązywaniu łamigłówek, planowaniu ścieżek, systemach eksperckich oraz w algorytmach typu backtracking. Jego siła tkwi w prostocie implementacji i efektywności pamięciowej, co czyni go atrakcyjnym wyborem dla problemów o głębokich, ale niekoniecznie szerokich przestrzeniach stanów.

Jak działają Przeszukiwanie w głąb (DFS)?

Algorytm Przeszukiwania w Głąb rozpoczyna swoją pracę od wybranego wierzchołka początkowego, a następnie systematycznie eksploruje jego sąsiadów. Zamiast przechodzić przez wszystkich sąsiadów na tym samym poziomie, wybiera jednego z nich i kontynuuje proces eksploracji od tego nowego wierzchołka, zagłębiając się coraz bardziej w strukturę grafu. Proces ten jest rekurencyjny i przypomina podróż w tunelu – idziemy naprzód, dopóki nie napotkamy ściany, a dopiero wtedy wracamy, aby zbadać inną odnogę. Technicznie, DFS zazwyczaj wykorzystuje strukturę danych typu stos (lub rekurencję, która wewnętrznie działa jak stos). Gdy algorytm odwiedza wierzchołek, oznacza go jako odwiedzony i dodaje do stosu jego nieodwiedzonych sąsiadów. Następnie pobiera kolejny wierzchołek ze stosu i powtarza procedurę. Jeśli dany wierzchołek nie ma nieodwiedzonych sąsiadów, algorytm cofa się (usuwa wierzchołek ze stosu) i kontynuuje z poprzednio odwiedzonego wierzchołka, eksplorując inną ścieżkę. Przykładem może być rozwiązywanie labiryntu. DFS zaczyna od wejścia, wybiera jedną drogę i idzie nią do samego końca. Jeśli trafi na ślepą uliczkę, cofa się do ostatniego rozwidlenia i wybiera inną, wcześniej nieeksplorowaną ścieżkę. Ten proces powtarza się, aż do znalezienia wyjścia lub stwierdzenia, że wszystkie ścieżki zostały zbadane.

Główne zalety i charakterystyka

Jedną z kluczowych zalet DFS jest jego efektywność pamięciowa. W porównaniu do Przeszukiwania w Szerz (BFS), DFS potrzebuje znacznie mniej pamięci, ponieważ przechowuje w stosie jedynie wierzchołki na aktualnie badanej ścieżce, a nie wszystkie wierzchołki na bieżącym poziomie. Jest to szczególnie korzystne w przypadku bardzo szerokich grafów. Dodatkowo, DFS może szybko znaleźć rozwiązanie, jeśli znajduje się ono na bardzo głębokiej gałęzi drzewa lub grafu. Jego rekurencyjna natura prowadzi do zwięzłej i często intuicyjnej implementacji, co ułatwia jego zastosowanie w wielu problemach algorytmicznych i AI, gdzie problem może być naturalnie zdefiniowany w kategoriach zagłębiania się w stanach.

Zastosowania w praktyce

• Rozwiązywanie labiryntów i innych problemów znajdowania ścieżek w grafach bez wag.
• Wyszukiwanie komponentów spójnych w grafach, czyli zbiorów wierzchołków, które są ze sobą połączone.
• Wykrywanie cykli w grafach, co jest kluczowe w wielu algorytmach.
• Topologiczne sortowanie grafów skierowanych acyklicznych (DAG), np. w planowaniu zadań.
• Implementacja algorytmów backtracking, takich jak problem N-hetmanów czy Sudoku.
• Generowanie drzewa rozpinającego (spanning tree) dla grafu.
• Analiza sieci społecznościowych w celu identyfikacji zależności lub grup.
• Wyszukiwanie rozwiązań w przestrzeni stanów gier, takich jak szachy czy warcaby (często w połączeniu z innymi algorytmami jak Minimax).

Porównanie z innymi strukturami danych

Główna różnica między Przeszukiwaniem w Głąb (DFS) a Przeszukiwaniem w Szerz (BFS) leży w sposobie eksploracji grafu i używanych strukturach danych. DFS zagłębia się w każdą gałąź, używając stosu, co sprawia, że jest efektywny pamięciowo i szybko znajduje rozwiązania położone głęboko, ale niekoniecznie optymalne. BFS natomiast eksploruje graf poziom po poziomie, używając kolejki. Gwarantuje znalezienie najkrótszej ścieżki w grafach bez wag, ale jest znacznie bardziej wymagający pamięciowo, ponieważ musi przechowywać wszystkie wierzchołki na bieżącym poziomie. W AI wybór między DFS a BFS zależy od charakterystyki problemu: DFS jest preferowany, gdy szukamy jakiegokolwiek rozwiązania i pamięć jest ograniczona, lub gdy spodziewamy się głębokiego rozwiązania; BFS jest lepszy, gdy szukamy optymalnego (najkrótszego) rozwiązania.

Najlepsze praktyki (2026)

• Zawsze utrzymuj listę odwiedzonych wierzchołków, aby zapobiec zapętleniu się w grafach zawierających cykle.
• Dla grafów z bardzo głębokimi ścieżkami lub cyklami, rozważ zastosowanie iteracyjnego pogłębiania DFS (Iterative Deepening DFS) lub DFS z ograniczeniem głębokości (Depth-Limited Search), aby zapewnić kompletność i uniknąć nieskończonych pętli.
• Używaj jawnego stosu zamiast rekurencji dla bardzo głębokich drzew, aby uniknąć przepełnienia stosu systemowego (stack overflow).
• Łącz DFS z heurystykami (np. w algorytmie A* lub przeszukiwaniu z najlepszym pierwszym) w celu ukierunkowania przeszukiwania i szybszego znalezienia rozwiązania.
• Implementuj DFS w sposób modularny, oddzielając logikę odwiedzania wierzchołków od mechanizmu przeszukiwania, co ułatwia modyfikację i testowanie.

Typowe błędy i pułapki

• Nieskończone pętle: brak mechanizmu śledzenia odwiedzonych wierzchołków prowadzi do wielokrotnego odwiedzania tych samych wierzchołków w grafach z cyklami.
• Przepełnienie stosu (stack overflow): rekurencyjna implementacja DFS może spowodować przepełnienie stosu systemowego dla bardzo głębokich ścieżek.
• Znajdowanie nieoptymalnych rozwiązań: DFS nie gwarantuje znalezienia najkrótszej ścieżki do celu, ponieważ zawsze zagłębia się w pierwszą napotkaną ścieżkę.
• Niekompletność: w grafach z nieskończonymi gałęziami lub cyklami bez odpowiedniego ograniczenia, DFS może nigdy nie znaleźć rozwiązania.
• Zbyt wolne działanie dla szerokich grafów, gdzie rozwiązanie znajduje się blisko korzenia, ale na innej, niepierwszej gałęzi.