Backtracking

[Baume]

Hallo Leute,
ich bin was programmieren angeht noch eher ein Anfänger und hoffe ihr könnt mir bei einem Problem helfen. Ich versuche gerade ein Problem zu lösen, das sehr ähnlich dem Färbeproblem von Landkarten ist. Also man hat ein 2 dim. Array und man soll jedes benachbarte Feld jeweils anders einfärben. Mein Ansatz ist dabei backtracking, allerdings setze ich wohl den Ansatz meines Professors falsch um, denn es funktioniert nicht ganz.
Das Problem ist, dass er einfach nur durch die rekursiven Aufrufe nach unten geht und da er bis zum Ende immer einfärben kann, läuft dann die Schleife nicht weiter. Ich weiß jetzt nicht genau, wie ich den Algorithmus dazu kriege, für jede Reihe auch durch alle Spalten, also in die Breite zu gehen.
Das ist meine Hauptfunktion:

	private boolean complete(int h ){
		//fertig?
		System.out.println("complete..");
		if(h == ROWS)
			return true;
		
		boolean success = false;
		int b = 0;
		//Cloth temp = getCloth(h, b);
		while ((b < COLS) && !success){
			System.out.println("COLS = "+COLS);
			Cloth tempCloth = getCloth(h, b);
			System.out.println("b = "+b);
			if(isValidPosition(tempCloth, h, b)){
				placeCloth(tempCloth, h, b);
				success = complete(h+1);
				if(!success)
					removeCloth(h, b);	
			}
			b++;
			System.out.println("b++");
		}
		return success;
	}

Für Vorschläge bin ich sehr dankbar. Alle meine Ideen sind bisher im Sand verlaufen...
schonma danke im Vorraus!

 

[SlaterB]

an deinem Code ist nicht viel zu erkennen, was bedeuten die Variablen, was macht er?
hat Cloth etwas mit Farbe zu tun? tempCloth wird von Position b, h gelesen (wieso schon da?)
und dann wieder geschrieben oder auch nicht, von Wahl einer Farbe ist nichts zu sehen,
passiert das in getCloth()?

die Ausgabe der Konstanten COLS in Zeile 11 in jedem Schleifendurchlauf neu irritiert, ist der Wert nicht bekannt, reicht nicht EINE Ausgabe?

----

jeder Aufruf von complete() behandelt eine Zeile von COLS Elementen, es gibt bei dir nur eine Rekursionstiefe von ROWS,
dann musst vor dem rekursiven Aufruf die gesamte Zeile befüllen, b muss komplett bis COLS laufen, alle Felder einen Wert erhalten,
dann erst wird complete() für die nächste Zeile aufgerufen,

falls false zurückkommt, so muss die eigene Zeile geändert werden, denn es gibt für so eine lange Zeile ja sicher mehrere Belegungsmöglichkeiten,
wichtig ist, dass egal ob ein Elemente der Zeile oder fast alle verändert werden, erst wenn die eigene Zeile komplett bereit ist, dann wieder rekursiv zur nächsten wechseln

einfacher ist das was du zur Hälfte vermischt eingebaut hast: nur ein einzelnes Feld ändern, und dann schon die Rekursion aufrufen,
dann musst du aber für jedes Feld einzeln einen Rekursionsschritt aufrufen, etwa

complete(h, b) {
  int nexth, nextb = .. // Indexe der nächsten Zelle, Zeilenwechsel bedenken
  for (alle (hier noch sinnvollen) Farben) {
    setze Farbe in eigenes Feld
    complete(nexth, nextb);
  }
}

alternativ zu zwei Indexen kann man auch alle Felder von 1 bis n durchnummerieren,
dann hat man es hier in der obersten Logik einfacher, muss aber in den Prüfroutinen auf benachbarte Felder erst ausrechnen, wer denn die Nachbarn sind

 

[Baume]

h und b sind jeweils "Höhe" und "Breite" des Arrays. Die Ausgaben hatte ich nur zu Fehlersuchzwecken eingebaut.
Also ich hab jetzt die Funktion so abgewandelt wie du vorgeschlagen hast, zumindest wenn ich das richtig verstanden habe. Cloth ist ein selbstdefinierter Datentyp von mir, da man laut Aufgabe quasi einen Quilt nähen soll mit Stoffresten und man hat eine Auswahl unterschiedlicher Stoffe mit begrenzter Anzahl. Deswegen wird darin die Art und die Restmenge gespeichert. Diese Stoffe sollen außerdem auch noch einigermaßen zufällig ausgewählt werden. Das passiert dann alles in der "getCloth" Funktion.
Meine neue Hauptfunktion sieht jetzt so aus:

	private boolean complete2(int h, int b){
		//fertig?
		System.out.println("complete for ["+h+"|"+b+"]");
		boolean success = false;
		
		int nextH = 0, nextB = 0;
		if(h < ROWS){
			System.out.println("h++");
			nextH = h+1;
			nextB = b;
		}
		if(h == ROWS && b < COLS){
			System.out.println("b++");
			nextB = b+1;
			nextH = 0;
		}
		
		while (isPossible(h, b)){
			Cloth tempCloth = getCloth(h, b);
			if(isValidPosition(tempCloth, h, b)){
				placeCloth(tempCloth, h, b);			
				if(h == ROWS && b == COLS)
					return true;			
				success = complete2(nextH, nextB);
				if(!success)
					removeCloth(h, b);	
			}
		}
		return success;
	}

Jetzt geht er schonmal das ganze Array durch, er setzt zwar meine Vorgaben noch nicht 100% um (hat einen Fehler gemacht und 2 benachbarte Felder waren gleichartig), aber ich denke das ich da in einer Unterfunktion einen kleinen Fehler gemacht habe, denn das backtracking sollte doch prinzipiell so funktionieren, oder?
Er sucht sich einen "Stofffetzen" aus, schaut nach ob man in gültig platzieren kann, wenn ja platziert er ihn und macht weiter. Entsteht dann in irgendeiner Rekursionstiefe ein Fehler, werden solange alle bereits platzieren Reste wieder entfernt und neue gesetzt, bis es wieder stimmt.

Edit: isPossible schaut nach, ob überhaupt noch ein Stoffetzen gefunden werden kann
hatte ohne diese Funktion eine Endlosschleife zur Folge.
Jetzt hört er aber wenn er fertig ist nicht ganz richtig auf.

Aber schonma danke für deine Tipps. Ich glaube ich sollte das bald alles richtig haben!

 

[SlaterB]

die while-Schleife in Zeile 18 läuft für meinen Geschmack etwas zu lange,
wenn ein Durchlauf nicht zum Erfolg führt, was macht dann der nächste besser?
liefert das nächste Mal getCloth(h, b) etwas anderes? woher weiß diese Methode das?

es kann durchaus sein bzw. ist ganz normal, dass ein Rekursionsaufruf sich die Nägel ausbeist und ohne Ergebnis false zurückgibt
(sonst bräuchte es ja gar keine Verzweigung),
ergo muss es ein return false; geben oder return success; mit success == false, deine while-Schleife verhindert dies aber

siehe dagegen mein Mini-Beispiel Zeile 3-6, erst die aktuell möglichen Kombinationen bestimmen, das muss ja möglich sein,
dann diese alle genau einmal ausprobieren, falls nicht zwischendurch Erfolg dann Schulterzucken und return false; oder so

 

[Baume]

getCloth liefert jedes mal etwas anderes, da ich eine selbstgebaute random funktion nutze, die eben dieses mehr oder weniger zufällig angeordnete verwirklichen soll
hier mal der Code:

	private Cloth getCloth(int h, int b){
		boolean found = false;
		ArrayList<Cloth> triedCloth = new ArrayList<Cloth>();
		Cloth tempCloth = new Cloth(h+1,b+1);//Fehler Stoffstück keins gefunden
		while(!found){
			//System.out.println("final search..");
			found = true;
			tempCloth = moreOrLessRandomCloth(triedCloth);
			if(!isValidPosition(tempCloth, h, b)){
				//System.out.println("validPosition?"+isValidPosition(tempCloth, h, b));
				found = false;
				triedCloth.add(tempCloth);
			}
		}
		//System.out.println("finaly found");
		return tempCloth;
	}
	private Cloth moreOrLessRandomCloth(ArrayList<Cloth> triedCloth){
		boolean found = false;
		Cloth temp = new Cloth(0,0);
		ArrayList<Integer> exeptions = new ArrayList<Integer>();
		int tempNumber = 0;
		int start = clothPool.length/3 * 2;
		while(!found){
			//System.out.println("not found..");
			found = true;
			//sinnvoll neue suchen
			if(exeptions.size() > (clothPool.length - start) - clothPool.length/10)
				start -= clothPool.length/3;
			if(start < 0)
				start = 0;
				
				
			tempNumber = myOwnRandom(start, clothPool.length-1, exeptions);
			temp = clothPool[tempNumber];
			for(Cloth c : triedCloth){
				if (c == temp){
					found = false;
					exeptions.add(tempNumber);					
				}
					
			}
			if(temp.getAmount() < 1){
				found = false;
				exeptions.add(tempNumber);
			}
		}
		//System.out.println("found");
		return temp;
		
	}
	private int myOwnRandom(int start, int end ,ArrayList<Integer> exeptions){
		boolean found = false;
		int temp = 0;
		while (!found) {
			found = true;
			temp = start + ((int)(Math.random() * (end - start + 1)));
			for(int i : exeptions){
				if(temp == i)
					found = false;
			}
		}
		return temp;
	 
	}

is vermutlich etwas kompliziert gedacht, aber ich dachte so müsste as funktionieren

Und du hast recht, er produziert am Ende immer eine Endlosschleife, ich geh mal auf Fehlersuche

 

[SlaterB]

den Fehler hab ich ja mehr oder weniger erklärt,
in den allermeisten Situation sind sämtliche mögliche Werte falsch, jedenfalls bei normalen Backtracking, da gibts auch nicht wirklich Random,
sondern alle noch verfügbaren Varianten werden der Reihe nach durchprobiert

man muss wissen wann man aufhören kann

-----

wenn du eine feste Liste von möglichen Dingen hast, kannst du von mir aus in zufälliger Reihenfolge durchprobieren (für das aktuelle Feld),
aber nur eine Liste von 1 bis n durchmischen, nicht manche mehrfach probieren..