Bei der Erstellung der Unterlagen wurden KI Assistenten (insbesondere Claude
aber ggf. auch ChatGPT, Ollama mit Gemma/LLama/Qwen oder OpenCode mit
Kimi/Qwen/Deepseek...) unterstützend eingesetzt.
Dies erfolgte insbesondere zur Unterstützung bei der Generierung von Grafiken
(d. h. SVG Dateien), oder um sich Übersichtstabellen generieren zu lassen.
Weiterhin wurde KI zur allgemeinen Qualitätssicherung eingesetzt.
Inhalte, die ggf. von der KI vorgeschlagen wurden, wurden im Falle der
Übernahme explizit validiert und angepasst.
Backtracking
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)
Ziel ist es vier Damen auf einem Schachbrett so zu platzieren, dass keine Dame eine andere Dame schlagen kann.
Eine Lösung für ein 4x4 Schachbrett
1
2
3
4
1
D
2
D
3
D
4
D
1procedure findeStellung(i : integer)// i: Spalte 2 j :=0// j: Zeile 3repeat 4{ wähle nächste Zeile j } 5if Dame an Position i / j bedroht
6 keine bisher platzierte Dame then 7{ platziere Dame in Feld i / j } 8if i =4then 9{ Lösung gefunden }10{ Ausgabe der Lösung }11else12 findeStellung(i +1)// rek. Aufruf13{ entferne Dame aus Spalte i und Zeile j }// zurücksetzen des Zustands14until{ alle Zeilen j getestet }
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 5, 6).
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 9, 10).
Die Methode wird rekursiv aufgerufen, um die Lösung zu vervollständigen (Zeile 12).
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.
1from abc import abstractmethod
2 3classExpr: 4 5@abstractmethod 6defis_solution( 7 self, 8 binding:dict["Var",bool])->bool|None: 9"""TrueorFalseif this expression definitively
10 evaluates to the respective truth value with the
11 given binding orNone 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 21is returned. 22 23 An expression such as"A ⋀ B" would returnTrue 24if A and B are both Truein the
25 binding andFalseif at least one of them is bound
26 to False,andNone otherwise. 27"""
28raise NotImplementedError
29 30 31classAnd(Expr): 32def__init__(self,*exprs: Expr): 33 self.exprs = exprs
34 35defis_solution(self, binding): 36 r =True 37for expr in self.exprs: 38 e = expr.is_solution(binding) 39if e isNone: 40 r =None 41elifnot e: 42returnFalse 43return r
44 45def__str__(self): 46return" ⋀ ".join(str(expr)for expr in self.exprs) 47 48def__repr__(self): 49 exprs =", ".join(str(expr)for expr in self.exprs) 50return"And("+ exprs +")" 51 52 53classOr(Expr): 54def__init__(self,*exprs: Expr): 55 self.exprs = exprs
56 57defis_solution(self, binding): 58 r =False 59for expr in self.exprs: 60 e = expr.is_solution(binding) 61if e isNone: 62 r =None 63elif e: 64returnTrue 65return r
66 67def__str__(self): 68return" ⋁ ".join(str(expr)for expr in self.exprs) 69 70def__repr__(self): 71 exprs =", ".join(repr(expr)for expr in self.exprs) 72return"Or("+ exprs +")" 73 74 75classNot(Expr): 76def__init__(self, expr: Expr): 77 self.expr = expr
78 79defis_solution(self, binding): 80 e = self.expr.is_solution(binding) 81if e isNone: 82returnNone 83else: 84returnnot e
85 86def__str__(self): 87returnf"¬{self.expr}" 88 89def__repr__(self): 90return"Not("+repr(self.expr)+")" 91 92 93classVar(Expr): 94def__init__(self, name:str): 95 self.name = name
96 97defis_solution(self, binding): 98"""TrueorFalseif bound. 99Noneif unbound (default).100"""
101if self notin binding:102returnNone103else:104return binding[self]105106def__str__(self):107return self.name
108109def__repr__(self):110return'Var("'+ self.name +'")'111112113A = Var("a")114B = Var("b")115C = Var("c")116D = Var("d")117vars=[A, B, C, D]118""" The variables are now indexed to enable iterating over
119 them in the solve function."""
120121expr = 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)128print("Finding solutions for: "+ expr.__str__())129130solution:dict[Var,bool]={}131""" Stores the current solution by mapping the name of a
132 variable to its current truth value (TrueorFalse)."""
133134135defsolve(expr,vars):
Java Template
1 2// Intended to be run using Java > 23 (Tested with Java 23 and 24) 3// May require --enable-preview to do so. 4 5interfaceExpr{ 6 7/** 8*AnOptionalTrue or OptionalFalseifthis expression
9* definitively evaluates tothe respective truth value
10*withthe given binding or an empty Optional otherwise. 11* 12*Returning a truth value does not necessarily
13* require all variables tobe bound toa definite
14*value. For example,Optional.empty will be returned, 15*if the truth value cannot be determined withthe given
16*binding. E. g.,ifthis expression represents a
17* variable for which the binding has no value, 18*Optional.empty is returned. 19* 20*An expression such as "A ⋀ B" would returntrue 21*ifA and B are both bound to"true" and false 22*if at least one of them is bound
23*to"false", and Optional.empty otherwise. 24*/ 25Optional<Boolean>isSolution(Map<Var,Boolean> binding); 26} 27 28classAndimplementsExpr{ 29 30privatefinalExpr[] exprs; 31 32And(Expr... exprs){ 33this.exprs = exprs; 34} 35 36publicOptional<Boolean>isSolution(Map<Var,Boolean> binding){ 37Optional<Boolean> r =Optional.of(true); 38for(var expr :this.exprs){ 39finalvar e = expr.isSolution(binding); 40if(!e.isPresent()) 41 r =Optional.empty(); 42elseif(!e.get()) 43return e; 44} 45return r; 46} 47 48publicStringtoString(){ 49returnArrays.stream(exprs) 50.map(Expr::toString) 51.collect(Collectors.joining(" ⋀ ")); 52} 53} 54 55classOrimplementsExpr{ 56 57privatefinalExpr[] exprs; 58 59Or(Expr... exprs){ 60this.exprs = exprs; 61} 62 63publicOptional<Boolean>isSolution(Map<Var,Boolean> binding){ 64var r =Optional.of(false); 65for(var expr :this.exprs){ 66finalvar e = expr.isSolution(binding); 67if(!e.isPresent()) 68 r =Optional.empty(); 69elseif(e.get()) 70return e; 71} 72return r; 73} 74 75publicStringtoString(){ 76returnArrays.stream(exprs) 77.map(Expr::toString) 78.collect(Collectors.joining(" ⋁ ")); 79} 80} 81 82classNotimplementsExpr{ 83 84privatefinalExpr expr; 85 86Not(Expr expr){ 87this.expr = expr; 88} 89 90publicOptional<Boolean>isSolution(Map<Var,Boolean> binding){ 91finalvar r = expr.isSolution(binding).map(b ->!b); 92return r; 93} 94 95publicStringtoString(){ 96return"¬"+ expr; 97} 98} 99100classVarimplementsExpr{101102privatefinalString name;103104Var(String name){105this.name = name;106}107108publicOptional<Boolean>isSolution(Map<Var,Boolean> binding){109finalvar r =Optional.ofNullable(binding.get(this));110return r;111}112113publicStringtoString(){114return name;115}116117}118119voidmain(){120finalVarA=newVar("a");121finalVarB=newVar("b");122finalVarC=newVar("c");123finalVarD=newVar("d");124Stack<Var> vars =newStack<>();125 vars.addAll(Arrays.asList(newVar[]{A,B,C,D}));126Expr expr =newAnd(127newOr(A,B),128newOr(newNot(A),B),129newOr(newNot(A),newNot(C)),130newOr(C,D),131newOr(newNot(C),newNot(D)));132IO.println("Finding solutions for: "+ expr.toString());133134Map<Var,Boolean> solution =newHashMap<>();135solve(expr, vars, solution);136}137138voidsolve(Expr expr,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):