Aufgabe 9.5

Bachelor Parallele und funktionale Programmierung
1

Sokoban Solver

Disclaimer: Dieser Thread wurde aus dem alten Forum importiert. Daher werden eventuell nicht alle Formatierungen richtig angezeigt. Der ursprüngliche Thread beginnt im zweiten Post dieses Threads.

2

Aufgabe 9.5
Hallo zusammen,
um bereits verarbeitete Spielfelder zu speichern, verwenden wir eine verkettete Liste. Mit der ArrayList aus den ersten sequentiellen Umsetzungsversuchen kracht es auch gleich mit mehreren Threads…
Welche verkette Liste bietet sich als thread-sichere Alternative an? Eine ConcurrentLinkedQueue?
Wäre es sinnvoll, wenn mehrere Threads gleichzeitig die Liste nach bestimmten Spielfeldern absuchen, jeweils einen Iterator zu verwenden?

3

Verwendet lieber eine (Concurrent)HashMap, bei einer verketteten Liste dauert die Suche sicherlich sehr lange, wenn die Levels größer sind.

4

Hat jemand die HarderPruningCases geknackt, ohne Deadlocks umzusetzen? Meine Implementierung schafft es ab Level 94 (Index 0) nicht mehr (sowohl sequentiell als auch parallel).

5

Da hänge ich momentan auch.

6

Haengt euch daran nicht auf. wenns nicht klappt, implementiert einfach die deadlock detection ;-).

7

Die Simple Deadlock Detection geht gut ab:
lvl 6 von 36 sekunden mal kurz auf 0,1 Sekunden (sequentiell) aber jetzt stirbt es ab den EVEN_HARDER_CASES in lvl 92.

Muss man die Frozen Deadlock Detecton auch noch einbauen, oder kanns auch noch an was anderem liegen?

8

Keine Ahnung :smiley: Den schafft nicht mal die aktuelle Musterloesung ;). Dort ist aber auch nur die Simple Deadlock Detection implementiert.

9

Frozen Deadlocks hats garnicht gebraucht .Mit Lowerbound fallen diese Testcases bleiben nur noch 143 144 und 145. Ich hab auch noch zusätzlich nur snapshots der Lösung gespeichert um Speicher zu sparen, so daß man am Ende die Lösung (aber mit verhältnismässig wenig Rechenaufwand) zusammenbauen muss. Blöd nur daß die Strings kurz vor der Abgabe nicht hundertprozentig gepasst haben, also die Dinger zwar gelöst werden aber nicht der richtige Pfad ausgespuckt wird. Ich glaub für diese Abgabe wird mich mein Tutor hassen :scared: :nuts: