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.

 

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

 

Bei dem Blick auf eine Karte erscheint dieses Vorgehen nicht sinnvoll, da zum Beispiel Ingolstadt 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 Berlins relativ zu München 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. Damit die Tiefensuche angewendet werden kann, muss der Graph zunächst traversiert werden, d.h. in Baumstruktur gebracht werden. Ein möglicher Pfad wäre, München, Nürnberg, Dresden, Berlin. Dieser läge nahe dem optimalen Pfad. Das Problem ist, dass dies nicht zwingend der erste zu beschreitende Pfad sein muss. Es könnte genauso gut München, Ingolstadt, Frankfurt, Düsseldorf, Hamburg, Berlin entstehen. 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 hoher 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 die A*-Search, dieser Algorithmus bezieht in die Suche noch die geschätzte Distanz zum Ziel mit ein und kann dadurch den optimalen Pfad finden.

 

Informieren sie sich vor der Übung über die vorgestellten Algorithmen und überlegen Sie sich ihre Funktion. Sollten sie weiterführendes Interesse haben, können Sie auch gerne die A*-Search suchen und sich zu Ihr informieren, diese wird jedoch nicht im Rahmen der Übung behandelt.