Przeszukiwanie w głąb

Przeszukiwanie w głąb (1) Przeszukiwanie w głąb, przykład

Przeszukiwanie w głąb (ang. depth-first search, w skrócie DFS) – jeden z dwóch podstawowych algorytmów przeszukiwania grafu. Polega na przechodzeniu zawsze do kolejnego nieodwiedzonego wierzchołka. Jeśli dany wierzchołek nie ma nieodwiedzonych sąsiadów, wracamy do poprzedniego wierzchołka i sprawdzamy jego sąsiadów. Mówiąc obrazowo, w algorytmie tym wchodzimy tak głęboko, jak to możliwe (przechodzimy dalej, dopóki się da).

Algorytm można zapisać w sposób rekurencyjny. Wywoływana rekurencyjnie procedura działa następująco: oznacz wierzchołek jako odwiedzony, a następnie wywołaj tę procedurę dla każdego sąsiada danego wierzchołka, jeśli nie został on wcześniej odwiedzony. Na początku wywołujemy procedurę dla wierzchołka początkowego.

Złożoność

Złożoność algorytmu jest rzędu O(v+e) – musimy sprawdzić wszystkie krawędzie i oznaczyć wszystkie wierzchołki. Jeśli każdy wierzchołek jest osiągalny ze źródła (po zakończeniu działania algorytmu nie będzie nieodwiedzonych wierzchołków), to e ≥ (v−1). Przy takim założeniu złożoność czasowa algorytmu wynosi O(e).

Ocena: +3 Tak Nie
Liczba głosów: 5.

Dodano: 27 listopada 2017 19:10, ostatnia edycja: 31 stycznia 2018 16:19.

REKLAMA

Zobacz też

K-opt, algorytm k-optymalny – algorytm lokalnej optymalizacji wykorzystywany przy rozwiązywaniu problemu komiwojażera. Algorytm ten nie służy do samego wyznaczania trasy, a jedynie do ulepszania jej. Najprostszą wersją tego algorytmu jest algorytm 2-optymalny.

→ Czytaj całość

Problem komiwojażera (ang. travelling salesman problem, w skrócie TSP) – problem obliczeniowy polegający na poszukiwaniu w grafie takiego cyklu, który zawiera wszystkie wierzchołki (każdy dokładnie raz) i ma jak najmniejszy koszt. Bardziej formalnie, problem komiwojażera polega na poszukiwaniu w grafie cyklu Hammiltona o najmniejszej wadze.

Problem ma liczne zastosowania w życiu codziennym. Najlepszym przykładem jest praca kuriera, który musi wyjechać z magazynu, zawieźć przesyłki w różne miejsca i wrócić do magazynu.

Nie jest znany efektywny (tj. działający w czasie co najwyżej wielomianowym) algorytm dający gwarancję znalezienia optymalnego rozwiązania problemu komiwojażera. Problem ten jest bowiem zaliczany do klasy problemów NP-trudnych. W wersji decyzyjnej (czy istnieje cykl o długości mniejszej od x) problem jest zaliczany do klasy problemów NP-zupełnych. W grafie pełnym mającym n wierzchołków liczba możliwych cykli Hammiltona wynosi aż (n-1)!/2. W praktyce sprawdzenie wszystkich możliwości jest zatem wykonalne tylko dla niewielkiej liczby wierzchołków.

→ Czytaj całość

Algorytm Bellmana-Forda – algorytm służący do wyznaczania najkrótszych ścieżek w grafie. Wyznacza najkrótsze ścieżki z jednego wierzchołka (zwanego wierzchołkiem źródłowym) do pozostałych wierzchołków. W odróżnieniu od algorytmu Dijkstry, algorytm Bellmana-Forda dopuszcza krawędzie o ujemnych wagach, nie mogą istnieć jednak ujemne cykle osiągalne z wierzchołka źródłowego. Algorytm może być również wykorzystywany do sprawdzania, czy w grafie występują ujemne cykle.

Algorytm występuje również pod nazwą algorytm Bellmana-Forda-Moore’a.

→ Czytaj całość
Polityka prywatnościKontakt