Dlaczego DFS nie może być używany do znajdowania najkrótszych ścieżek na nieważonych wykresach?

Rozumiem, że użycie DFS „tak jak jest” nie znajdzie najkrótszej ścieżki na nieważonym wykresie.

Ale dlaczego poprawianie DFS, aby umożliwić mu znajdowanie najkrótszych ścieżek na nieważonych wykresach, jest tak beznadziejną perspektywą? Wszystkie teksty na ten temat po prostu stwierdzają, że nie można tego zrobić. Nie jestem przekonany (sam tego nie próbowałem).

Czy znasz jakieś modyfikacje, które pozwolą DFS znaleźć najkrótsze ścieżki na nieważonych wykresach? Jeśli nie, co takiego jest w algorytmie, który sprawia, że ​​jest to tak trudne?

Jedynym elementem, który poprawiasz w pierwszej kolejności, jest kolejność, w jakiej badane są dzieci. Normalna wersja przebiega w dowolnej kolejności, tzn. W kolejności, w której dzieci są przechowywane.

Jedyną możliwą alternatywą (w kierunku najkrótszych ścieżek), jaką mogę wymyślić, jest chciwe podejście, polegające na patrzeniu na dzieci w kolejności ich odległości od obecnego węzła (od małego do dużego). Łatwo jest zbudować kontrprzykład dla tej reguły:

^{[ źródło ]}

To nie jest dowód na to, że nie istnieje strategia wyboru następnego dziecka do zbadania, która sprawiłaby, że DFS znalazłoby najkrótsze ścieżki.

$(s,t)$$(s,a)$$a$$(a,b)$$(s,t)$

$c$$c-1$

1. Tak długo, jak reguła jest deterministyczna. Jeśli tak nie jest, to oczywiście nie zawsze może znaleźć najkrótsze ścieżki.

Szerokość - pierwsze wyszukiwanie to algorytm, który znajdzie najkrótsze ścieżki na nieważonym wykresie.

Prostą modyfikację można uzyskać z DFS do algorytmu, który znajdzie najkrótsze ścieżki na nieważonym wykresie. Zasadniczo zamieniasz stos używany przez DFS na kolejkę. Jednak wynikowy algorytm nie jest już nazywany DFS. Zamiast tego zaimplementujesz szerokie wyszukiwanie.

Powyższy akapit daje prawidłową intuicję, ale nieco upraszcza sytuację. Łatwo jest napisać kod, dla którego prosta zamiana daje implementację szerokości pierwszego wyszukiwania, ale łatwo jest również napisać kod, który na początku wygląda na poprawną implementację, ale tak naprawdę nie jest. Możesz znaleźć powiązane pytanie cs.SE na BFS vs DFS tutaj . Tutaj znajdziesz fajny pseudo-kod.

Możesz!!!

Oznacz węzły jako odwiedzone podczas wchodzenia na głębokość i usuń zaznaczenie podczas powrotu, gdy wracasz, gdy znajdziesz inną gałąź (y), powtarzaj to samo.

Zapisz koszt / ścieżkę dla wszystkich możliwych wyszukiwań, w których znalazłeś węzeł docelowy, porównaj wszystkie takie koszty / ścieżkę i wybierz najkrótszy.

Dużym problemem (i mam na myśli DUŻY) w tym podejściu jest to, że odwiedzasz ten sam węzeł wiele razy, co sprawia, że ​​dfs jest oczywistym złym wyborem dla algorytmu najkrótszej ścieżki.

BFS ma fajną właściwość, że sprawdzi wszystkie krawędzie od nasady i utrzyma minimalną odległość od nasady do innych węzłów, ale dfs po prostu przeskakuje do pierwszego sąsiedniego węzła i idzie w głąb. Możesz zmodyfikować DFS, aby uzyskać najkrótszą ścieżkę, ale skończysz tylko na algorytmie o większej złożoności czasowej lub skończysz na tym samym działaniu, co BFS

Za pomocą DFS można znaleźć ścieżkę między dwoma wierzchołkami z minimalną liczbą krawędzi. możemy zastosować podejście poziomu

Możesz

po prostu przejrzyj wykres w sposób dfs i sprawdź

if(distance[dest] > distance[source]+cost[source_to_destination]){
    distance[dest] = distance[source] + cost[source_to_destination]);
}

Oto link do pełnego rozwiązania