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?
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?
(Resultat auf neue Seite im persönlichen Wiki schreiben):