Warum ist die Komplexität von A * exponentiell im Speicher?

Question

Wikipedia sagt auf A * Komplexität der folgenden (link here):

Problematischer als die Zeit Komplexität ist A * s Speichernutzung. In der schlimmste Fall, muss auch eine exponentielle Anzahl von Knoten erinnern.

ich nicht das ist zu sehen, richtig, weil:

sagen, dass wir den Knoten A erkunden, mit Nachfolger B, C und D. Dann fügen wir B, C und D in der Liste des offenen Knoten, jeweils mit einem Verweis auf A, und wir bewegen A von den offenen Knoten zu den geschlossenen Knoten.

Wenn wir irgendwann einen anderen Pfad zu B finden (zB über Q), der besser ist als der Pfad durch A, dann muss nur B auf A umgestellt werden, um auf Q zu zeigen und seine Aktualität zu aktualisieren Kosten, g (und logisch f).

Wenn wir also in einem Knoten seinen Namen, seinen Namen und die g-, h- und f-Werte speichern, ist die maximale Anzahl der gespeicherten Knoten die tatsächliche Anzahl der Knoten im Diagramm es? Ich kann wirklich nicht verstehen, warum der Algorithmus zu irgendeinem Zeitpunkt eine Menge von Knoten im Speicher speichern müsste, die exponentiell zur Länge des optimalen (kürzesten) Pfads ist.

Könnte jemand bitte erklären?

---

bearbeiten Wie ich jetzt verstehe Ihre Antworten zu lesen, war ich von der falschen Sicht des Problems Argumentation. Ich nahm eine gegeben Grafik vorausgesetzt, während die exponentielle Komplexität bezieht sich auf eine konzeptionelle Grafik, die ausschließlich durch einen "Verzweigungsfaktor" definiert ist.

Answer 1

A * ist nur eine geführte Version von Breitensuche, die in Speicherkomplexität in Bezug auf die Länge der exponentiellen Lösung ist.

Wenn Sie eine Konstantenheuristik verwenden, wird A * zu einer normalen Breitensuche; uniforme Kostensuche um genau zu sein.

Bei Verwendung der optimalen Heuristik wird A * O(n) sowohl in Raum- als auch in Zeitkomplexität sein, wenn wir die Komplexität der heuristischen Berechnung selbst außer Acht lassen. Auch hier ist n die Länge des Lösungsweges.

Answer 2

Ich denke, dass die Exponentialität ins Spiel kommt, wenn Sie zurück zu Knoten B, um es zu erweitern, aber zurück zu Knoten C, um es zu erweitern, und dann zurück zu Knoten D. Jetzt müssen wir alle Kinder verfolgen der Knoten A, B, C und D.

Die Rückverfolgung basiert auf den Kosten der Kanten, um zum nächsten Knoten zu gehen, also ist dies eine reale Möglichkeit, aber ist der schlimmste Fall.

Wenn jeder Knoten genau 2 Kinder davon hat und jeder Knoten die gleichen Kosten hat, dann ist die Gleichung 2^n, wobei n die Tiefe der bisherigen Suche ist.

Zum Beispiel beginnen Sie mit Knoten 0. 0 hat 2 Kinder 00 und 01. 00 hat 2 Kinder 000 und 001. Im schlimmsten Fall mit einer Tiefe von 4 ist die Gleichung 2^4, wo 2 ist Anzahl der Kinder, die jeder Knoten hat und 4 ist die Tiefe der Suche.

Answer 3

Ich bin kein Experte, aber ich studierte den Wikipedia-Artikel für eine Weile und meine Erklärung wäre dies ein (Hoffnung ich es gut verstanden habe :)

Sag mal, wir haben eine 4x4-Matrix von Knoten.
A, B, C, D sind die Richtungen, die wir zu einer bestimmten Zeit nehmen können (Nord, Süd, Ost, West)
Der A * -Algorithmus beginnt mit der Suche.

A
Queue: B, C, D
AA
Queue: B, C, D, AB, AC, AD
AAA -> Ziel
Queue: B, C, D, AB, AC, AD, AAB, AAC, AAD
Das Ziel ist erreicht, aber es gibt noch andere Möglichkeiten zu berücksichtigen.

D
Queue: B, C, AB, AC, AD, AAB, AAC, AAD
DC
Queue: B, C, AB, AC, AD, AAB, AAC, AAD, DA, DB, DD
DCA
Queue: B, C, AB, AC, AD, AAB, AAC, AAD, DA, DB, DD, DCB, DCC, DCD
DCAB -> Ziel
Queue: B, C, AB, AC, AD, AAB, AAC, AAD, DA, DB, DD, DCB, DCC, DCD, DCAA, DCAC, DCAD
etc etc

Wie Sie sehen können, Für jeden ausgeführten Schritt werden drei weitere Knoten zur Warteschlange hinzugefügt.
Da A * nur azyklischen Pfaden folgt [1], ist die maximale Anzahl der Schritte pro Route 15.
Die maximale Anzahl der möglichen Routen ist in diesem Fall 3^15 oder Richtungen^Knoten.
Da jede Route 15 Schritte hat, sind die Worst-Case-Schritte 15 * 3^15.
Im absoluten Worst-Case ist jeder Schritt "falsch".
In diesem Fall befinden sich 3 * 15 * 3^15 Knoten in der Warteschlange, bevor die Antwort gefunden wird.
Die Anzahl der Knoten im ungünstigsten Fall, die im Speicher gehalten werden müssen, ist also eine Konstante, die der Anzahl der verfügbaren Knoten entspricht. Mit anderen Worten, die Speicherverwendung ist exponentiell zur Anzahl der Knoten.

[1] http://www.autonlab.org/tutorials/astar08.pdf gleiten 15