Zurück   Flashforum > Flash > ActionScript > Softwarearchitektur und Entwurfsmuster

Antwort
 
LinkBack Themen-Optionen Ansicht
Alt 16-12-2007, 12:41   #1 (permalink)
Neuer User
 
Registriert seit: Mar 2007
Beiträge: 5
Question Backtracking Rekursion Problem

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.
mainstream86 ist offline   Mit Zitat antworten
Alt 16-12-2007, 12:53   #2 (permalink)
Techniker
 
Benutzerbild von hgseib
 
Registriert seit: Sep 2003
Ort: 64807
Beiträge: 18.114
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?
__________________
die ultimative antwort auf alle programmierfragen: der debugger
mfg h.g.seib www.SeibsProgrammLaden.de
hgseib ist offline   Mit Zitat antworten
Alt 16-12-2007, 12:53   #3 (permalink)
Perverted Hermit
 
Benutzerbild von Omega Psi
 
Registriert seit: Mar 2004
Ort: Bremen
Beiträge: 13.419
Das mag am Algorithmus liegen. Hast du den zur Hand?
Omega Psi ist offline   Mit Zitat antworten
Alt 16-12-2007, 13:23   #4 (permalink)
Neuer User
 
Registriert seit: Mar 2007
Beiträge: 5
Post

Code:
		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?
mainstream86 ist offline   Mit Zitat antworten
Alt 16-12-2007, 15:38   #5 (permalink)
Techniker
 
Benutzerbild von hgseib
 
Registriert seit: Sep 2003
Ort: 64807
Beiträge: 18.114
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 ...
__________________
die ultimative antwort auf alle programmierfragen: der debugger
mfg h.g.seib www.SeibsProgrammLaden.de
hgseib ist offline   Mit Zitat antworten
Alt 16-12-2007, 15:48   #6 (permalink)
Nagelneuer User
 
Benutzerbild von hazy fantazy
 
Registriert seit: Dec 2005
Beiträge: 923
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
__________________
The fact that you've got "Replica" written on the side of your gun and the fact that I've got "Desert Eagle written on the side of mine ... :D
hazy fantazy ist offline   Mit Zitat antworten
Alt 16-12-2007, 19:34   #7 (permalink)
Neuer User
 
Registriert seit: Mar 2007
Beiträge: 5
Daten

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
mainstream86 ist offline   Mit Zitat antworten
Alt 16-12-2007, 21:55   #8 (permalink)
Nagelneuer User
 
Benutzerbild von hazy fantazy
 
Registriert seit: Dec 2005
Beiträge: 923
Das Problem scheint aber eher eine Endlosschleife als eine Begrenzung des Flashplayers zu sein. Ich glaube, da musst du noch mal ran.
__________________
The fact that you've got "Replica" written on the side of your gun and the fact that I've got "Desert Eagle written on the side of mine ... :D
hazy fantazy ist offline   Mit Zitat antworten
Alt 16-12-2007, 22:00   #9 (permalink)
Techniker
 
Benutzerbild von hgseib
 
Registriert seit: Sep 2003
Ort: 64807
Beiträge: 18.114
:-)))
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 ;-)
__________________
die ultimative antwort auf alle programmierfragen: der debugger
mfg h.g.seib www.SeibsProgrammLaden.de

Geändert von hgseib (16-12-2007 um 22:02 Uhr)
hgseib ist offline   Mit Zitat antworten
Alt 17-12-2007, 01:13   #10 (permalink)
Neuer User
 
Registriert seit: Mar 2007
Beiträge: 5
Viel zu schwer!

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.
mainstream86 ist offline   Mit Zitat antworten
Alt 17-12-2007, 01:45   #11 (permalink)
Techniker
 
Benutzerbild von hgseib
 
Registriert seit: Sep 2003
Ort: 64807
Beiträge: 18.114
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.
__________________
die ultimative antwort auf alle programmierfragen: der debugger
mfg h.g.seib www.SeibsProgrammLaden.de
hgseib ist offline   Mit Zitat antworten
Alt 17-12-2007, 09:53   #12 (permalink)
Neuer User
 
Registriert seit: Mar 2007
Beiträge: 5
Thx

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.
mainstream86 ist offline   Mit Zitat antworten
Alt 17-12-2007, 10:12   #13 (permalink)
Techniker
 
Benutzerbild von hgseib
 
Registriert seit: Sep 2003
Ort: 64807
Beiträge: 18.114
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.
__________________
die ultimative antwort auf alle programmierfragen: der debugger
mfg h.g.seib www.SeibsProgrammLaden.de
hgseib ist offline   Mit Zitat antworten
Antwort

Lesezeichen

Themen-Optionen
Ansicht

Forumregeln
Es ist Ihnen nicht erlaubt, neue Themen zu verfassen.
Es ist Ihnen nicht erlaubt, auf Beiträge zu antworten.
Es ist Ihnen nicht erlaubt, Anhänge hochzuladen.
Es ist Ihnen nicht erlaubt, Ihre Beiträge zu bearbeiten.

BB-Code ist an.
Smileys sind an.
[IMG] Code ist an.
HTML-Code ist aus.
Trackbacks sind an
Pingbacks sind an
Refbacks sind an



Alle Zeitangaben in WEZ +1. Es ist jetzt 10:54 Uhr.

Domains, Webhosting & Vserver von Host Europe
Unterstützt das Flashforum!
Adobe User Group


Copyright ©1999 – 2014 Marc Thiele