Was ist der Sinn von IDA * gegen A * -Algorithmus?
Ich verstehe nicht, wie IDA* Speicherplatz spart.
Wie ich verstehe IDA* ist A* mit iterativer Vertiefung.
Was ist der Unterschied zwischen der Menge an Speicher A* verwendet vs IDA* .
Würde sich die letzte Iteration von IDA* nicht genau wie A* verhalten und die gleiche Menge an Speicher verwenden. Wenn ich IDA* nachverfolge, merke ich, dass es sich auch an eine Prioritätswarteschlange der Knoten erinnern muss, die unter dem Schwellenwert f(n) liegen.
Ich verstehe, dass ID-Depth first search bei der Tiefensuche hilft, indem es zuerst eine Breite wie die Suche macht, ohne sich jeden einzelnen Knoten merken zu müssen. Aber ich dachte, dass A* sich schon vorher wie die Tiefe verhält, da darin einige Unterbäume ignoriert werden. Wie macht die iterative Vertiefung weniger Speicherplatz?
Eine weitere Frage ist die Tiefe der ersten Suche mit iterativer Vertiefung, die es Ihnen ermöglicht, den kürzesten Pfad zu finden, indem Sie ihn zuerst als Breite behandeln lassen. Aber A* gibt bereits den optimalen kürzesten Pfad zurück (da die Heuristik zulässig ist). Wie hilft iterative Vertiefung? Ich denke, IDA * 's letzte Iteration ist identisch mit A* .
1 Antwort
In IDA* , im Gegensatz zu A* , müssen Sie keine vorläufigen Knoten aufbewahren, die Sie besuchen möchten. Daher ist Ihr Speicherverbrauch nur für die lokalen Variablen der rekursiven Funktion reserviert.
Obwohl dieser Algorithmus weniger Speicher verbraucht, hat er seine eigenen Fehler:
Im Gegensatz zu A * verwendet IDA * keine dynamische Programmierung und findet daher oft mehrere Male dieselben Knoten. (IDA * In Wiki)
Die heuristische Funktion muss noch für Ihren Fall angegeben werden, damit nicht der gesamte Graph gescannt werden kann. Der Scan-Speicher, der in jedem Moment benötigt wird, ist jedoch nur der Pfad, den Sie gerade scannen, ohne die umgebenden Knoten.
Hier ist eine Demo des für jeden Algorithmus benötigten Speichers:
Im Algorithmus A* müssen alle Knoten und ihre umgebenden Knoten in die Liste "muss besucht werden" aufgenommen werden, während Sie in IDA* die nächsten Knoten "träge" erhalten, wenn Sie den Vorschauknoten erreichen Sie müssen es nicht in einen zusätzlichen Satz aufnehmen.
Wie in den Kommentaren erwähnt, ist IDA* im Grunde nur IDDFS mit Heuristiken :
Tags und Links algorithm a-star path-finding