Routenplaner

Routenplaner gehören heute zum Alltag: Viele Autos haben sie bereits eingebaut, wer kein Navi im Fahrzeug hat, lässt sich den günstigsten Weg zu seinem Ziel oft auf dem heimischen PC ermitteln und druckt ihn aus. Auch auf den Handys ist heute mehr und mehr ein Routenfindungsprogramm verfügbar.

Wie bestimmt der Computer eigentlich die kürzeste Verbindung zwischen zwei Orten? Und das erst noch so schnell?

Lernziele:

• Sie können den Begriff Algorithmus erklären.
• Sie kennen wesentliche Schritte auf dem Weg zur Formulierung eines Algorithmus.
• Sie haben den Dijkstra-Algorithmus nachvollzogen.
• Sie haben den Begriff der Komplexität eines Algorithmus verstanden.
• Sie haben die Komplexität des Dijkstra-Algorithmus abgeschätzt.
• Sie können auch für andere Beispiel-Probleme die Komplexität abschätzen

Unterlagen:

1. Die kürzeste Strecke auf einer Landkarte finden kann man auch mit „Roher Gewalt“ (englisch „brute force“): man probiert einfach alle Wege durch. Bei einer grösseren Anzahl möglicher Strassenstücke ist dies aber schnell einmal kaum mehr durchführbar. Wie können wir besser vorgehen? Zuerst einmal dadurch, dass wir die Problemstellung soweit es geht abstrahieren und uns nur noch um die für unser Problem wichtigen Informationen kümmern. routenplaner_1.pdf

2. Oft kann man die verschiedenen Facetten eines Problems auf die gleichen Grundelemente zurückführen. Dadurch wird einerseits das Problem übersichtlicher und andererseits benötigt man weniger Lösungsansätze. Für einen neuen Lösungsansatz können wir von der Natur lernen: Ein Stamm Ameisen hat auf der Suche nach Futter ein ähnliches Problem: Eine Kundschafterin findet ein grosses Stück Nahrung. Welchen Weg sollen die Arbeiterinnen nehmen, um die Beute am schnellsten zu sichern? Der Ameisen-Algorithmus zeigt uns eine Lösung, die besser ist als „Rohe Gewalt“! routenplaner_2.pdf

3. Der Ameisen-Algorithmus lässt sich so formulieren, dass ihn ein Computer ausführen kann. Formuliert hat den Algorithmus ein Informatikprofessor aus Holland: Edsger Dijkstra. Den Algorithmus verstehen können aber auch wir!

4. Wir haben nun ein Verfahren, mit dem wir uns relativ schnell alle kürzesten Verbindungen von einem Startpunkt aus zu allen Nachbarstädten herausfinden können. Mit diesem Verfahren können wir nun in einem konkreten Stadtplan die Frage nach dem kürzesten Weg zwischen zwei Punkten durch Vorbereitung sehr vereinfachen.

5. Das Lösungsverfahren kann sehr einfach erweitert werden, so dass es auch dann noch funktioniert, wenn es Einbahnstrassen gibt.

6. Mit ähnlichen Lösungsverfahren können in der Informatik viele weitere Probleme gelöst werden. Aber welches Verfahren ist bei einer grossen Anzahl Städte das beste?

• Testaufgabe 1: Wir wollen eine Fläche der Länge n und der Breite 3n schachbrettartig mit Bäumen im Abstand 1 bepflanzen. Ist die Aufgabe P oder NP? (Lösung)

• Testaufgabe 2: Wie kann man einen Routenplaner entwickeln, der Autobahnen und Landstrassen unterschieden kann? (Lösung)

Animation zum Dijkstra-Algorithmus

• Dijkstra-Demo-Applet (inkl. deutsche Erklärung), dijkstravis.jar herunterladen und doppelklicken (für Java-Freaks: source code von dijkstravis )
• einfaches Dijkstra-Demo-Applet (online)
• Dijkstra-Algorithmus visualisiert (Windows executable) runterladen, entzippen, mit doppelklick starten

---

Spielwiese

• Türme von Hanoi
• LightBot Ein nettes und gegen Ende recht kniffliges Spiel, an dem sich die Denkweise eines Programmierers üben lässt
• LightBot2.0 Inkl. Tutorial und weiteren Levels