Zitat von
Cöster:
Ich hab bisher noch keine Erfahrung mit Backtracking gemacht. Könnte vielleicht jemand (z.B. der Unwissende oder auch jemand anders) hier mal eine Musterlösung (Code) präsentieren, die per Backtracking das Problem löst?
Dabei lern ich glaub ich am meisten, als wenn ich mir hier stundenlang vergebens den Kopf über etwas zerbreche, was man vll in ein paar Minuten lösen könnte.
Hi,
klar kann der Unwissende das, hab gerade mal getestet, komme auf wenig Zeilen (was nicht viel heißt!!!), die funktionieren. Das es wenig Zeilen sind heißt in dem Fall aber nur, dass ich schnell was hingeklatscht habe, da wäre der Lerneffekt gleich null (außer ich schreibe rüber "Was man nicht machen sollte!).
Aber das der Lerneffekt dann am größten ist, das zweifel ich doch mal stark an. Vorallem ist eine der Forenregeln (an die ich mich gerne zu halten versuche), dass hier keine HA gelöst werden. Also nicht persönlich nehmen, dass ich (noch?) keine Lösung poste. Immerhin habe ich jetzt eine Idee, was funktionieren sollte und die hab ich auch nicht nur von woanders kopiert. Also gibt es einen Weg, wie man auf die richtige Lösung kommen kann.
Das erste sind immer die Überlegungen, was man alles hat. In dem Fall gibt es ein Feld mit Daten, ich sag hier einfach mal es hat den Typ TIntegerDynArray (Array of Integer, uses Types), also ist ein Array mit variabler Länge, dass Zahlen enthält. Dann gibt es noch die Erbhaelfte, die gesucht wird. Die ist einfach die Haelfte der Summe aller Zahlen im Array (hier kann SumInt verwendet werden).
Ok, mehr hat man erstmal gar nicht, nennen wir also das Array Erbe und den gesuchten Betrag Erbhaelfte. Soweit wart ihr alle eh schon, ich möchte nur das klar ist, was ich wann meine.
So, der nächste Schritt ist dann die Überlegung, wie man rausfinden kann, ob eine der Teilsummen, die sich aus den Elementen des Arrays bilden lässt, der Erbhaelfte entspricht. Jetzt gibt es hier mehrere Möglichkeiten, aber auch die Vorgabe, dass es hier Backtracking sein muss. Also überlegt man sich, wie das Backtracking aussehen soll.
Die Überlegung ist dabei, dass das erste Element fest zur Lösung gehören muss (in einer der beiden Hälften muss die Zahl drin sein). Nun gibt es ja zwei Möglichkeiten:
- Man ist bereits fertig, das erste Element hat als Summe einfach schon die Erbhaelfte.
Man ist noch nicht fertig, also untersucht man das restliche Feld rekursiv.
Den ersten Schritt kann man so schon direkt in Delphi umsetzen, zum zweiten muss man sich noch weitere Überlegungen machen.
Im zweiten Fall versucht man nun alle Kombinationen der folgenden Elemente. Man hat also eine aktuelle Teilsumme, die bisher kleiner war als die Erbhaelfte und untersucht nun alle Zahlen die übrig bleiben. Ist eine Teilsumme dabei kleiner als die Erbhaelfte, so betrachtet man diese Teilsumme als neue aktuelle Teilsumme (rekursiv) und kann weiter machen.
Ist eine Teilsumme größer als die Erbhaelfte, braucht man nicht weitersuchen, diese Teilsumme ist falsch. Hier kann einfach die vorherige Lösung weitermachen.
Das ganze würde mit der Menge [5,9,3,1,8] einfach so aussehen:
Code:
// aktuelle Teilsumme ts
// neue aktuelle Teilsumme nts
// aktuell betrachteter Index i (Array 0 indiziert!)
ts = [5]
summe(5) = 5
// summe < Erbhaelfte
für alle i > 1 tue:
i = 1 -> nts = [5,9] // hier jetzt rekursiv weitermachen
// rekursiver Aufruf
ts = [5,9]
summe(5,9) > Erbhaelfte // also nicht weiter machen
// da hier noch für alle i aktiv:
i = 2 -> nts = [5,3]
// rekursiver Aufruf
ts = [5,3]
summe(5,3) < Erbhaelfte // also weiter
für alle i > 2 (vorheriges i + 1) tue:
i = 3 -> nts = [5,3,1]
// rekursiver Aufruf
ts = [5,3,1]
summe(5,3,1) < Erbhaelfte // also weiter
für alle i > 3 (vorheriges i + 1) tue:
i = 4 -> nts[5,3,1,8]
// rekursiver Aufruf
summe(5,3,1,8) > Erbhaelfte // also nicht weiter
i = 5 -> i > als Länge des Feldes // also nicht weiter
i = 4 -> nts = [5,3,8]
// rekursiver Aufruf
ts = [5,3,8]
summe(5,3,8) > Erbhaelfte, also nicht weiter
i = 5 -> i > als Länge des Feldes // also nicht weiter
i = 3 -> nts = [5,1]
...
So, jetzt steht hier der Code schon fast in Pseudocode. Es ist nicht mehr als die Überlegung, die man hat, wie hier das Backtracking aussieht. Man muss einfach nur eine aktuelle Teilsumme nehmen, ein neues Element hinzu tun und schauen ob das Element passt. Ist dies der Fall, macht man rekursiv weiter, sonst versucht man es mit dem nächsten Element.
Es ist wirklich nur die Idee von Backtracking, dass lässt sich auf alle Backtracking-Probleme so übertragen, man versucht etwas, prüft ob es so noch ok ist und wenn ja, dann kommt der nächste Schritt dazu, sonst versucht man etwas anderes. Hier mit der Einrückung soll noch mal die Hierachie veranschaulicht werden, wo der hinspringt. alles was auf der selben Höhe ist (also selber Abstand nach links) gehört zur gleichen Aufruf-Tiefe. Dass das Programm hier immer zurückspringt, wenn nichts gemacht wird, darum kümmert sich Delphi.
Es entspricht einfach dem
Delphi-Quellcode:
doFoo(x : Integer);
begin
if (x > 0) then
begin
doFoo(x-1);
end;
end;
Wobei hier x > 0 der Rekursionsanker ist (sonst hätte man unendlich viele Aufrufe). Ruft man das so auf, mit x = 1, dann wird Delphi hier doFoo(1-1) Aufrufen und auf das Ergebnis warten. Ist doFoo(1-1) berechnet, springt kennt doFoo(1) das Ergebnis und kann weiter machen (wobei hier nichts weiter passiert).
Man sollte also immer auch über einen solchen Anker (wann ist man fertig) nachdenken und nie in eine Rekursion springen, bevor dieser Anker geprüft wurde (sonst kann es eine endlose Rekursion geben, gut endet im Stack-Overflow).
Für das Erb-Problem ist natürlich klar, dass man fertig ist (mit dem Zweig) wenn man eine gültige Lösung hat, die das Problem löst oder wenn der aktuelle Zweig eine ungültige Lösung enthält, die nicht mehr zum Erfolg führen kann (zu klein und keine weiteren Elemente verfügbar oder bereits zu groß und keine neg. Zahlen erlaubt).
Hoffe das hilft weiter (denke die Aufrufe und Abfragen die schon fast Pseudocode sind sollten da einiges erklären).
Trotzdem, bei Unklarheiten ruhig nachfragen, taucht häufiger und gerne auf.
Gruß Der Unwissende