> 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

Attachment: signature.asc
Description: PGP signature

Antwort per Email an