Foren » 35. BwInf

Rotation - Puzzel Nr. 3

    • 6 Beiträge
    8. Dezember 2016 16:09:51 CET
    Hallo,
    nach wievielen Zügen steht fest, dass das Puzzel Nr.3 (mit den 10 x 10 Feldern) nicht lösbar ist?
    Wie wird das festgestellt?
    • 26 Beiträge
    8. Dezember 2016 16:44:26 CET
    Es ist in 90 Zügen lösbar...
    • 6 Beiträge
    8. Dezember 2016 16:49:06 CET
    Wahnsinn - und wie geht man vor, um 90 Züge zu erforschen?
    • 31 Beiträge
    8. Dezember 2016 17:14:36 CET
    Man muss den Code so optimieren, dass er das ganze möglichst effizient löst. Heuristiken sind dabei nicht notwendig. In Python habe ich das mit Optimierung in unter einer Minute geschafft (als ich das in die Einsendung getan habe, hat es komischerweise länger gedauert), wenn man C oder vergleichbare Programmiersprachen nimmt, geht das in unter 10 Sekunden. Die Laufzeit wird wohl in der ersten Runde keine Relevanz haben, wichtig ist nur (ohne Gewähr) hier, dass man den Plan findet.
    Dieser Beitrag wurde am 8. Dezember 2016 17:15:05 CET von Gabriel Dengler bearbeitet
    • 26 Beiträge
    8. Dezember 2016 22:12:25 CET
    Haha xD und ich war schon stolz, als ich die Laufzeit in Java auf eine halbe Stunde runter hauen konnte :P
    Der Knackpunkt war doch, die schon bereits gehabten Puzzlemöglichkeiten aus zu sortieren oder? >.<
    • 4 Beiträge
    9. Dezember 2016 08:23:56 CET
    [blockquote]Fabian Märkert sagte:
    Haha xD und ich war schon stolz, als ich die Laufzeit in Java auf eine halbe Stunde runter hauen konnte :P
    Der Knackpunkt war doch, die schon bereits gehabten Puzzlemöglichkeiten aus zu sortieren oder? >.<[/blockquote]


    Sehe ich genauso! Hatte Anfangs auch das Problem mit der langen Laufzeit (programmiere auch in Java), hab das aber wie folgt gelöst:

    Die Liste, welche die gehabten Puzzlemöglichkeiten darstellt, wird je nach Tiefe der Breitensuche gigantisch. Daher muss man hier eine Hashtabelle verwenden, damit das Durchsuchen der gehabten Puzzlemöglichkeiten quasi "blitzschnell" funktioniert (Liegt an der Komplexität von Hashtabellen)

    Zum Vergleich: Mit ArrayList habe ich nach 40 min keine Lösung für das 3. Beispiel gefunden und daher abgebrochen. Alleine durch den Einsatz von HashSet schafft selbst mein PC das in weniger als 20 Sekunden
    • 26 Beiträge
    9. Dezember 2016 12:20:50 CET
    Oh wow... Mit Hashtabellen habe ich noch nie gearbeitet. Muss ich mir dann mal unbedingt angucken.
    • 6 Beiträge
    9. Dezember 2016 12:35:40 CET
    [blockquote]Nils B said:
    [blockquote]Fabian Märkert sagte:
    Haha xD und ich war schon stolz, als ich die Laufzeit in Java auf eine halbe Stunde runter hauen konnte :P
    Der Knackpunkt war doch, die schon bereits gehabten Puzzlemöglichkeiten aus zu sortieren oder? >.<[/blockquote]


    Sehe ich genauso! Hatte Anfangs auch das Problem mit der langen Laufzeit (programmiere auch in Java), hab das aber wie folgt gelöst:

    Die Liste, welche die gehabten Puzzlemöglichkeiten darstellt, wird je nach Tiefe der Breitensuche gigantisch. Daher muss man hier eine Hashtabelle verwenden, damit das Durchsuchen der gehabten Puzzlemöglichkeiten quasi "blitzschnell" funktioniert (Liegt an der Komplexität von Hashtabellen)

    Zum Vergleich: Mit ArrayList habe ich nach 40 min keine Lösung für das 3. Beispiel gefunden und daher abgebrochen. Alleine durch den Einsatz von HashSet schafft selbst mein PC das in weniger als 20 Sekunden[/blockquote]

    Wie hast Du den Hash für Deine Puzzel erzeugt? Bei mir ist das der Zeitfresser
    • 4 Beiträge
    9. Dezember 2016 15:37:19 CET
    [blockquote]Holger Schlüter said:
    [...]

    Wie hast Du den Hash für Deine Puzzel erzeugt? Bei mir ist das der Zeitfresser[/blockquote]

    Ich habe den Zustand eines Spielfeldes bzw. einer Puzzlemöglichkeit als Objekt definiert, bei mir nennt sich diese Klasse "Spielfeld".

    Daher musste ich in dieser Klasse die Methoden hashCode() [und equals()] implementieren, da diese von einem Java Hash-Set vorrausgesetzt werden.

    Die hashCode Methode gibt dabei den Hashcode des Zeichenarrays zurück (via Arrays.hashCode() - einer Java internen Methode für Hashcodes von Arrays).

    Habe damit nie Probleme feststellen können...
    • 6 Beiträge
    11. Januar 2017 19:14:08 CET
    Ich habe die Aufgabe mit Dijkstra gelöst. In meinem Falle war die PriorityQueue aus der Standard-Bibliothek das Problem. Schockierenderweise hat diese nämlich eine lineare Laufzeitkomplexität. Da ich sonst nichts besseres gefunden habe, habe ich mir einfach selbst eine mit großteils logarithmischer Laufzeitkomplexität geschrieben. Nach einigem hin und her habe ich es geschafft, sämtliche Datensätze in unter 2,3 Sekunden auszurechnen.
    • 17 Beiträge
    12. Januar 2017 10:57:59 CET
    Interessant, warum Dijkstra? Hast du das Problem dann irgendwie anders modelliert? So wie ich die Lösung der Anderen verstanden habe (und wie ich es auch gemacht habe), geht es doch nur um eine vollständige Suche, bei der jede Kante ein Gewicht von 1 hat. Warum also keine Breitensuche?
    • 6 Beiträge
    12. Januar 2017 17:09:30 CET
    Das ist eine gute Frage...
    Aber bei einer Breitensuche muss man doch sowieso die Vorgängerknoten speichern.
    Wozu braucht man denn dann eigentlich noch ein HashSet?
    Dieser Beitrag wurde am 12. Januar 2017 17:09:41 CET von Robin Richtsfeld bearbeitet
    • 17 Beiträge
    12. Januar 2017 19:49:43 CET
    Das HashSet braucht man, um zu überprüfen, ob ein Knoten schon besucht wurde. Die offensichtliche Lösung wäre es, einfach eine Liste aller bisher gefundenen Knoten zu führen, dann musst du die aber auch jedes Mal von vorne bis hinten durchsuchen, was für die Laufzeit nicht so toll ist. Mit dem HashSet kannst du den zu überprüfenden Knoten einfach als Hash benutzen und so ziemlich schnell herausfinden, ob er schon besucht wurde.
    • 6 Beiträge
    12. Januar 2017 20:16:00 CET
    Dass ein HashSet eine Laufzeitkomplexität von O(1) hat, ist mir durchaus bewusst. Ich wollte lediglich darauf hinaus, dass die Existenz eines Vorgängers (Wert != null) gleichbedeutend mit "besucht" ist und man sich das HashSet somit komplett sparen kann.
    Dieser Beitrag wurde am 12. Januar 2017 20:16:50 CET von Robin Richtsfeld bearbeitet
    • 17 Beiträge
    13. Januar 2017 14:59:56 CET
    [blockquote]Robin Richtsfeld said:
    Dass ein HashSet eine Laufzeitkomplexität von O(1) hat, ist mir durchaus bewusst.[/blockquote]
    O(1) gilt soweit ich weiß nur für den absoluten Optimalfall, deswegen habe ich bewusst nur "ziemlich schnell" gesagt.

    [blockquote]Robin Richtsfeld said:
    Ich wollte lediglich darauf hinaus, dass die Existenz eines Vorgängers (Wert != null) gleichbedeutend mit "besucht" ist und man sich das HashSet somit komplett sparen kann.[/blockquote]
    Verstehe ich nicht. Wie willst du denn überhaupt die Existenz eines Vorgängers überprüfen, ohne ein HashSet oder eine langsamere Variante zu benutzen?
    • 6 Beiträge
    13. Januar 2017 15:19:11 CET
    Du musst doch ohnehin speichern, von wo du gekommen bist.