Kürzester Pfad: DFS, BFS-oder beides?

Ich weiß das BFS allein können den kürzesten Weg zu finden in einem ungewichteten graph, aber ich lese auch auf ein paar Seiten, wo Leute behaupten, die entweder BFS oder DFS konnte dies tun. Ich wollte nur bestätigen, dass diese waren wohl Fehler, und dass nur kann das BFS dazu (ich war nicht völlig überzeugt, auch nachdem eine schnelle google-Suche). Wenn ich bin falsch, kann mir bitte jemand erklären, wie es möglich ist, für die DFS geben kürzesten Weg.

InformationsquelleAutor user1136342 | 2013-02-09
  1. 13

    DFS nicht zwangsläufig kürzesten Wege in einem ungerichteten Graphen. BFS wäre die richtige Wahl hier.

    Als Beispiel wird ein graph gebildet, indem die Ecken des Dreiecks verbinden. Wenn Sie versuchen zu finden, den kürzesten Pfad von einem Knoten zu einem anderen mit der DFS, dann werden Sie die falsche Antwort erhalten, es sei denn, Sie befolgen Sie die Kante, die direkt verbindet die start-und Ziel-Knoten.

    Hoffe, das hilft!

    InformationsquelleAutor templatetypedef
  2. 3

    Iterative deepening search (IDS), die besteht aus vielen Runden depth-limited-search (im Grunde DFS, aber aufhören zu suchen, wenn Sie erreicht haben, eine Tiefe Grenze d), die schrittweise Erhöhung der Tiefe von 1, finden Sie den kürzesten Weg in einem ungewichteten graph.

    //Iterative deepening search
//isGoal is a function that checks whether the current node is the goal
function ids(graph, start, isGoal) { 
    maxDepth = 1
    do {
        found = dls(graph, start, isGoal, maxDepth, 0)
        //Clear the status whether a node has been visited
        graph.clearVisitedMarker();
        //Increase maximum depth
        depth = depth + 1

    //You can slightly modify the dls() function to return whether there is a
    //node beyond max depth, in case the graph doesn't have goal node.
    } while (found == null)

    return found
}

//Depth-limited search
//isGoal is a function that checks whether the current node is the goal
function dls(graph, currentNode, isGoal, maxDepth, currentDepth) {
    if (graph.visited(currentNode)) {
        return null
    }
    graph.setVisited(currentNode)

    if (isGoal(currentNode)) {
        return currentNode
    }

    //Stop searching when exceed max depth
    //This is the only difference from DFS
    if (currentDepth >= maxDepth) {
        return null
    }

    for (adjNode in graph.getAdjacent(currentNode)) {
        found = dls(graph, adjNode, goal, maxDepth, currentDepth + 1)
        if (found != null) {
            return found
        }
    }

    return null
}

    Es funktioniert, da Sie schrittweise Erhöhung der zulässigen Abstand von der start-Knoten: ein Knoten, der Entfernung, die ein + 1 nicht ausgeschöpft werden, bevor ein Knoten, dessen Abstand ein, aufgrund der Begrenzung auf die Tiefe.

    Einem gemeinsamen Anliegen ist der Knoten mit Distanz, die ein re-besucht (d - a + 1) - mal, wobei d die Tiefe der kürzeste Weg zum Ziel. Es hängt von der graph-oder Suchbaum, wenn wir darüber reden wollen Leistung. Auf einem Suchbaum mit großen branching-Faktor, der Knoten erzeugt in der Tiefe d wird der dominierende Begriff, so dass es nicht viel von einem problem mit Neubetrachtung. BFS unbrauchbar für diesen Fall aufgrund der exponentiellen Platzbedarf, aber IDS verwenden nur polynomial-space.

    InformationsquelleAutor nhahtdh
  3. 1

    Einer Perspektive zu verstehen: BFS in einem graph ohne Gewicht und die Richtung ist die gleiche wie Dijkstra(Gewicht=1, eine Richtung), so zu verstehen, warum Dijkstra ist richtig helfen könnte. Weitere details werden Hinzugefügt, wenn ich es geschafft haben.

    InformationsquelleAutor Saber Serker
  4. -1

    Beiden BFS und DFS geben wird, den kürzesten Weg von A nach B, wenn Sie umgesetzt werden.

    Denken wir den ganzen Graphen als einen Baum. Im Grunde, BFS wird führen Sie jede Ebene des Baumes und finden Sie heraus, den Weg durch das Durchlaufen aller Stufen. Im Gegensatz dazu, DFS läuft auf jeder Blatt-Knoten und den Pfad beim durchqueren Knoten entlang dieses Pfades. Beide sind mit Abgas-Pfad zu finden-Suche, so dass beide garantieren den kürzesten Weg zu finden, wieder, wenn Sie implementiert diese algorithmen korrekt.

    Die vor-und Nachteile für die Verwendung von BFS und DFS ist der folgende:

    BFS, verwendet mehr Speicher, durchqueren alle Knoten

    DFS, benötigt weniger Speicher, ist vielleicht etwas schneller, wenn Sie Glück haben, um wählen Sie die Blatt-Knoten Pfad enthält, der Knoten, der Sie interessiert.(Nicht unbedingt müssen durch alle Knoten).

    • Aber Sie haben, um sicherzustellen, dass der Pfad zu diesem Blatt ist das kürzeste eine nicht Sie?
    • Sie reden nur über die Bäume, richtig? Denn Ihre Argumentation ist nicht das richtige für Graphen
    InformationsquelleAutor Alan Dong
Schreibe einen Kommentar