- LiTime Speicher und Akkus         
Ergebnis 1 bis 4 von 4

Thema: Backtracking Algo | Rekursion | Problem

Baum-Darstellung

Vorheriger Beitrag Vorheriger Beitrag   Nächster Beitrag Nächster Beitrag
  1. #1
    Erfahrener Benutzer Fleißiges Mitglied
    Registriert seit
    06.05.2007
    Beiträge
    112

    Backtracking Algo | Rekursion | Problem

    Hallo, zusammen ich probiere jetzt schon seit einiger Zeit einen Backtracking Algo zu programmieren anhand dieses Pseudocodes

    Code:
    boolean FindeLoesung(int index, Lsg loesung, ...) {
    	// Allgemeiner Backtracking Algorithmus
    	// index = Schrittzahl, loesung = Referenz auf Teillösung
    	while (es gibt noch neue Teil-Lösungsschritte) {
    		Wähle einen neuen Teil-Lösungsschritt schritt; // Heuristik
    		if (schritt ist gültig) {
    			Erweitere loesung um schritt;
    			
    			if (loesung noch nicht vollständig) {
    				// rekursiver Aufruf von FindeLoesung
    				if (FindeLoesung(index+1,loesung,...)) {
    					 return true; // Lösung gefunden
    				} else { // wir sind in einer Sackgasse
    					Mache schritt rückgängig; // Backtracking
    	 			}
    			} else return true; // Lösung gefunden -> fertig
    		} 
    	} return false;
    } // Bei true als Rückgabewert steht die Lösung in loesung
    Kurze Einführung, es handelt sich dabei bzw soll sich dabei um eine Simulationssoftware handeln. Inder Software gibt es einen Käfer der folgende Sensoren hat

    Baum Vorne, Baum Links, Baum Rechts.
    Blatt Vorne, Blatt Links, Blatt Rechts.
    Pilz Vorne

    Bewegungen:
    ein Schritt nach vorne
    drehung links
    drehung rechts

    Kleeblat legen
    Kleeblat aufheben


    Und so sieht nun mein Code für die Simulationssoftware aus
    Code:
    boolean FindeLoesung(int index, double loesung) {
    	// index       = aktuelle Schrittzahl
    	// loesung     = Referenz auf bisherige Teil-Lösung
    
    	int schritt = 0;
    
    	// while(es gibt es noch neue Teil-Lösungsschritte)
    	while (schritt !=3 ) {
    		// Wähle einen neuen Teil-Lösungsschritt schritt;
    		schritt ++;	// Weg nach 1. oben, 2. rechts, 3. unten
    		// und 4. links zu erweitern versuchen.
    		if(schritt==1) {}else{
    	if(schritt==2){ kara.turnRight();}
    	if(schritt==3){kara.turnLeft();}
    		}
    	// Tests, ob schritt gültig ist
    		boolean ok = true;
    		// Test, ob schritt innerhalb Brett bleibt
    
    		// Test, ob schritt durch Wand führt (sofern innerhalb)
    		if (kara.treeFront()) ok = false;
    		// Test, ob schritt auf ein bereits besuchtes Feld führt
    		if (kara.leafFront()) ok = false;
     
    		// if (schritt ist gültig)
    		if (ok) {kara.move();
    		loesung=loesung + schritt;	// Erweitere loesung um schritt
    			// Markiere neues Feld mit aktueller Schrittzahl
    		if(!kara.onLeaf())
    		{kara.putLeaf();}
    
    			// Visualisierung
    				 
    
    			// if (loesung noch nicht vollständig) 
    			if (!kara.mushroomFront()) {
    				// rekursiver Aufruf von FindeLoesung
    				if (FindeLoesung(index+1, loesung)) {
    					// Lösung gefunden	
    					return true;
    				} else {
    					// Wir sind in einer Sackgasse:
    					// Mache schritt rückgängig: Backtracking
    					kara.turnLeft();
    					kara.turnLeft();
    					kara.move();
    					kara.turnLeft();
    					kara.turnLeft();
    					
    									
    				}
    			} else return true; // Lösung gefunden -> fertig		
    		}	
    	}
    	return false; // keine Lösung gefunden
    }
    
    
    
    void KaraProgram::myProgram() {
    /*	
    	Hier beginnt das Kara-Hauptprogramm:
    */
    FindeLoesung(0,0);
    }
    So sieht das ganze dann aus.

    Die Rekusion funktioniert soweit, das erkennt man an dem Test, der Käfer sucht alles ab und geht dann zur Ausgangsposition, beim komplexen Laby allerdings sucht er nur ein Bruchteil aller Wege ab und kehrt dann zur Ausgangsposistion zurück.

    Deshalb brauche ich eure Hilfe ich habe keine Ahnung woran das liegen kann.
    Und was ich bei dem Code nicht ganz verstehe denn ich übernommen also auf mein Programm angepasst habe ist die Variabel Index und Loesung.

    Wäre für eure Hilfe echt dankbar.

    Mfg Matze
    Miniaturansichten angehängter Grafiken Miniaturansichten angehängter Grafiken komplexes_labyrinth.jpg   test_rekursion.jpg  

Berechtigungen

  • Neue Themen erstellen: Nein
  • Themen beantworten: Nein
  • Anhänge hochladen: Nein
  • Beiträge bearbeiten: Nein
  •  

LiFePO4 Speicher Test