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

16

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?

algorithms graph-theory shortest-path

— The Unfun Cat
źródło

1

Najpopularniejszym algorytmem poszukiwania ścieżek na nieważonych grafach jest A *, z niewielką modyfikacją polegającą na tym, że więzi są zrywane bliżej końca. To da algorytm podobny do DFS, ponieważ najpierw wypróbuje najbardziej bezpośrednią trasę, a jeśli będzie to konieczne, będzie bąbelkować na zewnątrz.

— BlueRaja - Danny Pflughoeft

1

Spróbuj użyć DFS na niektórych (dobrze wybranych) wykresach; jeśli to naprawdę nie działa, powinieneś napotkać problemy. Przy okazji twoje pytanie brzmi, jakby działało na ważonych wykresach.

— Raphael

Tak, możesz to zrobić. Oto rozwiązanie

— Anmol Middha,

12

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:

kontrprzykład chciwej 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$

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.

— Raphael
źródło

Popraw mnie, jeśli się mylę, ale czy to oznacza, że DFS może znaleźć najkrótszą ścieżkę na dowolnym wykresie, ale zajmie to w tym czasie wykładniczy czas?

— Anmol Singh Jaggi

@AnmolSinghJaggi Nie. DFS zawsze znajduje tylko jedną ścieżkę.

— Raphael

10

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.

— Joe
źródło

3

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.

— użytkownik2407394
źródło

1

s

$s$

t

$t$

1

@ user2407394 Czy rzeczywiście zaimplementowałeś tę odmianę DFS raz i uruchomiłeś ją poprawnie dla umiarkowanie dużego wykresu? Wahałbym się nazywać tę odmianę DFS. Nazwałbym to poszukiwaniem głębokości, która wyczerpuje pierwszą ścieżkę.

— John L.

Wdrożyłem tego rodzaju podejście, które działa bardzo wolno. Zastanawiam się nad dodaniem mnemonizacji w celu poprawy wydajności.

— Mic

@ user2407394 wygląda na to, że to zadziała, ale jak sprawdzić, kiedy przestać, ponieważ nie będzie listy „odwiedzonych”, jeśli odznaczysz je wszystkie?

— Joe Black

0

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

— Vikkyhacks
źródło

-3

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

— Abereham Wodajia
źródło

2

Podaj więcej szczegółów. Nie potrafię powiedzieć, jaki algorytm próbujesz opisać w tym jednym zdaniu.

— David Richerby,

-3

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

— Anmol Middha
źródło

1

Przyjęta odpowiedź twierdzi, że nie jest to możliwe, co jest sprzeczne z twoim twierdzeniem. Czy możesz wyjaśnić, dlaczego Twoim zdaniem takie podejście działa? (lub wyjaśnij, dlaczego to podejście ogólnie działa)

— Dyskretna jaszczurka

Czy to nie jest po prostu powtarzanie odpowiedzi user2407394 , tylko z trudnym do zrozumienia kodem (nie zdefiniowałeś, co oznacza żadna z tych zmiennych i dla mnie to nie jest oczywiste) zamiast wyjaśnienia?

— David Richerby,

Tak, jest to implementacja odpowiedzi user2407394. Przepraszamy za niedogodności. Dodałem komentarze w kodzie. Możesz to teraz sprawdzić.

— Anmol Middha,