Wegpunkt wird nicht zur History einer Tiefensuche hinzugefügt

[kirchrath]

Hallo,
Seit Tagen bin ich jetzt am überlegen und bin gestern auf eine relativ schnelle Lösung gekommen - doch leider ist am Ende ein Schritt nicht in dem Lösungsweg registriert.
Es geht um eine Matrix mit einer beliebigen Zahl an Zeichenpärchen. Um herauszufinden ob die Matrix auf die erlaubte Art zu leeren ist, habe ich mir überlegt zu schauen, welche Züge aktuell möglich sind, den ersten zu nehmen, diesen durchzuführen und auf der Nächsten ebene zu schauen welche möglich sind- ist die Matrix leer bin ich fertig, wenn nicht und es gibt keine Möglichen Züge gehe ich einen Schritt zurück und nehme dort den zweiten Weg....
Am Schluss sagt er mir, dass es eine Möglichkeit gibt - wann ich nun an einem Punkt angekommen bin und es nicht geht, weiß ich noch nicht.
Das was das größte Problem darstellt ist, dass in meiner Liste für den Lösungsweg ein Zug fehlt - und damit ist die ganze Liste kaputt.

Die Methode die das alles berechnen sollte sieht so aus:

• LevelParser ist ein Object das die Matrix beinhaltet.
• lpHistory speichert die LevelParser objekte ab die entstanden sind - wird ein schritt zurückgegangen wird entsprechend dort gelöscht (hier ist der Hund begraben - manchmal wird zu viel gelöscht, der nächste schritt der Berechnung fängt aber dort an, wo er sein sollte)
• setSol berechnet aus dem unterschied der Matrizen die Schritte die gegangen wurden

private void solverLogic() throws ParameterOutOfRangeException, SyntacticIncException{
		boolean couldBeSolved = true;
		LevelParser lpObject = this.lpObject.clone();
		LinkedList<int[][]> apm;
		int positionToUse = 0;
		while(!solvable || couldBeSolved)
		{
			apm = getActualPossibleMoves(lpObject.clone());
			if(apm.size()>0){
				if(positionToUse>apm.size())
				{
					couldBeSolved = false;
					break;
				}
				LevelParser genL = easyMove(lpObject,apm.get(positionToUse));
				this.lpHistory.add(genL.clone());
				if(Move.isSolved(genL))
				{
					this.solvable = true;
					break;
				}else
				{
					lpObject = genL.clone();
				}
				if(positionToUse>0) {
					positionToUse--;
				}
			}else{
				this.lpHistory.removeLast();
				LevelParser lpTMPObject = this.lpHistory.removeLast();
				lpObject = lpTMPObject.clone();
				positionToUse++;
			}
		}
		setSol(this.lpObject.clone(),this.lpHistory);
	}

Wäre toll, wenn jemand helfen könnte.
Gruß
Kirchrath

PS: Das ist ein teil eines Projektes und ich kann leider nicht alles veröffentlichen - ich möchte auch keine komplettcodes sondern würde mich darüber freuen, wenn mir jemand erklären könnte, wieso er den Fehler macht....

 

[JanHH]

Inhaltlich verstehe ich fast nur Bahnhof, aber spontan fällt mir dazu ein:

- der Algorithmus, den Du skizzierst, ist ein brute-force-"alles ausprobieren"-Algorithmus. Vom zeitlichen Verhalten her ist das nicht praktikabel. Wenn man an die Geschichte mit den Reiskörnern auf einem Schachbrett erinnert.. von Feld zu Feld die Anzahl verdoppeln. Führt bei 8x8 Feldern zu 2 hoch 64 Reiskörnern bzw. Iterationen, die der Algorithmus durchlaufen muss, um alle Züge zu prüfen. Das ist nicht in normaler Rechenzeit machbar.

- Wenn man es doch so machen will, handelt es sich um einen rekursiven Algorithmus, und den sollte man dann auch so implementieren. Das reduziert den Verwaltungs-Overhead doch sehr. Würde dann so aussehen:

1. Finde alle möglichen Züge im aktuellen Zustand der Matrix und speichere sie in einer Liste.
2. Gehe in einer Schleife diese Liste durch. Führe den jeweiligen Zug aus, erstelle eine Kopie der Matrix in dem Zustand, in dem sie dann ist, und rufe diese Funktion dann für diese Matrix erneut auf.

Da wird dann entweder irgendwann die Funktion feststellen "fertig", oder, wenn das die ganze Zeit nicht passiert, am Ende halt "es gibt keine Lösung".

 

[kirchrath]

Danke für die Antwort. Als Bruteforce würde ich es nicht bezeichnen, da er zuvor über einen anderen Algorithmus genau herausfinden welche Züge valide sind (diese werden über Objektbeziehungen der einzelnen Punkte errechnet - nicht ausprobiert) und dann wird der erste Mögliche Zug genommen und das entsprechende Ergebnis wiederum in gewisser Weise rekursiv aufgerufen. Ich habe das gleiche bereits einmal rekursiv implementiert und hatte damit eine deutlich höhere Laufzeit.

Würde mich freuen, wenn jemand auf den Quellcode eingehen könnte und mir sagen könnte wieso er ein Ergebnis auslässt.

Gruß
kirchrath


Edit: ich hab jetzt eine Lösung gefunden die aber nicht auf dem alten Code sondern auf einem entsprechenden der Rekursion verwendet.