Routenplaner gehören heute zum Alltag: Viele Autos haben sie bereits eingebaut, wer keinen 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 (inkl. Anforderungen).
  • Sie kennen wesentliche Schritte auf dem Weg zur Formulierung eines Algorithmus.
  • Sie haben den Dijkstra-Algorithmus nachvollzogen.
  • Sie können Struktogramme lesen und einfache Algorithmen in Form eines Struktogramms formulieren.
  • 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 einfache Beispiel-Probleme/Algorithmen die Komplexität abschätzen und in O-Notation angeben.
  • Sie können grob beschreiben, was man unter dem P-NP-Problem versteht.

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 /*(Passwort: Reduktion)*/
  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! routenplaner_3.pdf /*(Passwort: Dijkstra)*/
  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. routenplaner_4.pdf /*(Passwort: Algorithmus)*/
  5. Das Lösungsverfahren kann sehr einfach erweitert werden, so dass es auch dann noch funktioniert, wenn es Einbahnstrassen gibt. routenplaner_5.pdf /* (Passwort: Entfernung) */
  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? routenplaner_6.pdf /*(Passwort: Graphen)*/

Animation zum Dijkstra-Algorithmus

  • DijkstraViz.zip Ausführlich, inkl. deutsche Erklärung; Entpacken, dann dijkstravis.jar doppelklicken (für Java-Freaks: source code von dijkstravis )
  • Animal-2.3.21.jar Viele wichtige Algorithmen; herunterladen und doppelklicken, dann unter „File“, „Repository“, Dijkstra Algorithm auswählen.

Struktogramme

Laufzeitabschätzung und O-Notation