Ich verstehe nicht, wie die folgenden Komplexitäten herkommen.Zeit und Raum Komplexität der Breite erste Suche
espeacialy b (b^d-1) in der Zeitkomplexität
Zeitkomplexität: Gesamt taub. der erzeugten Knoten: 1 + b + b2 + ... + bd + b (b^d-1) = 0 (b^(d + 1)) Raumkomplexität: O (b^(d + 1))
wo b - maximal um den Faktor des Baumes d Suche Verzweigung - Tiefe der Least-Cost-Lösung
an der Wurzel, Sie b Knoten als die nächsten Elemente in dem Suchbaum erweitern werden. Diese, wenn keine die Lösung sind, erweitern wiederum b Knoten von jedem. Dies wird fortgesetzt, bis eine Lösung gefunden wird, die sich in der Tiefe d befindet.
Daraus folgt: O (b^d)
(Ich bin nicht sicher, wo Sie die 1 von bekam aber ...)
ist diese Komplexität für Raum und Zeit? –
Ja. Jeder Knoten muss sowohl gesucht (Zeit) als auch gespeichert (Raum) sein, bis eine Lösung gefunden wird. – Paul
hängt diese Komplexität auch von der Datenstruktur ab, die verwendet wird ??? –
Wenn der Algorithmus das Ziel Test Knoten anzuwenden waren Bei der Auswahl für die Erweiterung und nicht bei der Generierung würde die gesamte Ebene der Knoten in der Tiefe d erweitert werden, bevor das Ziel erkannt wird, und die Zeitkomplexität wäre 0 (b^(d + 1)).
Vereinfacht ausgedrückt verwenden wir in BFS eine Warteschlange, um den besuchten Pfad zu verfolgen. Jeder Scheitelpunkt in der Grafik wird höchstens einmal besucht. Daher ist die Warteschlangengröße maximal V. Daher die Raumkomplexität, wenn eine Funktion der Anzahl der Eckpunkte in dem Graph ist, d. H. O (| V |). Im Hinblick auf die Komplexität der Zeit führen wir eine Schleife durch, um alle Ecken im Graphen zu durchlaufen. Dies ist O (| V |). Außerdem müssen wir für jeden gefundenen Knoten all seine Nachbarn und damit die Anzahl der Kanten überprüfen, mit denen er verbunden ist. Das gibt uns O (| E |). Somit kann die Komplexität durch die Notation O (| V | + | E |) erklärt werden.
Woher haben Sie die Formeln? –
Eigentlich hat unser Dr. uns gerade in der lec gegeben –