Datenbäume

Neben den Listen gibt es eine weitere wichtige Datenstruktur, den Baum. Beinahe jeder verwendet heutzutage Navigationsgeräte. Diese machen intern nichts anderes als auf einem Graphen, welcher aus Orten und Straßen besteht nach einem Weg zu einem Punkt zu suchen.

 

Bei einer Karte von Deutschland sind große Städte wie Berlin, Hamburg oder Frankfurt solche Orte die man als Ausgangspunkt oder auch als Ziel wählen könnte, die dazwischenliegenden Straßen wären die Kanten entlang derer man dorthin gelangt. Wendet man nun einen Suchalgorithmus auf diesen Graph an, wird er irgendwann das Ziel finden und kann den gegangenen Weg zurückgeben, dieser ist dann die Route die zum Ziel führt. In diesem Kapitel werden die Breitensuche und die Tiefensuche vorgestellt, die auf solche Graphen angewendet werden können.

 

Wir möchten uns nun von Darmstadt aus nach Gießen navigieren. Wir wenden eine Breitensuche auf den Anfangsknoten Darmstadt an. Der Algorithmus wird zunächst die benachbarten Städte, wie Wiesbaden oder Hanau besuchen und prüfen ob sie die geforderten sind, dann werden die wiederrum ihnen nächstgelegenen besucht. Dies wird fortgesetzt bis Gießen gefunden ist.

 

Bei dem Blick auf eine Karte erscheint dieses Vorgehen nicht sinnvoll, da zum Beispiel Hanau nicht in der Richtung der direkten Verbindungslinie liegt und somit in jeden Fall einen Umweg darstellt. Damit wir zu dieser Aussage aber gelangen können, dass dies ein Umweg ist, benötigen wir eine Information über die Art des Problems. Wir kennen die Position Gießens relativ zu Darmstadt und können daher bereits Knoten ausschließen, bzw. geringer gewichten.

 

Nachdem die Breitensuche für dieses Problem nicht optimal ist, versuchen Sie die Tiefensuche. Die Tiefensuche verfolgt einen Pfad bis zu seinem Ende, bis der nächste beschritten wird. Ein möglicher Pfad, der durch die Tiefensuche beschritten wird, wäre Darmstadt, Wiesbaden, Gießen. Dieser läge nahe dem optimalen Pfad Darmstadt, Frankfurt, Gießen. Das Problem ist, dass dies nicht zwingend der erste zu beschreitende Pfad sein muss. Es könnte genauso gut Darmstadt, Hanau, Gießen besucht werden. In letzterem Fall wird NICHT die optimale Route gefunden, aber das Ziel wird trotzdem gefunden. Ein Problem der Tiefensuche ist, dass sie nicht vollständig arbeitet. Angenommen es gäbe einen Pfad innerhalb des Straßennetzes in Deutschland der unendlich lang, bzw. tief wäre, würde die Tiefensuche nie das Ziel erreichen oder nur nach sehr sehr langer Rechenzeit. Dies ist kein wünschenswerter Zustand.

 

Für den Fall einer Wegfindung in einem Netz aus Knoten scheint weder die Tiefensuche noch die Breitensuche geeignet zu sein. Für die Behandlung solcher Probleme eignen sich heuristische Algorithmen. Sie zeichnen sich dadurch aus, dass sie weiterführende Informationen über das Problem verarbeiten können. Ein Beispiel hierfür wäre der A*-Algorithmus. Dieser Algorithmus bezieht in die Suche noch die geschätzte Distanz zum Ziel mit ein und kann dadurch den optimalen Pfad schneller finden.

 

Informieren sie sich vor der Übung über die vorgestellten Algorithmen (Binäre Suche, Breitensuche und Tiefensuche) und überlegen Sie sich ihre Funktion. Sollten Sie weiterführendes Interesse haben, können Sie auch gerne den A*-Algorithmus suchen und sich zu ihm informieren, diese wird jedoch nicht im Rahmen der Übung behandelt.