Backtracking Algo | Rekursion | Problem

[WDragon91]

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


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


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

[fumir]

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.

[WDragon91]

@ 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.

[WDragon91]

So hab das Problem nun endlich mit ein "wenig" O:) Hilfe gelöst, ich poste einfach mal den fertigen Code wenn es jemanden interressiert.


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");}
}