Schmigalla
Mit diesem Programm kann man Schmigalla’s Dreiecksverfahren vom Computer ausführen lassen. Verfügbar ist es via Java WebStart. Wenigstens beim ersten Start wird sich die Laufzeitumgebung beschweren, ich sei nicht vertrauenswürdig. Das muss dann jeder für sich selbst entscheiden, aber wenn man das Programm benutzen möchte muss man mir vertrauen… Eine weitere Voraussetzung ist Java 1.5 oder neuer.
Benutzung
Der Startbildschirm sieht so aus:
Eingabe der Intensitätsmatrix
In diesem können die Transportintensitäten zwischen den einzelnen Anlagen definiert werden, indem man diese in den Teil der Matrix oberhalb der Hauptdiagonalen einträgt. Der Rest der Matrix ist implizit Null. Mit dem “+” unten links kann man neue Zeilen / Spalten hinzufügen. Diese werden im Moment mit Zufallswerten gefüllt. Bitte beachten. Dies ist nur ein Relikt aus der Entwicklung, welches mir beim “schnell mal testen” geholfen hat. Bei Bedarf kann ich das gerene noch abstellen. Mit “laden” kann man CSV – Dateien direkt einlesen. Diese können z.B. aus Excel exportiert werden. Ein Klick auf “los” startet die Berechnung:
Die gefundenen Lösungen
Hier werden sämtliche gefundenen Lösungen vorgehalten. Die erste Lösung ist jene, welche der klassische Schmigalla liefert. Danach startet eine wetere Suche nach verfeinerungen (siehe Funktionsweise). Alle Lösungen welche wenigstens nicht schlechter sind als die beste bisher bekannte Lösung werden in der Liste links vermerkt und können in Ruhe studiert werden.Der Algorithmus hat terminiert, wenn unter dem Reiter “Fortschritt” nichts mehr passiert. Für realistische Problemgrößen wird man so lange allerdings nicht warten wollen. Aber mal über Mittag laufen lassen kann sich schon lohnen.
Dateiimport
Das Programm kann CSV – Dateien importieren. Diese müssen einigen Regeln genügen:
- als Trenner zwischen den Werten sollte ein Komma, kein Semikolon stehen
- der Trenner zwischen Vor- und Nachkommaanteil einer Zahl muss ein Punkt, kein Komma sein
- auf der Hauptdiagonalen müssen Nullen stehen, keine “x”, auch wenn das Programm das dann anders anzeigt
Eigentlich sind die ersten zwei Regeln überflüssig, denn eine CSV – Datei muss diesen Regeln ohnehin genügen, damit sie sich als CSV bezeichnen darf. Warum schreibe ich das hier trotz dem nochmal hin? Weil Excel, zumindest in der Standardeinstellung, sie selbstverständlich nicht an diese Regeln hält. Man kann aber irgendwo im exportieren – Dialog jedoch entsprechende Einstellungen vornehmen. Eine gültige Eingabe – Datei würde z.B. so aussehen:
"", "Anlage 1", "Anlage 2", "Anlage 3" 0.0, 1.0, 2.0, 3.0 0.0, 0.0, 4.0, 5.0 0.0, 0.0, 0.0, 6.0
Dateiexport
Da die Sache mit dem Datei – Import zugegebener Maßen etwas wackelig ist, gibt es nun endlich auch einen funktionierenden “speichern” – Knopf. Dieser schreibt genau die Dateien, die das Programm anschließend auch wieder einlesen kann. Damit hat der Ärger mit Excel ein Ende: einfach die Daten von Anfang an im Programm verwalten, und mit diesem Speichern und wieder Laden. Und die gespeicherten CSV – Dateien dürfte Excel auch ohne Probleme lesen können — beim Lesen ist es so weit ich weiß weniger zickig als beim Schreiben.
Funktionsweise
Das Programm arbeitet mit einem klassischen Backtracking – Algorithmus. Die Reihenfolge, in welcher die Möglichkeiten ausprobiert werden, entspricht genau der Heuristik welche Schmigalla ’86 vorgeschlagen hat (kann gerade keine Referenz finden, das Buch liegt hier im Institut irgendwo rum — falls es Dich interessiert kann ich mal nachfragen). Da das Absuchen des gesamten Lösungsraumes für realistisch große Probleme lange dauert, wird die jeweils beste gefundene Lösung als Zwischenergebnis ausgegeben. Die erste gefundene Lösung entspricht dabei dem, was hin und wieder produziert wird, wenn man “Schmigalla von Hand macht”. Wobei ich aber aus seinem Buch nicht herausgelesen habe, dass das von Herr Schmigalla jemals so vorgesehen war. Ich weiß auch nicht, wer zu erst auf die Idee kam, Schmigalla von Hand auszuführen…
Bisschen tricky bei dem Problem ist, dass es gerne passiert, dass man Kombinationen mehrmals betrachtet (da die Reihenfolge, in welcher die Maschinen aufgestellt werden, für die Güte der Lösung egal ist — für den Alg. sind es aber verschiedene Wege zum Ziel, welche er auch gesondert betrachtet. Um diese Problematik ein wenig zu lockern habe ich einen Cache eingebaut, in welchem Konstellationen mit wenigen platzierten Maschinen gemerkt werden — wenn eine Stellung im Cache gefunden wird, so braucht diese nicht nochmals betrachtet werden. Das kann sicher noch verbessert werden (Spiegelungen/Rotationen erkennen, …).
Da eine optimale Lösung für ein Teilproblem nicht notwendigerweise auch Bestandteil der Gesamtlösung ist, verschließt sich das Problem leider der dynamischen Programmierung. Daher würde ich vermuten, dass es kein signifikant schnelleres exaktes Verfahren gibt. Nicht exakte Verfahren habe ich nicht betrachtet, aber da geht bestimmt noch einiges.
Dem Programm bei der Arbeit zuschauen
Haftungsausschluss
Ich habe dieses Programm in meiner Freizeit nach bestem Wissen und Gewissen erstellt und bin für Kritik sowie Verbesserungsvorschläge dankbar. Jedoch garantiere ich für nichts. Ich stelle dieses Programm “wie es ist” zur freien Benutzung zur Verfügung. Jegliche Gewärleistung — implizit oder explizit — betreffs der Marktgängigkeit oder auch nur der Tauglichkeit für irgend einen Einsatzzweck ist hiermit ausdrücklich ausgeschlossen. Dies schließt auch jeden denkbaren Folgeschaden, welcher aus der Benutzung dieser Software entsteht, ein. Wirklich, ich garantiere für gar nichts. Echt. Aber selbst nachrechnen ist erlaubt.
17 Comments
Jump to comment form | comments rss [?] | trackback uri [?]