Warum kann DFS nicht verwendet werden, um kürzeste Pfade in ungewichteten Diagrammen zu finden?

16

Ich verstehe, dass die Verwendung von DFS "wie sie ist" keinen kürzesten Weg in einem ungewichteten Diagramm findet.

Aber warum ist das Optimieren von DFS, um kürzeste Wege in ungewichteten Diagrammen zu finden, eine so hoffnungslose Perspektive? Alle Texte zum Thema geben lediglich an, dass dies nicht möglich ist. Ich bin nicht überzeugt (ohne es selbst ausprobiert zu haben).

Kennen Sie Änderungen, mit denen DFS in ungewichteten Diagrammen die kürzesten Wege finden kann? Wenn nicht, was macht den Algorithmus so schwierig?

Die unfun Katze
quelle
1
Der gebräuchlichste Pfadfindungsalgorithmus für ungewichtete Graphen ist A *, mit der geringfügigen Änderung, dass die Bindungen zum Ziel hin unterbrochen werden. Dies ergibt einen Algorithmus, der DFS ähnelt, indem er zuerst die direkteste Route versucht und nur dann nach außen sprudelt, wenn dies erforderlich ist.
BlueRaja - Danny Pflughoeft
1
Versuchen Sie, DFS in einigen (gut ausgewählten) Diagrammen zu verwenden. Wenn es wirklich nicht funktioniert, sollten Sie auf Probleme stoßen. Übrigens liest sich Ihre Frage so, als ob sie auf gewichteten Graphen funktioniert hätte.
Raphael
ja, du kannst es schaffen Hier ist die Lösung
Anmol Middha

Antworten:

12

Das einzige Element der Tiefensuche, das Sie optimieren, ist die Reihenfolge, in der Kinder untersucht werden. Die normale Version läuft in beliebiger Reihenfolge ab, dh in der Reihenfolge, in der die Kinder gespeichert sind.

Die einzig mögliche Alternative (in Richtung kürzester Wege) ist ein gieriger Ansatz, bei dem Kinder in der Reihenfolge ihres Abstands vom aktuellen Knoten (von klein nach groß) betrachtet werden. Es ist einfach, ein Gegenbeispiel für diese Regel zu erstellen:

Gegenbeispiel für gierige Regel
[ Quelle ]

Dies ist kein Beweis dafür, dass es keine Strategie für die Auswahl des nächsten zu untersuchenden Kindes gibt, die es der DFS ermöglicht, kürzeste Wege zu finden.

Unabhängig von der Regel¹ können Sie jedoch Diagramme erstellen, bei denen DFS gleich beim ersten Knoten einen langen Umweg einlegt, genau wie bei der gierigen Regel. Weisen Sie die Kantengewichte und ( s , a ) so zu, dass die Regel einen ersten Besuch wählt , und weisen Sie ( a , b ) ein Gewicht zu, das größer als das von ist(s,t)(s,a)a(a,b)(s,t)

cc1


  1. Solange die Regel deterministisch ist. Wenn es nicht ist, kann es eindeutig nicht immer kürzeste Wege finden.
Raphael
quelle
Korrigieren Sie mich, wenn ich falsch liege. Bedeutet dies, dass DFS in jedem Diagramm den kürzesten Pfad finden kann, dabei aber exponentielle Zeit benötigt?
Anmol Singh Jaggi
@AnmolSinghJaggi Nein. DFS findet immer nur einen Pfad.
Raphael
10

Die Breitensuche ist der Algorithmus, der die kürzesten Wege in einem ungewichteten Graphen findet.

Es gibt eine einfache Optimierung, um von DFS zu einem Algorithmus zu gelangen, der die kürzesten Wege in einem ungewichteten Graphen findet. Im Wesentlichen ersetzen Sie den von DFS verwendeten Stapel durch eine Warteschlange. Der resultierende Algorithmus heißt jedoch nicht mehr DFS. Stattdessen haben Sie die Breitensuche implementiert.

Der obige Absatz gibt die richtige Intuition wieder, vereinfacht jedoch die Situation ein wenig. Es ist einfach, Code zu schreiben, für den der einfache Tausch eine Implementierung der Breitensuche ergibt, aber es ist auch einfach, Code zu schreiben, der auf den ersten Blick wie eine korrekte Implementierung aussieht, dies jedoch nicht ist. Eine verwandte cs.SE-Frage zu BFS vs DFS finden Sie hier . Sie können hier einen netten Pseudocode finden.

Joe
quelle
2

Du kannst!!!

Markieren Sie die Knoten als besucht, während Sie in die Tiefe gehen, und entfernen Sie die Markierung, während Sie zurückkehren.

Speichern Sie Kosten / Pfad für alle möglichen Suchen, bei denen Sie den Zielknoten gefunden haben, vergleichen Sie alle Kosten / Pfad und wählen Sie den kürzesten aus.

Das große (und ich meine GROSSE) Problem bei diesem Ansatz ist, dass Sie denselben Knoten mehrmals besuchen würden, was dfs zu einer offensichtlichen schlechten Wahl für den Algorithmus mit dem kürzesten Pfad macht.

user2407394
quelle
1
st
1
@ user2407394 Haben Sie diese Variante von DFS tatsächlich einmal implementiert und für ein mäßig großes Diagramm korrekt ausgeführt? Ich würde zögern, diese Variante als DFS zu bezeichnen. Ich würde es Tiefensuche nennen.
John L.
Ich habe einen solchen Ansatz implementiert, der sehr langsam funktioniert. Ich denke über das Hinzufügen von Mnemonization nach, um die Leistung zu verbessern.
Mic
0

BFS hat eine nette Eigenschaft, dass es alle Kanten von der Wurzel überprüft und den Abstand von der Wurzel zu den anderen Knoten so gering wie möglich hält, aber dfs springt einfach zum ersten benachbarten Knoten und geht in die Tiefe. Sie KÖNNEN DFS ändern, um den kürzesten Pfad zu ermitteln, aber Sie werden nur in einem Algorithmus mit höherer zeitlicher Komplexität landen oder dasselbe tun, was BFS tut

vikkyhacks
quelle
-3

Mit DFS ist es möglich, den Pfad zwischen zwei Eckpunkten mit der Mindestanzahl von Kanten zu finden. Wir können Level-Ansatz anwenden

Abereham Wodajia
quelle
2
Bitte machen Sie nähere Angaben. Ich kann nicht sagen, welchen Algorithmus Sie in diesem einzigen Satz beschreiben wollen.
David Richerby
-3

Du kannst

Durchqueren Sie den Graphen auf dfs-Weise und überprüfen Sie ihn

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

Hier ist der Link für die vollständige Lösung

Anmol Middha
quelle
1
Die akzeptierte Antwort behauptet, dies sei nicht möglich, was Ihrem Anspruch widerspricht. Kannst du erklären, warum du denkst, dass dieser Ansatz trotzdem funktioniert? (oder erklären, warum dieser Ansatz im Allgemeinen funktioniert)
Diskrete Eidechse
Wiederholt dies nicht einfach die Antwort von user2407394 , nur mit schwer verständlichem Code (Sie haben nicht definiert, was eine dieser Variablen bedeutet, und es ist für mich nicht offensichtlich) anstatt einer Erklärung?
David Richerby
Ja, es ist die Implementierung der Antwort von user2407394. Entschuldigung für die Unannehmlichkeiten. Ich habe Kommentare im Code hinzugefügt. Sie können es jetzt überprüfen.
Anmol Middha