SPoGG
war hier der Erste, der nichts mit Spaß zu tun hatte. Er ist während der Arbeit an meiner Dissertation entstanden. In der Arbeit geht es - grob gesagt - um das Erzeugen guter Alternativ-Lösungen von mathematischen Optimierungs-Problemen.
Am Beispiel eines "Kürzeste-Wege-Problem"s zeigt SPoGG, daß der zweit-kürzeste oder dritt-kürzeste oder k.-kürzeste Weg (k>1) in der Regel keine echte Alternative zum kürzesten Weg darstellt. Im Gegensatz dazu sind Alternativ-Lösungen, die mit der "Penalty Methode" oder der "Mutual Penalty Methode" erzeugt sind, wesentlich sinnvoller. Durch die Visualisierung der Lösungen wird das einfach und intuitiv verständlich.
Einfaches, aber unpräzises Beispiel: Angenommen hinter den folgenden Bildern verstecke sich ein "fein-gestricktes" Straßen-Netz. Von jedem Pixel ausgehend gibt es eine Straße zu seinem oberen und zu seinem rechten Nachbar-Pixel. Die Straßen seien unterschiedlich schnell befahrbar, so dass man für jeweils einen Straßenabschnitt zwischen 0 und 1 Minute braucht. (Die Zeiten kann man den Grafiken aber nicht ansehen!) Wir wollen schnellstmöglich von links unten nach rechts oben fahren. Es handelt sich also eigentlich um ein "Schnellste-Wege-Problem".
 |
 |
 |
Im Bild links ist der schellste Weg dargestellt (grün). Alle anderen Straßen sind ausgeblendet.
Im mittleren Bild ist neben dem schnellsten Weg noch der zweit-schnellste Weg eingezeichnet (gelb). Die Straßen-Abschnitte, die von beiden Wegen benutzt werden, sind braun eingefärbt. Eigentlich ist fast der ganze Weg braun. Also unterscheiden sich die Wege nicht wirklich. Wem der "grüne" Weg nicht gefällt, weil man dort an keinem Bratwurst-Stand vorbeikommt, der wirklich echte Thüringer Rostbratwürste hat, dem wird sicher der "gelbe" Weg auch nicht gefallen. Dass es ausgerechnet auf dem kleinen Weg-Stück, das die beiden Wege unterscheidet, die gewünschten Würste gibt, ist unwahrscheinlich. Würde man anstelle des zweit-schnellsten Wegs den dritt-schnellsten oder gar fünfzigst-schnellsten Weg nehmen, dann sähe das in der Regel ähnlich aus: Irgendwo auf der ursprünglichen Strecke mal ganz kurz von der Straße, einmal um den nächstgelegenen Häuserblock und dann zurück auf die ursprüngliche Straße. Das ist nicht das, was wir Menschen unter einer Alternative verstehen.
Im Bild rechts ist zusätzlich zum schnellsten Weg (grün) ein Alternativ-Weg (gelb) dargestellt, der mit der Penalty Methode berechnet wurde.
Diese ermöglicht es (in diesem Kontext), einen schnellen Weg zu berechnen, der gezielt andere schnelle Teil-Abschnitte nutzt als der Vergleichsweg.
Die Straßen-Abschnitte, die von beiden Wegen benutzt werden, sind wieder braun eingefärbt.
Auch wenn der neue Weg in dem zugrundeliegenden Straßen-Netz ganze 2% länger dauert, so ist die Hoffnung berechtigt, daß es dort irgendwo die leckeren Bratwürste gibt, vielleicht sogar Süd-Thüringer.
Zumindest ist der größte Teil der beiden Wege unterschiedlich.
Wer wissen möchte, was da "wirklich" vor sich geht, sei an den Lehrstuhl für Mathematische Optimierung an der Friedrich-Schiller-Universität Jena oder hierher verwiesen.
Download
- SPoGG v4.0 (für Win32, [zip] 169kB)
1. März 2008