Neben der dynamischen Programmierung ist das Backtrack-Prinzip ein weiteres grundlegendes Verfahren zur Lösung von Problemen.
Backtracking ist ein Verfahren, das in vielen Algorithmen zur Anwendung kommt. Insbesondere, wenn kein effizienterer Algorithmus bekannt ist, als alle möglichen Lösungen auszuprobieren.
Backtracking ist eine systematische Methode, um alle möglichen Lösungen eines Problems zu finden. Es ist eine Art von rekursivem Durchsuchen, bei dem Teillösungen zu Gesamtlösungen erweitert werden.
Backtracking erlaubt ggf. Heuristiken, um die Suche zu beschleunigen.
Weder die Komplexitätsklasse noch die Korrektheit ändert sich dadurch.
Viele NP-harte Probleme werden mit Backtracking gelöst.[1]
Backtracking führt eine erschöpfende Suche durch, um eine Lösung zu finden. Kann aber auch direkt genutzt werden, um ggf. alle Lösungen zu finden.
Backtracking ist in Prolog inherent vorhanden, da Prolog auf dem Prinzip des Backtrackings basiert, weswegen Prolog für die Lösung solcher Probleme gut geeignet ist.
Beispiel: Das 4-Damen Problem (konzeptuell)
1 // i: Spalte; j: Zeile 2 procedurefindeStellung(i:integer) 3 j:=0 4 repeat 5 { wähle nächste Zeile j } 6 ifDameanPositioni/jbedroht 7 keinebisherplatzierteDamethen 8 { platziere Dame in Feld i / j } 9 ifi=4then10 { Lösung gefunden }11 { Ausgabe der Lösung }12 else13 findeStellung(i+1)// rek. Aufruf14 { entferne Dame aus Spalte i und Zeile j }// zurücksetzen des Zustands15 until{ alle Zeilen j getestet }
Ziel ist es vier Damen auf einem Schachbrett so zu platzieren, dass keine Dame eine andere Dame schlagen kann.[2] Eine Lösung:
1
2
3
4
1
D
2
D
3
D
4
D
Wesentliche Elemente:
Die Lösung ist endlich.
Die Lösung wird iterativ aufgebaut. Es ist jederzeit möglich zu testen, ob die bisherige Lösung noch gültig ist (Zeile 6, 7).
Ist eine Lösung nicht mehr möglich, wird die Teillösung auch nicht weiter verfolgt.
Wurde eine Lösung gefunden, wird sie ausgegeben (Zeile 10, 11).
Die Methode wird rekursiv aufgerufen, um die Lösung zu vervollständigen (Zeile 13).
Backtracking - Allgemein
Voraussetzungen für Backtracking
Die Lösung ist als Vektor a[1],a[2],... endlicher Länge darstellbar.
Jedes Element a[i] hat eine endliche Anzahl von möglichen Werten A[i].
D. h. die Menge der möglichen Werte pro a[i] kann unterschiedlich sein.
Es gibt einen effizienten Test, ob eine Teillösung a[1],a[2],...,a[k] zu einer gültigen Lösung führen kann.
Verfahren
Start:
Wähle eine Teillösung a[1].
Allgemein:
Ist eine Teillösung basierend auf a[1],a[2],...,a[k-1] noch keine Gesamtlösung, dann erweitere sie mit dem nächsten nicht ausgeschlossenen Wert a[k] aus A[k] zur neuen Teillösung a[1],a[2],...,a[k].
Falls noch nicht alle Elemente von A[K], die zu keiner inkonsistenten Lösungen führen, ausgeschöpft sind, dann gehe zurück (backtrack) und wähle a[k] neu. Ggf. gehe zu a[k-1] usw. zurück.
Es wird hier nicht gefordert, dass alle Element den gleichen Wertebereich haben. Es ist auch möglich, dass die Werte unterschiedlich sind.
Bestimmen Sie für folgenden Ausdruck c - mittels Backtracking - Wahrheitswerte für die Variablen, damit der Ausdruck als Ganzes wahr wird:
c = (A ∨ ¬B) ∧ (¬A ∨ B) ∧ (¬A ∨ ¬C) ∧ (C ∨ D) ∧ (¬C ∨ ¬D)
Füllen Sie dazu die folgende Tabelle aus, um alle Lösungen zu finden. In der letzten Spalte geben Sie an, ob die Zeile eine Teillösung darstellt (nicht inkonsistent), keine Lösung ist bzw. sein kann, oder eine Gesamtlösung identifiziert wurde. Die Evaluation wie vieler vollständiger Belegungen wurde eingespart, wenn die Lösung gefunden wurde?
A
B
C
D
nicht inkonsistent (T), keine Lösung (K), vollständige Lösung (L)
Ein logischer Ausdruck ist in KNF, wenn der Ausdruck nur als Konjunktion (UND-Verknüpfung) von Disjunktionen (ODER-Verknüpfungen) dargestellt wird. Die Negation darf nur auf Variablen angewendet werden.
Beispiel: (A ∨ B ∨ C) ∧ (¬C ∨ D)
Entwickeln Sie ein Programm — in einer Programmiersprache Ihrer Wahl — das in der Lage ist eine Formel in konjunktiver Normalform (KNF) auf Erfüllbarkeit zu prüfen.
Prüfen Sie Ihr Programm anhand der vorhergehenden Aufgabe.
1 fromabcimportabstractmethod 2 3 classExpr: 4 5 @abstractmethod 6 defis_solution( 7 self, 8 binding:dict["Var",bool])->bool|None: 9 """True or False if this expression definitively
10 evaluates to the respective truth value with the
11 given binding or None otherwise.
12 13 Returning a truth value does not necessarily
14 require all variables to be bound to a definite
15 value.
16 17 For example, None will be returned, if the
18 truth value cannot be determined with the given
19 binding. E. g., if this expression represents a
20 variable for which the binding has no value, None
21 is returned.
22 23 An expression such as "A ⋀ B" would return True
24 if A and B are both True in the
25 binding and False if at least one of them is bound
26 to False, and None otherwise.
27 """ 28 raiseNotImplementedError 29 30 31 classAnd(Expr): 32 def__init__(self,*exprs:Expr): 33 self.exprs=exprs 34 35 defis_solution(self,binding): 36 r=True 37 forexprinself.exprs: 38 e=expr.is_solution(binding) 39 ifeisNone: 40 r=None 41 elifnote: 42 returnFalse 43 returnr 44 45 def__str__(self): 46 return" ⋀ ".join(str(expr)forexprinself.exprs) 47 48 def__repr__(self): 49 exprs=", ".join(str(expr)forexprinself.exprs) 50 return"And("+exprs+")" 51 52 53 classOr(Expr): 54 def__init__(self,*exprs:Expr): 55 self.exprs=exprs 56 57 defis_solution(self,binding): 58 r=False 59 forexprinself.exprs: 60 e=expr.is_solution(binding) 61 ifeisNone: 62 r=None 63 elife: 64 returnTrue 65 returnr 66 67 def__str__(self): 68 return" ⋁ ".join(str(expr)forexprinself.exprs) 69 70 def__repr__(self): 71 exprs=", ".join(repr(expr)forexprinself.exprs) 72 return"Or("+exprs+")" 73 74 75 classNot(Expr): 76 def__init__(self,expr:Expr): 77 self.expr=expr 78 79 defis_solution(self,binding): 80 e=self.expr.is_solution(binding) 81 ifeisNone: 82 returnNone 83 else: 84 returnnote 85 86 def__str__(self): 87 returnf"¬{self.expr}" 88 89 def__repr__(self): 90 return"Not("+repr(self.expr)+")" 91 92 93 classVar(Expr): 94 def__init__(self,name:str): 95 self.name=name 96 97 defis_solution(self,binding): 98 """True or False if bound.
99 None if unbound (default).
100 """101 ifselfnotinbinding:102 returnNone103 else:104 returnbinding[self]105 106 def__str__(self):107 returnself.name108 109 def__repr__(self):110 return'Var("'+self.name+'")'111 112 113 A=Var("a")114 B=Var("b")115 C=Var("c")116 D=Var("d")117 vars=[A,B,C,D]118 """ The variables are now indexed to enable iterating over
119 them in the solve function. """120 121 expr=And(122 Or(A,B),123 Or(Not(A),B),124 Or(Not(A),Not(C)),125 Or(C,D),126 Or(Not(C),Not(D)),127 )128 print("Finding solutions for: "+expr.__str__())129 130 solution:dict[Var,bool]={}131 """ Stores the current solution by mapping the name of a
132 variable to its current truth value (True or False)."""133 134 135 defsolve(expr,vars):
Java Template
1 // Intended to be run using Java > 23 (Tested with Java 23 and 24) 2 // May require --enable-preview to do so. 3 4 interfaceExpr{ 5 6 /**
7 * An Optional True or Optional False if this expression
8 * definitively evaluates to the respective truth value
9 * with the given binding or an empty Optional otherwise.
10 *
11 * Returning a truth value does not necessarily
12 * require all variables to be bound to a definite
13 * value. For example, Optional.empty will be returned,
14 * if the truth value cannot be determined with the given
15 * binding. E. g., if this expression represents a
16 * variable for which the binding has no value,
17 * Optional.empty is returned.
18 *
19 * An expression such as "A ⋀ B" would return true
20 * if A and B are both bound to "true" and false
21 * if at least one of them is bound
22 * to "false", and Optional.empty otherwise.
23 */ 24 Optional<Boolean>isSolution(Map<Var,Boolean>binding); 25 } 26 27 classAndimplementsExpr{ 28 29 privatefinalExpr[]exprs; 30 31 And(Expr...exprs){ 32 this.exprs=exprs; 33 } 34 35 publicOptional<Boolean>isSolution(Map<Var,Boolean>binding){ 36 Optional<Boolean>r=Optional.of(true); 37 for(varexpr:this.exprs){ 38 finalvare=expr.isSolution(binding); 39 if(!e.isPresent()) 40 r=Optional.empty(); 41 elseif(!e.get()) 42 returne; 43 } 44 returnr; 45 } 46 47 publicStringtoString(){ 48 returnArrays.stream(exprs) 49 .map(Expr::toString) 50 .collect(Collectors.joining(" ⋀ ")); 51 } 52 } 53 54 classOrimplementsExpr{ 55 56 privatefinalExpr[]exprs; 57 58 Or(Expr...exprs){ 59 this.exprs=exprs; 60 } 61 62 publicOptional<Boolean>isSolution(Map<Var,Boolean>binding){ 63 varr=Optional.of(false); 64 for(varexpr:this.exprs){ 65 finalvare=expr.isSolution(binding); 66 if(!e.isPresent()) 67 r=Optional.empty(); 68 elseif(e.get()) 69 returne; 70 } 71 returnr; 72 } 73 74 publicStringtoString(){ 75 returnArrays.stream(exprs) 76 .map(Expr::toString) 77 .collect(Collectors.joining(" ⋁ ")); 78 } 79 } 80 81 classNotimplementsExpr{ 82 83 privatefinalExprexpr; 84 85 Not(Exprexpr){ 86 this.expr=expr; 87 } 88 89 publicOptional<Boolean>isSolution(Map<Var,Boolean>binding){ 90 finalvarr=expr.isSolution(binding).map(b->!b); 91 returnr; 92 } 93 94 publicStringtoString(){ 95 return"¬"+expr; 96 } 97 } 98 99 classVarimplementsExpr{100 101 privatefinalStringname;102 103 Var(Stringname){104 this.name=name;105 }106 107 publicOptional<Boolean>isSolution(Map<Var,Boolean>binding){108 finalvarr=Optional.ofNullable(binding.get(this));109 returnr;110 }111 112 publicStringtoString(){113 returnname;114 }115 116 }117 118 voidmain(){119 finalVarA=newVar("a");120 finalVarB=newVar("b");121 finalVarC=newVar("c");122 finalVarD=newVar("d");123 Stack<Var>vars=newStack<>();124 vars.addAll(Arrays.asList(newVar[]{A,B,C,D}));125 Exprexpr=newAnd(126 newOr(A,B),127 newOr(newNot(A),B),128 newOr(newNot(A),newNot(C)),129 newOr(C,D),130 newOr(newNot(C),newNot(D)));131 IO.println("Finding solutions for: "+expr.toString());132 133 Map<Var,Boolean>solution=newHashMap<>();134 solve(expr,vars,solution);135 }136 137 voidsolve(Exprexpr,Stack<Var>vars,Map<Var,Boolean>solution){
Übung
Gruppenzuteilung
Finden Sie eine sehr gute Aufteilung von Personen (Studierenden) auf eine feste Anzahl an Gruppen, basierend auf den Präferenzen der Personen zueinander. Nutzen Sie dazu Backtracking.
Im Template ist eine initiale Aufgabenstellung hinterlegt, die es zu lösen gilt: Verteilung von 16 Studierenden auf 4 Gruppen inkl. Bewertungsmatrix (jeder Studierende hat jeden anderen mit Werten von 1 bis 10 bewertet):