-         

+ Antworten
Ergebnis 1 bis 4 von 4

Thema: Backtracking Algo | Rekursion | Problem

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

    Backtracking Algo | Rekursion | Problem

    Anzeige

    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  

  2. #2
    Erfahrener Benutzer Roboter-Spezialist
    Registriert seit
    25.10.2007
    Ort
    41464 Neuss
    Alter
    48
    Beiträge
    375
    ich würde sagen:

    du legst immer ein kleeblatt ab, wenn du ein neues feld gefunden hast.
    und du betrachtest ein kleeblatt als hindernis, ähnlich einem baum.

    das ergibt folgendes problem:
    je nach labyrinth kann es vorkommen, das du einen unbesuchten bereich komplett mit kleeblättern umgibts, oder der suchbereich durch kleeblätter in mehrere teile zerlegt wird.
    dann kann der liebe käfer dort natürlich nicht mehr rein (da er vor den selbstgelegten kleeblättern erschrickt)

    lösung:
    lege die markierungen nicht beim vorwärts krabbeln, sondern erst wenn du nach ner sackgasse im backtracking wieder zurückgehst.

  3. #3
    Erfahrener Benutzer Fleißiges Mitglied
    Registriert seit
    06.05.2007
    Beiträge
    112
    @ fumir danke für deine Antwort aber
    leider löst das, dass Problem nicht, es muss irgendwo noch ein weiteres Problem geben.
    Ich habe das Gefühl, dass es beim Linksabbiegen scheitert. Auf dem Bild ist ja am Ende des Ganges keine Sackgasse, er könnte ja nach Links abbiegen, macht er allerdings nicht sondern geht einfach wieder zurück. Und legt dann die Kleeblätter, bei der Test Welt also da wo die Bäume Rings um stehen läuft er dann nur noch im Kreis und erkennt es nicht. Solangsam verzeifel ich da ich einige Sache des Algos denn ich übersetzt habe nicht richtig verstehen auch nach dem Einarbeiten, verstehe einfach nicht was es mit index und loesung auf sich hat, wäre für weitere Vorschläge dankbar.
    Miniaturansichten angehängter Grafiken Miniaturansichten angehängter Grafiken backtracking_2.jpg  

  4. #4
    Erfahrener Benutzer Fleißiges Mitglied
    Registriert seit
    06.05.2007
    Beiträge
    112
    So hab das Problem nun endlich mit ein "wenig" Hilfe gelöst, ich poste einfach mal den fertigen Code wenn es jemanden interressiert.

    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 !=4 ) {
          // 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();}
       if(schritt==4){kara.turnLeft(); 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 (kara.mushroomFront()) {return true;}
          // if (schritt ist gültig)
          if (ok) {kara.move();
          loesung=loesung + schritt;   // Erweitere loesung um schritt
             // Markiere neues Feld mit aktueller Schrittzahl
    		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      
          } 
    	  
    		if(schritt==3){ kara.turnRight();}
    	 if(schritt==2){kara.turnLeft();}
        if(schritt==4){kara.turnLeft(); kara.turnLeft();} 
       }
       return false; // keine Lösung gefunden
    }
    
    
    
    void KaraProgram::myProgram() {
    /*   
       Hier beginnt das Kara-Hauptprogramm:
    */
    	if(FindeLoesung(0,0)==true){tools.showMessage("Ausgang gefunden");} 
    	else{tools.showMessage("Gibbet keinen");}
    }

+ Antworten

Berechtigungen

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