Anwendungen wie Google Maps oder Navigationssysteme berechnen ständig kürzeste oder auch schnellste Wege. Es gibt bereits seit den 50er Jahren sehr effiziente Algorithmen, um diese Aufgabe zu lösen. Der zuverlässigste Weg kann durch die gleichen Verfahren gefunden werden – mit Hilfe eines kleinen Tricks.
Hierarchische Information ist allgegenwärtig: Stammbäume, Organigramme, Taxonomien oder auch Produktstrukturpläne. Eine gute graphische Darstellung ermöglicht einen schnellen Überblick. Allerdings ist die manuelle Erstellung einer schönen Zeichnung mit hohem Aufwand verbunden. Hier soll gezeigt werden, wie ein derartiger Vorgang automatisch durchgeführt werden kann.
Ich bin vor kurzem auf ein sogenanntes Legespiel gestoßen. Bei diesem Spiel müssen quadratische Karten so zu einem größeren Quadrat gelegt werden, dass die Bilder aller Karten an den Rändern zusammenpassen. Ich werde hier zeigen, wie komplex derartige Spiele sind, und einen Algorithmus zur Lösung vorstellen.