Disclaimer: Dieser Thread wurde aus dem alten Forum importiert. Daher werden eventuell nicht alle Formatierungen richtig angezeigt. Der ursprüngliche Thread beginnt im zweiten Post dieses Threads.
Dynamische Programmierung/Gierige Algroithmen
Kann mir jemand die dynamische Programmierung erklären wie hängt das Bottom up mit dem Lookup zusammen oder das Topdown mit dem Look up ?
wie muss man das implementieren ?
In den Übungsflolien ist es nur schwammig erklärt!
andere Frage ist wie muss man Gierige Algorithmen implementiern nach Floyd/Dijkstra/Prim/Kruskal?
Bottom up: lookup auf bereits sicher vorher errechnete ergebnisse
Top down: lookup nach ergebnissen, abstieg falls noch nicht errechnet, dann weiter rechnen mit Ergebnis
Meinst nach einem pseudo code, oder was das gierige in der Implementierung ist?
Top down ist eine Rekursion so wie ich es verstanden habe.
Bottom up mit Look up und Top down mit Look up immer bei DP.
Man braucht immer ein Array zum zwischenspeichern wieso muss man das Array mit n+1 initialisieren ?
zu Gierige Algorithmen:
wäre gut wenn man es erklären könnte mit einem evtl Pseudocode
Wie meinst du das genau? Grundsätzlich speicherst du Werte ab, z.B. in einem Array.
Je nachdem was du berechnen möchtest bietet sich nun ein Bottom-Up(Tabulation) oder Top-Down Approach an, meistens gehen aber beide Varianten. Ich würde dir empfehlen Altklausuren zu diesem Aufgabentyp durchzuarbeiten und dich dadurch an verschiedene Herangehensweisen zu gewöhnen.
1. Top-Down Approach: Hier beginnst du bei der Eingabe n selbst und berechnest die Zahlen “topdown”
z.B. für die n-te Fibonacci-zahl.
Angenommen wir würden die 7.te Fibonacci-Zahl finden wollen, dann ist 7 hier “Top” und wir fragen rekursiv immer:
7.te Fibonacci Zahl: Was ist nun die Summe aus der 6.ten und der 5.ten?
Die 6.te: Was ist nun die Summe aus der 5.en und der 4.e?
Die 5.te: Was ist die Summe aus der 4.en und der 3.en?
Die 4.te: aus der 3.en und der 2.en?
Die 3.te aus der 2.en und der 1.en?
Glücklicherweise wissen wir aber unsere Basisfälle. Unser Wert für Stelle 1 und 2 beträgt 1.
Daraus können wir dann wieder nach oben rechnen und kommen irgendwann beim Wert an der 7. Stelle an, den wir ja ursprünglich wissen wollten.
Das war jetzt die normale Rekursion. Wie du aber oben siehst, fragen wir mehrmals nach den gleichen Werten. Der Computer merkt sich diese aber nicht - so wie wir Menschen es tun würden, sondern berechnet diese jedes Mal wenn er gefragt wird von neuem was natürlich viel Zeit kostet.
Mit dynamischer Programmierung möchten wir dem Computer die Fähigkeit geben sich die Werte die er schonmal berechnet hat zu merken, dass er nicht nochmal neu rechnen muss wenn er nochmal gefragt wird, sondern einfach in seinem Notizblock (im unteren Beispiel der array table nachsehen kann. Dieser Schritt ist der Lookup. Der Computer schaut im Array nach “habe ich diesen Wert schonmal berechnet?” statt den Wert direkt neu zu berechnen.
(Das ist nicht nur bei Rekursion hilfreich, sondern auch bei iterativen Berechnungen, dazu gibt es auch Aufgaben in den Altklausuren.)
Kurz: wir fangen von der obersten Zahl an zu rechnen, wie in diesem Beispiel zur Berechnung der Fibonacci-Zahlen aus der TÜ.
public static long fibMem(int n) {
long[] table = new long[n+1]; // Tabelle für die Memoization
return fibMemHelper(n, table);
}
private static long fibMemHelper(int n, long[] table) {
// Lookup
if (table[n] != 0) {
return table[n];
}
long result;
if (n == 1 || n == 2) {
result = 1;
} else {
result = fibMemHelper(n-1, table) + fibMemHelper(n-2, table);
}
// Memoization
table[n] = result;
return result; }
2. Bottom-Up Approach a.k.a Tabulation
Hier sieht der Look-Up etwas anders aus. Man muss nicht überprüfen ob der Wert bereits berechnet wurde, da man ja immer aus vorherigen Zahlen den direkt nächsten Wert berechnet. Wir müssen hier nicht mehr abfragen, ob der Wert bereits berechnet wurde, da wir die Werte der Reihe nach aufsteigend in unseren Array abspeichern.
Allerdings rechnet man jetzt von unten(bottom) hoch zum Ergebnis.
Hier mal eine Iterative Lösung, statt rekursiv:
public static int fibBottomUp(int n){
int[] table = new int[n+1];
table[1] = 1;
table[2] = 1; //Was vorher beim Top-Down Approach unsere Basisfaelle waren,
//fuellen wir jetzt direkt am Beginn in unsere SpeicherTabelle
//Diese SpeicherTABELLE fuellt sich beim Bottom-Up Approach von unten auf,
//woher der Name Tabulation vermutlich kommt.
for(int i=3; i<=n; i++){
//Das Loop startet bei 3, da ich ja schon an Stelle 1 und 2 einen Wert gesetzt habe ;)
table[i] = table[i-1] + table[i-2];
//der nächste Wert setzt sich aus dessen VorVorgaenger und VorVorgaenger zusammen.
}
return table[n];
}Ich hoffe das hat dir geholfen, evtl. kann ja jemand mit einem umfassenderen Blick die Sache noch ein bisschen besser auf den Punkt bringen.
Zu deiner Frage zu gierigen Algorithmen und der Implementierung der Graphalgorithmen würde ich dir empfehlen einen separaten Thread zu eröffnen, dass macht die Sache übersichtlicher.
Liebe Grüße,
Speedy
2 „Gefällt mir“
Jetzt hab ich das Prinzip genauer verstanden
danke
Zur Array-Initialisierung:
angenommen du würdest in deinem Array im rahmen des Methodenablaufs die Werte 1,2,3,4 (n=4) speichern wollen:
dann hast du üblicherweise diese Zwei Optionen:
1.)
du initialisierst den array als: int[] a = new int[n];
und speicherst die vier Werte so:
a[0] = 1;
a[1] = 2;
a[2] = 3;
a[3] = 4;
2.) [code]
du initialisierst den array als: int[] a = new int[n+1];
und speicherst die vier Werte so:
a[0] = null;
a[1] = 1;
a[2] = 2;
a[3] = 3;
a[4] = 4;
[/code]
Der Vorteil bei der zweiten Variante ist, dass du in darauffolgenden Berechnungen, wie zum Beispiel bei der obigen iterativen Berechnung der Fibonacci-Zahlen:
a[i]=a[i-1] + a[i-2]
schreiben kannst. Das i entspricht also dem Wert der an der Stelle
a[i]
gespeichert ist.
Bei der ersten Version müsstest du schreiben:
a[i-1] = a[i-2] + a[i-3]
und das for-loop als auch die Intialisierung des arrays mit den “Basiswerten” ändern.
LG
Speedy