Liste der Anhänge anzeigen (Anzahl: 2)
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
Liste der Anhänge anzeigen (Anzahl: 1)
@ 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.
