Backtracking - Versionsgeschichte

Akaibel: /* Erklärvideos */

2023-01-16T17:54:16Z

Erklärvideos

← Nächstältere Version		Version vom 16. Januar 2023, 17:54 Uhr
Zeile 4:		Zeile 4:
	<font color='red'>'''nur relevant für den Leistungskurs!'''</font>		<font color='red'>'''nur relevant für den Leistungskurs!'''</font>
	= Erklärvideos =		= Erklärvideos =

	* [https://youtu.be/XG3qgot1SGY Sudokus mit Backtracking lösen: Teil 1 - Planung]

	* [https://youtu.be/SYqT_r4jMGE Sudokus mit Backtracking lösen: Teil 2 - Java Implementierung]

	* [https://youtu.be/dYwatqXIUkw Rucksackproblem mit Backtracking lösen: Java Implementierung]		* [https://youtu.be/dYwatqXIUkw Rucksackproblem mit Backtracking lösen: Java Implementierung]

Akaibel am 23. Januar 2022 um 17:53 Uhr

2022-01-23T17:53:43Z

← Nächstältere Version		Version vom 23. Januar 2022, 17:53 Uhr
Zeile 21:		Zeile 21:
	''Die folgende Beschreibung ist gekürzt und leicht verändert aus der Wikipedia [http://de.wikipedia.org/wiki/Backtracking] übernommen. ''		''Die folgende Beschreibung ist gekürzt und leicht verändert aus der Wikipedia [http://de.wikipedia.org/wiki/Backtracking] übernommen. ''

	<code>		<code>
	Teillösung ist zu Anfang leer.		Teillösung ist zu Anfang leer.
	Stufe ist 0.		Stufe ist 0.
Zeile 35:		Zeile 35:
	c) rekursiver Aufruf: FindeLoesung(Stufe+1, Teillösung)		c) rekursiver Aufruf: FindeLoesung(Stufe+1, Teillösung)
	d) Mache die Erweiterung der Teillösung rückgängig		d) Mache die Erweiterung der Teillösung rückgängig
	</code>		</code>

	= Backtracking für kürzeste Wege auf Graphen =		= Backtracking für kürzeste Wege auf Graphen =
Zeile 63:		Zeile 63:
	Mithilfe dieser lässt sich der Algorithmus so beschreiben:		Mithilfe dieser lässt sich der Algorithmus so beschreiben:

	<code>		<code>
	'''findeKuerzestenWegBacktracking (pNode)'''		'''findeKuerzestenWegBacktracking (pNode)'''
	'''Abbruchbedingung:'''		'''Abbruchbedingung:'''
Zeile 79:		Zeile 79:
	- aktuelleDistanz wieder zurücksetzen		- aktuelleDistanz wieder zurücksetzen
	- die Markierung des Nachbarn entfernen		- die Markierung des Nachbarn entfernen
	</code>		</code>

	==Implementierung==		==Implementierung==
Zeile 90:		Zeile 90:
	* die '''rekursive Backtracking-Methode''' <code>kuerzestenWegFindenBacktracking(GraphNode pNode)</code>		* die '''rekursive Backtracking-Methode''' <code>kuerzestenWegFindenBacktracking(GraphNode pNode)</code>

	<code>		<code>
	'''// Attribute'''		'''// Attribute'''
	public GraphWithViewer graph;		public GraphWithViewer graph;
Zeile 161:		Zeile 161:
	return;		return;
	}		}
	</code>		</code>

	=Backtracking für Arrays: Magisches Quadrat=		=Backtracking für Arrays: Magisches Quadrat=
Zeile 176:		Zeile 176:
	* Das eigentliche Backtracking findet in der Methode <u><code>public void findeLoesung(int pStufe)</code></u> statt; diese Methode wird von der Rahmenmethode <code>public void findeLoesung()</code> aufgerufen.		* Das eigentliche Backtracking findet in der Methode <u><code>public void findeLoesung(int pStufe)</code></u> statt; diese Methode wird von der Rahmenmethode <code>public void findeLoesung()</code> aufgerufen.

	<code>		<code>
	public class MagischesQuadratFertig {		public class MagischesQuadratFertig {

Zeile 307:		Zeile 307:
	}		}
	}		}
	</code>		</code>

	=Aufgabe: Backtracking für Arrays: Rucksackproblem selber programmieren=		=Aufgabe: Backtracking für Arrays: Rucksackproblem selber programmieren=
Zeile 326:		Zeile 326:
	'''Viel Spaß beim Programmieren!'''		'''Viel Spaß beim Programmieren!'''

	<code>		<code>
	public class Rucksackproblem {		public class Rucksackproblem {
	public int[] '''gewichte''' = {28, 57, 33, 18, 99, 42, 17, 52};		public int[] '''gewichte''' = {28, 57, 33, 18, 99, 42, 17, 52};
Zeile 394:		Zeile 394:
	}		}
	}		}
	</code>		</code>
	=Aufgabe: Backtracking zum Lösen von Sudokus=		=Aufgabe: Backtracking zum Lösen von Sudokus=

Zeile 409:		Zeile 409:
	* Die "Stufe" beginnt nicht bei 0, sondern bei der Anzahl der belegten Felder. Dann kann der Backtracking-Algorithmus abbrechen, sobald man die Stufe 81 erreicht.		* Die "Stufe" beginnt nicht bei 0, sondern bei der Anzahl der belegten Felder. Dann kann der Backtracking-Algorithmus abbrechen, sobald man die Stufe 81 erreicht.

	<code>		<code>
	'''public class Sudoku {'''		'''public class Sudoku {'''

Zeile 612:		Zeile 612:
	}		}
	}		}
	</code>		</code>

Akaibel: /* Idee */

2020-05-26T13:44:27Z

Idee

← Nächstältere Version		Version vom 26. Mai 2020, 13:44 Uhr
Zeile 3:		Zeile 3:
	[[Kategorie:Algorithmen]]		[[Kategorie:Algorithmen]]
	<font color='red'>'''nur relevant für den Leistungskurs!'''</font>		<font color='red'>'''nur relevant für den Leistungskurs!'''</font>
			= Erklärvideos =

			* [https://youtu.be/XG3qgot1SGY Sudokus mit Backtracking lösen: Teil 1 - Planung]

			* [https://youtu.be/SYqT_r4jMGE Sudokus mit Backtracking lösen: Teil 2 - Java Implementierung]

			* [https://youtu.be/dYwatqXIUkw Rucksackproblem mit Backtracking lösen: Java Implementierung]

	= Idee =		= Idee =
	''Der folgende Text ist gekürzt aus der Wikipedia [http://de.wikipedia.org/wiki/Backtracking] übernommen. ''		''Der folgende Text ist gekürzt aus der Wikipedia [http://de.wikipedia.org/wiki/Backtracking] übernommen. ''

Akaibel: /* Aufgabe: Backtracking zum Lösen von Sudokus */

2020-04-09T07:14:01Z

Aufgabe: Backtracking zum Lösen von Sudokus

← Nächstältere Version		Version vom 9. April 2020, 07:14 Uhr
Zeile 393:		Zeile 393:
	Abhilfe schafft hier ein geeignetes Java-Programm!		Abhilfe schafft hier ein geeignetes Java-Programm!

	Die "langweiligen" Hilfsmethoden sind unten schon programmiert - es fehlt nur noch die Methode <code>loesenMitBacktracking()</code>.		Die "langweiligen" Hilfsmethoden sind unten schon programmiert - es fehlt nur noch die Methode <code>loesenMitBacktracking(int pStufe)</code>.

	<u>Hinweise</u>:		<u>Hinweise</u>:
Zeile 399:		Zeile 399:
	* Die "Teillösung" muss man nicht als Parameter der Backtracking-Methode übergeben, weil immer das Array <code>zahlen</code> entsprechend aktualisiert wird.		* Die "Teillösung" muss man nicht als Parameter der Backtracking-Methode übergeben, weil immer das Array <code>zahlen</code> entsprechend aktualisiert wird.

	* Die "Stufe" ~~muss man auch~~ nicht ~~als Parameter übergeben! Das liegt daran~~, ~~dass man als nächste "Stufe" immer das Feld wählen~~ kann, ~~wo es die wenigsten Möglichkeiten gibt (aber mehr als 0!!!)~~		* Die "Stufe" beginnt nicht bei 0, sondern bei der Anzahl der belegten Felder. Dann kann der Backtracking-Algorithmus abbrechen, sobald man die Stufe 81 erreicht.

	* Wenn man eine Lösung gefunden hat, dann gibt man die ~~aus und beendet das Programm mit <code>System.exit(0)</code><br/>Nicht gerade elegant, aber wirksam~~.

	<code>		<code>
	'''public class Sudoku {'''		'''public class Sudoku {'''

	// Das "schwerste Sudoku der Welt"		// Das "schwerste Sudoku der Welt"
	// https://www.oe24.at/welt/Das-ist-das-schwierigste-Sudoku-der-Welt/1597831		// https://www.oe24.at/welt/Das-ist-das-schwierigste-Sudoku-der-Welt/1597831
Zeile 418:		Zeile 417:
	{0,0,0,0,0,9,7,0,0}		{0,0,0,0,0,9,7,0,0}
	};		};

	'''public static void main(String[] args) {'''		'''public static void main(String[] args) {'''
	Sudoku s = new Sudoku();		Sudoku s = new Sudoku();
	System.out.println("* Aufgabe *");		System.out.println("* Aufgabe *");
	s.ausgeben();		s.ausgeben();
	s.loesenMitBacktracking();		int belegteFelder = s.belegteFelder();
			boolean erfolg = s.loesenMitBacktracking(belegteFelder);
			if(erfolg == true){
			System.out.println("Loesung gefunden!");
			}
			else{
			System.out.println("keine Loesung");
			}
			}

			'''public boolean loesenMitBacktracking(int pStufe){'''
			'''//TODO'''
			return false;
	}		}

Zeile 471:		Zeile 482:
	return true;		return true;
	}		}

	/**		/**
	* ueberprueft, ob das Quadrat ok ist,		* ueberprueft, ob das Quadrat ok ist,
Zeile 484:		Zeile 495:
	int startSpalte = pSpaltenNr - pSpaltenNr%3;		int startSpalte = pSpaltenNr - pSpaltenNr%3;
	//System.out.println("Start: ("+startZeile+"\|"+startSpalte+")");		//System.out.println("Start: ("+startZeile+"\|"+startSpalte+")");
			for(int zeile = startZeile; zeile<startZeile+3; zeile++){
	for(int zeile = startZeile; zeile<startZeile+3; zeile++){
	for(int spalte = startSpalte; spalte<startSpalte+3; spalte++){		for(int spalte = startSpalte; spalte<startSpalte+3; spalte++){
	int z= zahlen[zeile][spalte];		int z= zahlen[zeile][spalte];
Zeile 498:		Zeile 508:
	return true;		return true;
	}		}

	/**		/**
	* prueft, ob pZahl an der Position moeglich ist.		* prueft, ob pZahl an der Position moeglich ist.
Zeile 526:		Zeile 536:
	return true;		return true;
	}		}

			'''public int belegteFelder(){'''
			int ergebnis = 0;
			for(int zeile=0; zeile<9; zeile++){
			for(int spalte=0; spalte<9; spalte++){
			if(zahlen[zeile][spalte] != 0){
			ergebnis++;
			}
			}
			}
			return ergebnis;
			}

	/**		/**
	* berechnet, wie viele Moeglichkeiten es fuer dieses Feld gibt.		* berechnet, wie viele Moeglichkeiten es fuer dieses Feld gibt.
Zeile 548:		Zeile 570:
	return ergebnis;		return ergebnis;
	}		}

	/**		/**
	* bestimmt das Feld mit den wenigsten Moeglichkeiten.		* bestimmt das Feld mit den wenigsten Moeglichkeiten.
Zeile 571:		Zeile 593:
	return minFeld;		return minFeld;
	}		}

	/**		/**
	*		*
Zeile 580:		Zeile 602:
	'''public void eintragen(int zahl, int zeile, int spalte){'''		'''public void eintragen(int zahl, int zeile, int spalte){'''
	zahlen[zeile][spalte] = zahl;		zahlen[zeile][spalte] = zahl;
	}

	~~'''public void loesenMitBacktracking(){'''~~
	~~'''//TODO'''~~
	}		}
	}		}

	</code>		</code>

Akaibel: /* Aufgabe: Backtracking zum Lösen von Sudokus */

2020-04-08T22:15:59Z

Aufgabe: Backtracking zum Lösen von Sudokus

← Nächstältere Version		Version vom 8. April 2020, 22:15 Uhr
Zeile 404:		Zeile 404:

	<code>		<code>

	'''public class Sudoku {'''		'''public class Sudoku {'''
	// Das "schwerste Sudoku der Welt"		// Das "schwerste Sudoku der Welt"
Zeile 499:		Zeile 498:
	return true;		return true;
	}		}


	/**		/**
	* prueft, ob pZahl an der Position moeglich ist.		* prueft, ob pZahl an der Position moeglich ist.
Zeile 585:		Zeile 583:

	'''public void loesenMitBacktracking(){'''		'''public void loesenMitBacktracking(){'''

	'''//TODO'''		'''//TODO'''
	}		}

Akaibel: /* Implementierung zum Selbermachen */

2020-04-08T22:12:27Z

Implementierung zum Selbermachen

Änderungen zeigen

Akaibel am 29. März 2020 um 14:39 Uhr

2020-03-29T14:39:52Z

← Nächstältere Version		Version vom 29. März 2020, 14:39 Uhr
Zeile 2:		Zeile 2:
	[[Kategorie:Informatik-Abitur]]		[[Kategorie:Informatik-Abitur]]
	[[Kategorie:Algorithmen]]		[[Kategorie:Algorithmen]]
			<font color='red'>'''nur relevant für den Leistungskurs!'''</font>
	= Idee =		= Idee =
	''Der folgende Text ist gekürzt aus der Wikipedia [http://de.wikipedia.org/wiki/Backtracking] übernommen. ''		''Der folgende Text ist gekürzt aus der Wikipedia [http://de.wikipedia.org/wiki/Backtracking] übernommen. ''

Akaibel: /* Implementierung zum Selbermachen */

2020-03-29T12:58:49Z

Implementierung zum Selbermachen

← Nächstältere Version		Version vom 29. März 2020, 12:58 Uhr
Zeile 339:		Zeile 339:

	'''public void sucheBesteLoesung(int pStufe) {'''		'''public void sucheBesteLoesung(int pStufe) {'''
	~~dabeiArrayAusgeben~~();		teilLoesungAusgeben();
	'''//TODO'''		'''//TODO'''
	}		}
Zeile 353:		Zeile 353:
	}		}

	'''public void ~~dabeiArrayAusgeben~~(){'''		'''public void teilLoesungAusgeben(){'''
	for(int i=0; i<teilLoesung.length; i++){		for(int i=0; i<teilLoesung.length; i++){
	if(teilLoesung[i]){		if(teilLoesung[i]){

Akaibel: /* Implementierung zum Selbermachen */

2020-03-29T12:42:25Z

Implementierung zum Selbermachen

Änderungen zeigen

Akaibel: Akaibel verschob die Seite Backtracking ab Abi 2017 nach Backtracking

2018-09-03T06:32:50Z

Akaibel verschob die Seite Backtracking ab Abi 2017 nach Backtracking

← Nächstältere Version	Version vom 3. September 2018, 06:32 Uhr
(kein Unterschied)