Backtracking Rekursion Problem

[mainstream86]

Hi,

habe folgendes Problem.
Ich will ein Kartenspiel mit 36 Karten per
Backtracking lösen lassen. Das ist erst mal nicht das
Problem. Leider dauert die Rekursion je nach Startkarte
unterschiedlich lang. Bei einigen Karten länger als
15 Sekunden. Der Flashplayer bricht ab, da die
standard Timeoutzeit von Flash erreicht wurde.
Kann man diese erhöhen? Benutze as3 und FB2.

[hgseib]

flash9: datei/einstellungen für veröffentlichungen...
flash-reiter: script-höchstzeit
also prinzipiel: ja, man kann sie verlängern.


wenn du allerdings in AS3 diese zeit überschreitest, dann -so sage ich mal- ist dein auswertungsprogramm aber nicht optimal programmiert?

[Omega Psi]

Das mag am Algorithmus liegen. Hast du den zur Hand?

[mainstream86]

		private function findNext(stufe:int):Boolean{

			//Anzahl restlicher Karten auf dem Feld					
			for(var a:int = numCards - 1 - stufe ; a >= 0  ; a--){
				//Hier neue Karte aus den verbleibenden
				var myCard:Card = Cards[a];
				
				for(var u:int = 0; u < 4; u++){
					
					if(cardTest(myCard)){
						
						//trace("Test OK");
						
						addToField(myCard);
						
						if(Field.length == numCards){return true;}
						else{
							if(findNext(stufe+1)){return true;}
							else{
								//Karte rückgängig machen
								removeFromField(a);
							}
						}
					}
					
					//Karte vier mal drehen
					myCard.rotate();	
				}
				 
			}													
			return false;	
		}

das ist das backtracking.

Veröffentlichungseinstellungen in Eclipse?

[hgseib]

ohne zu wissen, was das ganze soll ist natürlich keine aussage möglich.

cardTest
was lässt diese entscheidung durch?

deine u-schleife hinterlässt den eindruck, als wenn du alles 4x machst?
sehe aber den sinn dazu nicht ...

[hazy fantazy]

In Eclipse hast kannst du entweder einen Parameter an den Compiler übergeben oder die Zeit per Metadata festlegen. Ich habe den genauen Wortlaut für die Timeoutzeit jetzt nicht zur Hand, das muesstest du aber in der Hilfe zum Compiler bzw. Metadata finden könnnen

[mainstream86]

Hi,

hier mal die ganzen Dateien zum Download.
Die u-Schleife wird 4 mal ausgeführt weil die Karten an jeder Seite geprüft werden. Es werden halt alle möglichen Kombinationen der Karten in einer 6x6 Matrix ausprobiert.

http://www.wellenblau.de/dev/backtracking.zip

[hazy fantazy]

Das Problem scheint aber eher eine Endlosschleife als eine Begrenzung des Flashplayers zu sein. Ich glaube, da musst du noch mal ran.

[hgseib]

:-)))
so, jetzt wäre für uns leien halt noch interessant: nach welchen regeln wird gespielt?

a) es gibt nur eine einzige mögliche lösung in der alle fussstapfen zusammen passen (ausser dreh- und spiegelgleich)?
b) es führen keine fussstapfen aus dem spielfeld raus?

wenn man es selbst spielt, dann wären die regeln(?):
c) es werden je zwei karten getauscht?
d) es wird eine karte um 90 grad gedreht

und dein programm soll jetzt die lösung suchen, also welche schritte c+d gemacht werden müssen um schnellstmöglichst zu a zu kommen?


wenn dem so ist:
mit brutaler gewalt gehts bestimmt nicht. da könnte die rechenzeit ins astronomische steigen. ein bisschen intelligenz ist gefragt ;-)

z.b.
zwei tabellen erstellen, welche carten mindestens eine 1 und welche mindestens eine 4 haben. das würde die anzahl der zu testenden carten stark reduzieren, was bei der rekursiven suche schon einiges an zeit einspahren würde.
es gibt nur 6 karten, die sowohl 1 als auch 4 haben. bei einer anschluss-suche an 1 wäre somit fast die hälfte der carten schon ausgeschlossen. dito bei 4.

um nur mal ein beispiel zu nennen ;-)

[mainstream86]

Das Spiel ist eine Aufgabe aus unserem Studium! Es soll nicht wirklich
spielbar sein. Es soll das Spiel lösen.

Wir sollen mittels Backtracking nur eine von vielen Kombinationen
der Karten finden. Es wird mit einem Klick eine Karte bestimmt die
dann oben rechts die Erste zu prüfende Karte wird.
Danach werden die restlichen Karten angelegt und gedreht bis zu der
Startkarte eine Kombination gefunden wurde. Sollte keine Kombination gefunden werden wird die nächste Karte als Startkarte gesetzt.

Die Regeln sind leicht. Es dürfen nur kleine in kleine und große in große
Spuren übergehen. Die Spuren am Rand des Feldes sind egal.

Das Backtracking kann ich schlecht ändern, da es Hauptteil der Aufgabe
ist.

Endlosschleife ist es wohl kaum, nur leider gibt es im worst case verdammt
viele Möglichkeiten die Karten anzuordnen bis eine Kombination gefunden wurde. Anfangs sollte auch noch die Richtung der Spuren beachtet werden. Das wurde aber verworfen.

Die max-execution-time kann allerdings nicht höher als 60 Sek. eingestellt
werden.


Aber Danke für alle Hinweise und Tipps.

[hgseib]

ihr sollt programmieren, wie eine lösung gefunden wird, aber ihr dürft nichts am programm ändern??? naja, wirst schon wissen was du machst.

eine möglichkeit zu mehr rechenzeit zu kommen ist, die berechnung aufteilen (aber du darfst ja nichts ändern ?), das sie in mehreren onEnterFrames ausgeführt wird.
z.b. anstatt dass das programm sich selbst aufruft, wird diese möglichkeit auf einen stack (ein array) gegeben. das wird dann im nächsten onEnterFrame abgearbeitet.
bzw. nur eine bestimmte anzahl von cards berechnen, den zustand in variablen festhalten und die bearbeitung beenden. dann halt im nächsten onEnterFrames dort weiter arbeiten.

dabei hättest du dann auch die möglichkeit dem programm beim arbeiten zusehen zu können indem du die bis dahin berechneten carten anzeigen lässt.

[mainstream86]

Werde das mal Testen. Aufteilung hatte ich auch mal geplant.
Man wird dann allerdings eine lange lange Zeit davor sitzen.
Einige Karten werden bis zu 4000 mal gedreht und verlegt
wenn eine Lösung gefunden wird.

Werde das mal ausprobieren. Habe gemerkt das der Timeout
nicht greift wenn man das Programm im Debug-Modus laufen lässt.
Werde es halt so vorführen.

Thx für alle Tipps.

[hgseib]

jou mach mal und schade, wenns hier nicht weiter geht - war mal was anderes als die üblichen fragen, die sich die leute auch selbst beantworten könnten, wenn sie nur mal in die flash-hilfe reinsehen würden.