Quote:
Originally Posted by The_Dentist
Ui, vielen DANK!
Gruß
€dit:
PHP Code:
if(add==true)
{
setsUsed[idxCoverage]=true;
}
else
{
setsUsed[idxCoverage]=false;
}
solveCoverageProblem(idxCoverage+1,true);
solveCoverageProblem(idxCoverage+1,false);
Diesen Part verstehe ich noch nicht ganz, wieso muss ich die Methode zwei mal aufrufen mit dem gleichen Index aber einmal mit true und einmal mit false? |
Die Idee des ganzen Algorithmuses sieht wie folgt aus:
Generiere jede mögliche Menge an Belegungen um alle Fächer zu überdecken, wenn man das also einmal für unsere Beispiel mit 3 Lehrern durchgeht probiert der Algorithmus das in folgender Art und Weise (in genaue dieser Reihenfolge):
als erstes wird die Lösung generiert bei der wir alle Lehrer benutzen, also die erste Lösung, die wir zwischen speichern ist:
Lehrer1 & Lehrer2 & Lehrer3
Als nächstes schauen wir die Lösung für Lehrer1 und Lehrer2 aber NICHT Lehrer3 an, also:
Lehrer1 & Lehrer2 & NICHT Lehrer3
Was nichts anderes ist als:
Lehrer1 & Lehrer2
Anschließend gehen wir (dank dem Backtracking-Verfahren) einen Schritt zurück.
Wir haben jetzt alle möglichen Lösungen dafür aufgestellt, dass Lehrer1 und Lehrer2 sicher genommen werden, aber wir wissen nicht ob Lehrer2 wirklich benötigt wird, also generieren wir als nächstes alle Lösungen wenn Lehrer2 nicht genommen wird, Lehrer1 also schon.
Dann hätten wir:
1. Lehrer1 & NICHT Lehrer2 & Lehrer3
2. Lehrer1 & NICHT Lehrer2 & NICHT Lehrer3
Jetzt sind wir aber davon ausgegangen, dass wir Lehrer1 sicher brauchen, also müssen wir auch noch alle Fälle betrachten, wo wir Lehrer1 nicht brauchen, was dann so aussähe:
1. NICHT Lehrer1 & Lehrer2 & Lehrer3
2. NICHT Lehrer1 & Lehrer2 & NICHT Lehrer3
3. NICHT Lehrer1 & NICHT Lehrer2 & Lehrer3
4. NICHT Lehrer1 & NICHT Lehrer2 & NICHT Lehrer3
Damit haben wir alle möglichen Kombinationen angeschaut, die es gibt und jetzt müssen wir uns nur während dem Anschauen merken welche Lösung am wenigstens Lehrer benötigt hat.
Nun zurück zur eigentlichen Frage:
"Wieso brauchen wir 2 Aufrufe?"
Die Antwort darauf muss man in 2 Teilen beantworten:
Teil 1:
Nicht jeder Algorithmus, der rekursiv arbeitet und das Problem löst benötigt 2 verschiedene Aufrufe. Es unterlag jetzt also meiner Willkür den Algorithmus so zu gestalten, dass wir 2 Aufrufe benutzen. Mein Hauptargument es so zu machen lag besonders bei der Kürze des Codes der entsteht, da ich das nur "schnell" zusammen schreiben wollte.
Laufzeit technisch ist mein Code eh eine Katastrophe (wie bereits angedeutet)
Teil 2:
Was genau machen die 2 Aufrufe jetzt genau?
Da wir, wie oben beschrieben, zuerst davon ausgehen dass wir alle Lehrer brauchen und dann schrittweise auch die Möglichkeiten durchgehen, wo wir nicht alle Lehrer brauchen bietet es sich an folgendes Vorgehen zu benutzen:
Gehe alle Lehrer durch und pro Lehrer gibt es 2 "neue" Pfade, die man verfolgen kann, um eine Lösung zu finden.
Einmal den Pfad: Der Lehrer ist Teil der Lösung und
den Pfad: Der Lehrer ist nicht Teil der Lösung
Daher auch die 2 Aufrufe, einmal verfolgen wir den Pfad weiter, wenn der Lehrer Teil der Lösung ist ( solveCoverageProblem(idxCoverage+1,true); ) und einmal wenn er nicht Teil der Lösung ist ( solveCoverageProblem(idxCoverage+1,false); )
Dementsprechend speichern wir in unserem bool Array dann auch false (der Lehrer gehört nicht zur aktuellen Lösung) bzw. true (der Lehrer gehört zur aktuellen Lösung).
Edit:
Wenn dus trotzdem nicht verstehst sag Bescheid, dann versuch ich dir das Ganze graphisch klar zu machen.
