Unterschiede

Hier werden die Unterschiede zwischen zwei Versionen der Seite angezeigt.

--- faecher:informatik:oberstufe:algorithmen:rekursion:backtracking:start [22.01.2025 14:48] – Marco Kuemmel
+++ faecher:informatik:oberstufe:algorithmen:rekursion:backtracking:start [22.01.2025 14:51] (aktuell) – Marco Kuemmel
@@ Zeile 7: / Zeile 7: @@
 {{ :faecher:informatik:oberstufe:algorithmen:rekursion:backtracking:backtracking_tree.png?600|}}
 Am rechten Baum sieht man, wie man sich das Backtracking vorstellen kann. Man beginnt an der Wurzel und probiert zunächst immer die linken Pfade aus. In diesem Fall gibt es beim ''U'' die erste (rot dargestellte) Regelverletzung (die ist diesem Beispiel nicht genauer erklärt sei). Man ist daher gezwungen, wieder einen Knoten zurück zu gehen und den nächsten Nachbarknoten (sofern vorhanden) zu testen. ''J'' ist eine legitime Lösung. Auch jetzt geht man wieder so weit zurück zu den Elternknoten, bis es einen weiteren Nachbarzweig gibt, den man ausprobieren kann. Am Ende hat man herausgefunden, dass ''J'', ''P'' und ''V'' legitime Lösungen darstellen.
+Der **Clou der Sache** ist, dass man bei den roten (abgebrochenen) Knoten wegen der Regelverletzung auch gar nicht mehr deren Kinderknoten anschauen muss (sofern vorhanden)! Eine Regelverletzung schließt also mit etwas Glück automatisch zahlreiche weitere Knoten aus. Das spart verständlicherweise sehr viel Zeit!
 Die folgenden komplexen Probleme sind Beispiele, die sich mit Backtracking mit erstaunlich wenig Code schnell lösen lassen.