Wikipedia · einfach zusammengefasst · Stand
IDA*
IDA* (englisch iterative deepening A*) ist ein Begriff aus der Informatik. Er bezeichnet ein Verfahren zum Suchen des kürzesten Weges zwischen zwei Knoten …
Inhalt5 Abschnitte
Kernidee und Zweck
IDA* steht für „iterative deepening A*“ und ist ein Suchverfahren aus der Informatik. Es dient dazu, den kürzesten Weg zwischen zwei Knoten in einem Graphen zu finden. Ein Graph besteht aus Knoten und Kanten; Knoten sind die Punkte des Netzes, Kanten verbinden sie miteinander.
Der Algorithmus verbindet zwei Vorteile: Wie die Tiefensuche benötigt er wenig Speicherplatz, und wie der A*-Algorithmus nutzt er eine Heuristik, also eine Schätzung, um die Suche gezielt in Richtung Ziel zu steuern. Dadurch gehört IDA* zu den informierten Suchverfahren: Die Suche läuft nicht blind ab, sondern verwendet Zusatzwissen über die ungefähre Entfernung zum Ziel.
Heuristik und Suchgrenze
IDA* ähnelt der iterativen Tiefensuche. Bei der einfachen iterativen Tiefensuche wird die erlaubte Suchtiefe in einer Schleife schrittweise erhöht, meist beginnend bei 1. Dabei wird die Tiefe als Abstand vom Startknoten bis zum gerade untersuchten Knoten gemessen. Wenn die Tiefe nicht in Kanten gezählt wird, sondern zum Beispiel als Weglänge in Kilometern, muss festgelegt werden, um welchen Wert die Grenze jeweils erhöht wird. Ist dieser Wert zu groß, kann unter Umständen eine nicht optimale Lösung gefunden werden.
IDA* verwendet für die Abbruchbedingung nicht nur die bekannte Länge vom Startknoten bis zum aktuellen Knoten. Stattdessen betrachtet es die geschätzte Länge des gesamten Weges vom Startknoten bis zum Zielknoten. Die bisher zurückgelegte Strecke ist exakt bekannt; die noch fehlende Strecke vom aktuellen Knoten bis zum Ziel wird durch eine Heuristik geschätzt.
Diese Heuristik muss eine wichtige Bedingung erfüllen: Die geschätzte Entfernung zum Ziel muss kleiner oder gleich der wirklichen Entfernung zum Ziel sein. Sie darf also nicht überschätzen. Bei einer geografischen Suche in einem Straßennetz ist die Luftlinienentfernung eine gültige Heuristik, weil sie nicht länger als die tatsächliche Straßenstrecke sein kann.
Ablauf des Verfahrens
IDA* beginnt mit einer Grenze für die Suche. Diese Grenze ist der Heuristikwert des Startknotens, also die geschätzte Mindestentfernung vom Start zum Ziel. Wegen der Bedingung an die Heuristik kann es keinen kürzeren Weg geben als diesen geschätzten Wert.
Innerhalb der äußeren Schleife wird rekursiv gesucht. Die Suche hat zwei mögliche Ergebnisse: Sie findet eine Lösung, oder sie liefert das kleinste geschätzte Gesamtmaß für die Knoten zurück, die als erste außerhalb der aktuellen Grenze liegen. Dieses Minimum wird dann als neue Grenze für den nächsten Schleifendurchlauf verwendet. So wächst die Suchgrenze nicht um einen festen Betrag, sondern genau bis zur nächsten relevanten Grenze, die bei der vorherigen Suche entdeckt wurde.
Wenn zwischen Startknoten und Zielknoten kein Weg existiert, terminiert IDA* in der beschriebenen Grundform nicht. Um eine Endlosschleife zu verhindern, kann die äußere Schleife begrenzt werden. Im Artikel wird als Beispiel eine maximale Grenze verwendet, die durch Multiplikation des Heuristikwertes des Startknotens mit einem festen Faktor entsteht; im Programmcode ist dieser Faktor willkürlich auf 10 gesetzt.
Formale Berechnung
Im formalen Algorithmus startet solve mit dem Startknoten root. Zuerst wird bound auf root.getOptimisticDistanceToSolution() gesetzt, also auf die optimistische geschätzte Entfernung vom Start zur Lösung. Zusätzlich wird maxBound = bound * 10 gesetzt, um die Suche zu begrenzen.
Die Funktion search(node, bound) berechnet für jeden Knoten den Wert f = node.getMovesDone() + node.getOptimisticDistanceToSolution(). Dieser Wert besteht aus den bereits gemachten Schritten oder Kosten vom Start bis zum aktuellen Knoten plus der optimistisch geschätzten Entfernung vom aktuellen Knoten bis zur Lösung. Wenn f > bound ist, wird dieser Wert zurückgegeben, weil der Knoten außerhalb der aktuellen Suchgrenze liegt. Wenn node.isSolution() wahr ist, wird der Lösungsknoten zurückgegeben.
Andernfalls erzeugt der Algorithmus mit node.nextNodes() die Nachfolger des aktuellen Knotens und durchsucht sie rekursiv. Falls ein Nachfolger eine Lösung liefert, wird diese sofort zurückgegeben. Wenn keine Lösung gefunden wird, merkt sich der Algorithmus den kleinsten Wert r.t, der außerhalb der Grenze lag, und gibt dieses Minimum zurück. Dieses Minimum wird in solve zur neuen Suchgrenze.
Speicherbedarf und Laufzeit
Der Speicherplatzverbrauch von IDA* ist proportional zur Anzahl der Kanten auf dem Weg vom Startknoten zum Zielknoten. Das bedeutet: Gespeichert werden im Wesentlichen nur die Knoten entlang des aktuellen Suchpfades. Deshalb benötigt IDA* deutlich weniger Speicher als eine Breitensuche oder der A*-Algorithmus, weil weder die gesamte Suchfront noch die Menge aller bereits untersuchten Knoten gespeichert werden muss.
Die Laufzeit kann im schlechtesten Fall sehr groß werden. Dann werden alle möglichen Pfade zu allen möglichen Knoten betrachtet, und die Laufzeit wächst exponentiell mit der Suchtiefe, gemessen in der Anzahl der Kanten. Bei einer guten Heuristik ist die Laufzeit jedoch deutlich geringer, weil die Suche besser gesteuert wird und weniger unnötige Pfade verfolgt werden.
