Java Backtracking Boolean Array

[hubertus1990]

Hi Leute.

Habe eine kleine Frage bezüglich Backtracking.
Ich möchte alle möglichen true/false Kombinationen eines boolean Arrays mit 4 Werten mittels Backtracking herausfinden, also zum Beispiel:

TTTT
TTTF
TTFF usw...

leider funktioniert die Sache bei mir nicht so ganz.
Kann mir jemand sagen was ich falsch mache?

"Main" Methode

boolean[] visitors = new boolean[4] { true, true, true, true }

	public void printVariations() {
	
		do {
			if (isValid(visitors)) { // check if kombination is allowed
				/* print */
				
				StringBuffer a = new StringBuffer();
				for(int i = 0; i < visitors.length; i++) {
					
					if(visitors[i] == true) a.append(Person.values()[i] + " ");
				}
				
				System.out.println(a.toString());
			}
			
		} while (nextState(0) == true); // as long as it is somehow possible, to find a valid way, the loop continues
	}

Die Methode isValid(visitors) macht nichts anderes als zu überprüfen, ob die errechnete Kombination erlaubt ist (Ausgabe erfolgt nur, wenn erlaubt) -> bei mir ist beispielsweise TTFF nicht erlaubt. Sollte aber irrelevant bezüglich der eigentlichen Frage sein.


Rekursive Methode für Backtracking

	public boolean nextState(int level) {

		System.out.println("try");

		if(visitors[level] == true) { // wahl gültig
			visitors[level] = false;
			
			if(level >= visitors.length - 1) return true; // vektor vollständig
				
			if(nextState(level + 1) == true) return true;
			else visitors[level] = true; // rückgängig machen
		}

		return false;
	}

 

[NullPointer]

leider funktioniert die Sache bei mir nicht so ganz.

Kannst du das noch etwas genauer beschreiben?

 

[hubertus1990]

System.out.println("try");

Diese Codezeile wird exakt 5 mal ausgegeben, obwohl es 2^4 Variationen gibt

 

[Darlis]

Du bekommst 5x "try" weil beim ersten nextState(0) das visitors-Array erst komplett durchlaufen wird und alles auf false gesetzt wird (4x try). Der nächste Aufruf von nextState(0) endet direkt mit return false (1x "try") weil visitors[0] == false ist. Schon mal im Debugger durchgelaufen?

Vielleicht sollte in Zeile 5 eher isValid(visitors) stehen?
Btw. ist die Einrückung ab Zeile 10 etwas verwirrend.

 

[NullPointer]

Dein Programm backtrackt nirgendwo, sondern setzt einfach nur die Felder des Arrays eins nach dem anderen auf false. Deshalb bekommst du genau fünf Durchläufe: TTTT, FTTT, FFTT, FFFT, FFFF.

 

[hubertus1990]

@Darlis:
Ja aber das ist immer so ne Sache ne Rekursion mit dem Debugger zu durchlaufen. Das wird sehr schnell total unübersichtlich.
Wie gesagt, isValid(visitors) überprüft lediglich bestimmte von mir festgelegte Regeln, ob die errechnete Kombination "erlaubt" ist und nur Einfluss darauf ob die Kombination auch ausgegeben wird, und nicht auf die Anzahl der Kombinationen.

@NullPointer:
Das ist richtig. Allerdings dist mir nicht ganz klar wieso.
Diese Zeile:

else visitors[level] = true; // rückgängig machen

wäre eigentlich dafür verantwortlich. Ich kann mir nicht ganz erklären wieso diese falsch implementiert ist.

EDIT:
Habe mir grade mal die WIkipedia Ansätze zu Backtracking durchgelesen, sieht meinem Code eigentlich sehr ähnlich, nur dass Punkt 1 im WIkipedia Artikel durch meine Do-While Schleife außerhalb der eigentlichen Backtracking Methode erfolgt.
http://de.wikipedia.org/wiki/Backtracking

 

[NullPointer]

Diese Zeile wird nie ausgeführt. Nachdem du rekursiv runtergegangen bist bis zum letzten Arrayelement, wird dieses auf F gesetzt, der Array ist jetzt also FFFF. Danach returnt die Funktion true (Zeile 8), weil das Arrayende erreicht ist. Die aufrufende Funktion (einen Schritt zurück) returnt ebenfalls true, weil die aufgerufene true war (Zeile 10) und alle weiteren auch, bis du schließlich rausspringst.

 

[hubertus1990]

Dankesehr, hab das ganze jetzt mal ausführlich mit dem Debugger durchlaufen und du hast Recht. Nun ist die Frage, was mache ich dagegen?

 

[Darlis]

Ich glaube, dass Backtracking für dein Problem der false Ansatz ist: Du willst alle möglichen (gültigen) Kombinationen deines Array haben, Backtracking liefert dir aber nur eine Kombination. Ob diese gültig ist, wird in deinem Backtracking-Algorithmus aber nicht geprüft.

 

[NullPointer]

Noch eine Sache ist mir aufgefallen: Die ganzen Kombinationen, die du berechnest, kommen da, wo sie benutzt werden sollen (bei isValid() ... println()) gar nicht an, weil dieser Code außerhalb der Rekursion steht, alle Kombinationen aber in der Rekursion berechnet werden. D. h. du gibst einmal TTTT aus, nextState() returnt einmal true, visitors sind dann aber schon FFFF, danach ist nextState() false und das wars.

 

[hubertus1990]

Könnte jemand diesen Fall (Quelle Wikipedia) anhand eines Boolean arrays mit 4 Werten nachprogrammieren: "Stufe" ist der Index im Array, also 0-3, "Vektor" sei das boolean array mit 4 Werten.

Dies ist genau die Lösungsvariante die ich suche, allerdings probiere ich nun schon seit Ewigkeiten, diese in Java umzusetzen, komme aber auf keine Lösung.

Ziel dieser Funktion ist es, eine Kombination aus boolean Werten zu finden, und diese Zurückzugeben. Beim nächsten Aufruf wird die nächste mögliche Kombination zurückgegeben.
z.B.: erster Aufruf: TTTT, zweiter Aufruf: FTTT, dritter Aufruf: FFTTT usw, bis das alle möglichen Variationen ausgegeben wurden.

Funktion FindeLoesung (Stufe, Vektor)
  1. wiederhole, solange es noch neue Teil-Lösungsschritte gibt:
     a) wähle einen neuen Teil-Lösungsschritt;
     b) falls Wahl gültig ist: // wahl ist dann gültig, wenn diese kombination zuvor noch nicht ausgegeben wurde
               I) erweitere Vektor um Wahl;
              II) falls Vektor vollständig ist, return true; // Lösung gefunden!
                  sonst:
                       falls (FindeLoesung(Stufe+1, Vektor)) return true; // Lösung!
                       sonst mache Wahl rückgängig; // Sackgasse (Backtracking)!
  2. Da es keinen neuen Teil-Lösungsschritt gibt: return false // Keine Lösung!

 

[Darlis]

Dein Problem ist, wie ich auch schon angesprochen habe, Zeile 5, bzw. 1b: falls Wahl gültig ist
Dort schreibst du aber wahl ist dann gültig, wenn diese kombination zuvor noch nicht ausgegeben wurde.
1. Prüfst du hier nicht auf einen "gültigen" Wert sonder nur auf visitors == true, 2. müsstest du für dein Vorhaben alle ausgegebenen Werte speichern und mit dem jetzigen vergleichen.

Wie gesagt, Backtracking ist für dein Problem nicht geeignet. Ich würde einen anderen Algorithmus nehmen. Weißt du, wie man eine binäre Zahl hochzählt?

 

[NullPointer]

Die Binärzahl-Idee finde ich auch gut. Hier ist eine einfache Umsetzung:

        for (int i = 0; i <= 15; ++i) {
    		visitors[0] = (i & 8) > 0;
    		visitors[1] = (i & 4) > 0;
    		visitors[2] = (i & 2) > 0;
    		visitors[3] = (i & 1) > 0;
        	// if (isValid(...)) usw.
    	}

 

[Darlis]

Schleifen sind doch langweilig, warum keine Rekursion?
(Als Aufgabe für den TE)

 

[hubertus1990]

Ich habe die ganze sache jetzt iterativ implementiert, ähnlich wie NullPointer vorgeschlagen hat

So ist es natürlich einfach, dennoch reizt mich die rekursive Lösung

 

[Darlis]

Dann mach' es! Nur so lernst du programmieren und hier insbesondere die Rekursion besser zu verstehen.

 

[hubertus1990]

Ich habe schon des öfteren Rekursionsmethoden programmiert, und habe eingentlich auch keine Probleme damit gehabt. Aber dieses gesamte Backtracking Konzept ist mir nicht ganz klar