Topswop

Ich probiere mich momentan an AI Zimmermann’s Programming Contest, bei dem es darum geht ein wirklich sehr rechenintensives Problem zu lösen. Die Aufgabenstellung findet man hier. Die Probleminstanzen für k in {2,3,5,7,11} lassen sich noch sehr einfach mit einem naiven Bruteforce-Verfahren errechnen, bei dem einfach alle Permutationen des Kartenstapels ausgewertet werden. Ich denke ich dürfte auch für k=13 die optimale Lösung haben (auch wenn ich dies nicht ganz beweisen kann). Danach wird es schwierig und eine geschickte Vorgehensweise ist angesagt (vor allem hab ich hier nur einen Laptop, den ich auch nicht 24/7 laufen lassen möchte). Da ich meine ersten Lösungen gerade schrittweise eingegeben habe, erlaubte das noch den ein oder anderen Rückschluss auf die derzeitig beste Lösung. Für k=97 hat meine beste Lösung genau 2300 Züge. Erschreckenderweise ist das aber nur 0.16 der zur Zeit besten Lösung. Und auch beim Eingeben meiner Lösung für k=17 stieg meine Punktezahl nicht um 1, so dass es auch hier noch Spielraum nach oben geben muss. Mit meinen jetzigen Lösungen komme ich gerade mal auf Platz 100 (27.12. um 19:33 Uhr, mittlerweile könnte sich mein Punktestand aufgrund des Bewertungssystems auch schon verschlechtert haben). Naja, ich mal mir da sowieso keine großen Chancen auf eine gute Plazierung aus, aber ich möchte wenigstens meine jetzige Lösung noch ein wenig verbessern :).

Advertisements
Dieser Beitrag wurde unter Allgemein veröffentlicht. Setze ein Lesezeichen auf den Permalink.

4 Antworten zu Topswop

  1. anonym2 schreibt:

    Ich war so irgendwo zwischen Platz 20 und 30, bevor Al’s Datenbank sich verabschiedet hatte und alles wieder von vorne anfing. Dann hatte ich aber keine Lust mehr, alles wieder neu einzugeben, da ich ohnehin keine Chance mehr sah, unter die ersten 10 zu kommen.

    Gefällt mir

  2. nope schreibt:

    The UT Dallas group made several additional improvements and was able to determine that permutations of length 17 require at most 159 Topswops steps.

    hast du die 159 Lösung?

    Gefällt mir

    • anonym2 schreibt:

      ja, die 159 ist kein Problem, wenn man nur Konfigurationen untersucht, die am Schluss vollständig geordnet sind. Unter diesen Voraussetzungen finde ich auch 204 für n=19, allerdings nicht die 207, das wohl das Optimum für geordnete Endfolgen darstellt.

      Gefällt mir

    • anonym2 schreibt:

      ja, die 159 ist kein Problem, wenn man nur Konfigurationen untersucht, die am Schluss vollständig geordnet sind. Unter diesen Voraussetzungen finde ich auch 204 für n=19, allerdings nicht die 207, das wohl das Optimum für geordnete Endfolgen darstellt.

      Gefällt mir

Kommentar verfassen

Trage deine Daten unten ein oder klicke ein Icon um dich einzuloggen:

WordPress.com-Logo

Du kommentierst mit Deinem WordPress.com-Konto. Abmelden /  Ändern )

Google+ Foto

Du kommentierst mit Deinem Google+-Konto. Abmelden /  Ändern )

Twitter-Bild

Du kommentierst mit Deinem Twitter-Konto. Abmelden /  Ändern )

Facebook-Foto

Du kommentierst mit Deinem Facebook-Konto. Abmelden /  Ändern )

Verbinde mit %s