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 (Graphentheorie) in einem Graphen. Der Algorithmus kombiniert die wünschenswerten Eigenschaften von Tiefensuche (geringer Speicherverbrauch) und einer Variante der Breitensuche, dem A*-Algorithmus (Steuerung der Suche durch eine Heuristik).
Allgemeines
IDA* ist im Gegensatz zur normalen und der iterativen Tiefensuche eine informierte Suche, sie funktioniert ähnlich wie die iterative Tiefensuche, steuert die Suchtiefe jedoch mit Hilfe einer Heuristik.
Die iterative Tiefensuche besteht im Kern aus einer Schleife, in der die Suchtiefe (bei 1 beginnend) pro Schleifendurchlauf um den Wert 1 erhöht wird, bis eine Lösung gefunden wird. Es wird dabei immer die Tiefe vom Startknoten bis zum untersuchten Knoten gemessen. Wenn die Einheit für die Tiefe nicht mehr die Anzahl von Kanten, sondern eine andere Einheit (z. B. Weglänge in Kilometern) ist, muss man bei der Erhöhung der Tiefe einen Wert festlegen. Wählt man den Wert zu groß, findet man unter Umständen eine nicht optimale Lösung.
IDA* nimmt nicht die Tiefe vom Startknoten bis zum untersuchten Knoten für die Abbruchbedingung, sondern die Länge des gesamten Weges vom Startknoten bis zum Zielknoten. Da nur die Länge des Weges vom Startknoten bis zum aktuell untersuchten Knoten exakt bekannt ist, wird die Weglänge vom aktuell untersuchten Knoten bis zum Zielknoten mittels einer Heuristik geschätzt.
Die verwendete Heuristik muss eine Bedingung erfüllen: Die von ihr geschätzte Entfernung zum Ziel muss kleiner gleich der realen Entfernung zum Ziel sein. Bei einer geografischen Suche im Straßennetz stellt die Länge der Luftlinie offensichtlich eine gültige Heuristik dar.
Algorithmus (informell)
In IDA* startet die Schleife mit dem Wert der Heuristik für den Startknoten als Grenze für die Suchtiefe. Nach der Bedingung an die Heuristik kann es keinen kürzeren Weg vom Start zum Ziel geben. Die rekursive Suche innerhalb der Schleife muss nun entweder eine Lösung zurückliefern oder das Minimum der per Heuristik bestimmten Weglänge für alle Knoten, die als erste Knoten hinter der Grenze gefunden wurden. Dieses Minimum wird für den nächsten Schleifendurchlauf als Grenze für die Suchtiefe verwendet.
Wenn kein Weg vom Startknoten zum Zielknoten existiert, terminiert dieser Algorithmus nicht. Um die Endlosschleife zu verhindern, kann man die äußere Schleife begrenzen, zum Beispiel mit einer Grenze, die man durch Multiplikation des von der Heuristik berechneten Wertes für den Startknoten mit einem festen Faktor erhält (im folgenden Programmcode willkürlich auf 10 gesetzt).
Algorithmus (formal)
public Node<?> solve(Node root) {
Node solutionNode = null;
int bound = root.getOptimisticDistanceToSolution();
// 10 ist ein willkürlich gewählter Faktor zur Begrenzung der Suche
int maxBound = bound * 10;
while (solutionNode == null) {
SearchResult r = search(root, bound);
if (r.solutionNode != null) {
solutionNode = r.solutionNode;
}
if (r.t >= maxBound) {
return null;
}
bound = r.t;
}
return solutionNode;
}
SearchResult search(Node node, int bound) {
int f = node.getMovesDone() + node.getOptimisticDistanceToSolution();
if (f > bound) {
return new SearchResult(f);
}
if (node.isSolution()) {
return new SearchResult(node);
}
int min = Integer.MAX_VALUE;
List<Node> successors = node.nextNodes();
for (Node succ : successors) {
SearchResult r = search(succ, bound);
if (r.solutionNode != null) {
return r;
}
if (r.t < min) {
min = r.t;
}
}
return new SearchResult(min);
}
Eigenschaften
Speicherplatzverbrauch
Der Speicherplatzverbrauch ist proportional zu der Anzahl Kanten auf dem Weg vom Start- zum Zielknoten. Er ist damit deutlich kleiner als bei einer Breitensuche oder dem A*-Algorithmus, da die Suchfront und die Menge der bereits untersuchten Knoten nicht gespeichert werden muss.
Laufzeit
Im schlimmsten Fall werden alle möglichen Pfade zu allen möglichen Knoten betracht, die Laufzeit steigt dann exponentiell mit der Suchtiefe (gemessen in Anzahl Kanten). Bei einer guten Heuristik ist die Laufzeit jedoch deutlich geringer.
Literatur
- Korf, Richard (1985). Depth-first Iterative-Deepening: An Optimal Admissible Tree Search. Artificial Intelligence 27: 97–109. doi:10.1016/0004-3702(85)90084-0.