> Mein Optimierer verwendet eine (leicht erweiterte) QAP Formulierung, > und ich vermute, bei Arne ist es nicht viel anders. Das aufstellen > der Matrizen A und B ist von der eigentlichen Optimierung getrennt.
Der klare Vorteil einer strikten QAP-Formulierung ist, dass z.B. die Kostendifferenz zweier Belegungen, die sich nur um eine Vertauschung unterscheiden mit Rechenaufwand O(n) berechnet werden können (der Aufwand für die Neuberechnung der Kosten beläuft sich auf O(n^3) für ein QAP). Soweit ich das sehen konnte, nutzt Arnes Optimierer diese Tatsache jedenfalls nicht, sondern berechnet die Kosten für jedes generierte Layout aufs neue. In der Liesmich zu deinem Optimierer habe ich auch keine Hinweise darauf gefunden. >> • mittels Matrix C: Häufige Buchstaben auf guten Plätzen > > Nur dann, wenn man in C Häufigkeiten und Aufwände verwurstelt. Ich > mache das nicht explizit, sondern habe Terme analog zu A*B, nur dass > dort nur ein Summationsindex auftritt. Ja, momentan errechnet mein Programm die Matrix C aus den Häufigkeiten und Aufwänden. Zeilen und Spalten der Matrix sind also allesamt linear abhängig. > So wie im Artikel formuliert würde C zum Beispiel erlauben > auszudrücken, dass Belegungen, die eine Referenz-Belegung ähnlich > sind besser sind als solche, die das nicht sind (Stichwort: > Ctrl-XCV). Ich glaube Arne hat sowas, ich nicht. Daran habe ich noch nicht gedacht. xcv könnte man also ganz einfach auf die linke Seite zwingen, indem man für die Positionierung dieser Buchstaben auf die rechte Seite extrem hohe Kosten festlegt. >> • Shiftkollisionen oder allgemeiner: Modifierkollisionen >> Allgemein über Optimierung auf mehreren Ebenen (mit Modifiern) >> habe ich mir noch keine näheren Gedanken gemacht. Prinzipiell lassen >> sich Shiftkollisionen durchaus berücksichtigen, allerdings >> bräuchten wir keine nxn-Matrix, sondern eine 2nx2n, was das QAP >> um einiges erschweren würde (unnötigerweise aus meiner Sicht). > > So schlimm ist es nicht. Der Aufwand vervierfacht sich nur (in einer > naiven Implementierung), man hat ja nach wie vor nur n Tasten. Es ist wohl noch schwieriger, als ich dachte. Wie gibt man an, dass die Großbuchstaben auch auf die selben Tasten positioniert werden, wie die Kleinbuchstaben, wenn man doch eine 2nx2n Matrix hat. Zwar hat man nur n Tasten, aber die QAP Beschreibung erfordert doppelt so viele. Gruß, Stephan
signature.asc
Description: PGP signature