> Meine ursprüngliche Idee zum Optimierungsalgorithmus ging in diese > Richtung, die Einschränkung sollte aber dynamisch gefunden werden: Man > sortiert die Zeichen ihrer Häufigkeit nach. Dann nimmt man die > häufigsten k Zeichen (k vielleicht 4, soviel man eben packt), probiert > alle ihre Verteilungen über die n Tasten aus (also n!/k! > Kombinationen), und berechnet für jede dieser Kombinationen eine untere > Abschätzung für den Tippaufwand einer Tastatur, die die Tasten auf diese > Weise festlegt. Liegt die untere Abschätzung über der besten bekannten > Tastatur kann man die betreffende Kombination gleich verwerfen; das ist > der Kern der Idee. Für die Kombinationen die Aussicht haben, die beste > Tastatur zu schlagen, nimmt man ein (k+1)-tes Zeichen hinzu und probiert > alle verbleibenden Positionen aus, berechnet dafür nunmehr strengere > untere Schranken, und so weiter. > > Ob das funktioniert oder nicht hängt davon ab, ab wieviel schlecht > platzierten Zeichen eine Tastatur endgültig verhunzt ist. Vielleicht > geht das zu langsam, um die kombinatorische Explosion im Zaum zu halten. > Es fragt sich auch, ob es sich überhaupt lohnt, diesen Weg zu gehen, > dann das simple Verfahren funktioniert allem Anschein nach gut. Aber > Spaß macht es bestimmt.
Ich habe in Python deinen damals beschriebenen Algorithmus geschrieben. Und zwar: 1. Mache eine zufällige Tastatur 2. Tausche zwei Zeichen. Gibt das bessere Punkte, dann mache mit „2“ weiter. Gibt es nicht bessere Punkte, dann tausche zwei anderen ( bis 32 * 32 = 1024 minus 32 die gleich sind -> 992 Möglichkeiten erschöpft sind). 3. Ist keine Besserung mehr möglich, dann höre auf. Das ist doch so richtig oder nicht? Under Python braucht man dazu auf meinem Rechner 4-6 Sekunden (ich kann bis 5 zählen). Es liefert zwar ein Ergebnis, aber nicht immer sehr schön. Nur 1 von 25 Tastaturen gefällt mir. Sie sind nicht so schöne wie deine. Vielleicht benutze ich eine falsche Bewertung? Wie bewertest du ganz genau? ==== Mein vorheriger Algorithmus liefert bessere Ergebnisse. Bei mir. Die geht so: 1. Mache 1000 Tastaturen (a) durch Zufall oder (b) durch Mehrung vorgegebener Tastaturen in beliebiger Zahl, bis 1000 da sind. Die Mehrung geschieht durch Kopie und Mutation. 2. Nehme an jeder von ihnen eine oder mehr Mutationen vor und lege die neue Tastatur zu der Liste. Entferne alle Doppelgänger. Mache weiter bis über 1000 da sind. 3. Reduziere die Liste auf N (z.B. 1000) durch Verwerfung derjenigen mit den meisten Punkten. Mache bei Punkt 2 weiter. Mache weiter bis eine bestimmte Zahl von Generationen. Dann guck manuell die 50 besten an und suche welche aus, die vom Aussehen her sich am besten für die weitere „Zucht“ eignen. Dann wiederhole. Auf diese Weise komme ich pro Abend an 2-3 „guten“Tastaturen. Es ist also sehr langsam und mühselig. ==== Beobachtung: Durch wiederholte Sichtung der „Top 50“ fällt auf, dass gelegentlich neue Spitzenreiter offensichtlich Söhne von schlechteren Vätern sind. Es bedarf demnach oft mehr als eine Mutation bevor eine Besserung eintritt. Das geht bei deinem Algorithmus nicht. Da muss jede Mutation eine Besserung bringen. Auch mal was zum überlegen??? ==== Wenn ich mit deinem Algorithmus 50 Tastaturen mache und lasse sie durch meinen laufen kommen scheinbar sehr gute heraus. Bei Interesse werde ich davon welche hier posten. Ulf
