Was ist der Unterschied zwischen Top-Down und Bottom-Up in der dynamischen Programmierung?
Top-Down löst das Problem rekursiv mit Memoization, Bottom-Up löst es iterativ mit einer Tabelle.
Wann wird bei Top-Down ein Wert berechnet?
Nur dann, wenn er gebraucht wird (Lazy Evaluation).
Was ist ein Nachteil des Top-Down-Ansatzes?
Kann zu einem Stack Overflow führen, wenn die Rekursion zu tief wird.
Was ist ein Vorteil des Bottom-Up-Ansatzes?
Alle Teilprobleme werden systematisch und effizient gelöst, ohne Rekursion.
Was bedeutet 'Memoization'?
Das Zwischenspeichern von bereits berechneten Ergebnissen, um doppelte Berechnungen zu vermeiden.
Welche Probleme eignen sich gut für dynamische Programmierung?
Probleme mit optimaler Teilstruktur und überlappenden Teilproblemen, z.B. Rucksack, Fibonacci, Münzwechsel.
Wie erkennt man, ob dynamische Programmierung anwendbar ist?
Wenn sich das Problem in kleinere, sich wiederholende Teilprobleme zerlegen lässt, die sich überlappen.
Was passiert bei Bottom-Up mit den vorherigen Werten?
Sie werden in einer Tabelle gespeichert und schrittweise weiterverwendet.
Welcher Ansatz ist rekursiv: Top-Down oder Bottom-Up?
Top-Down.
Welcher Ansatz verwendet meist eine Schleife: Top-Down oder Bottom-Up?
Bottom-Up.
Welche Schrittfunktion wird typischerweise bei Simulated Annealing verwendet?
Die Nachbarschaft wird meist zufällig durchsucht (Random Neighbor)
Was ist das Metropolis-Kriterium?
Das Metropolis-Kriterium ist die Regel
Wie funktioniert das Metropolis-Kriterium formal?
Eine Zufallszahl Z ∈ [0
Was bedeutet eine hohe Temperatur bei Simulated Annealing?
Bei hoher Temperatur ist die Wahrscheinlichkeit auch deutlich schlechtere Lösungen zu akzeptieren größer. Das erlaubt eine breite Erkundung des Lösungsraums zu Beginn der Suche.
Wie verändert sich die Temperatur im Laufe der Zeit?
Die Temperatur sinkt typischerweise geometrisch oder adaptiv was bedeutet dass die Wahrscheinlichkeit schlechtere Lösungen zu akzeptieren mit der Zeit abnimmt.
Was ist adaptives Abkühlen?
Beim adaptiven Abkühlen wird die Abkühlrate abhängig vom Fortschritt angepasst – etwa abhängig davon wie viele Verbesserungen in letzter Zeit erzielt wurden.
Welche Parameter sind beim SA entscheidend?
Wichtige Parameter sind die Anfangstemperatur die Abkühlrate und die Anzahl der Iterationen pro Temperaturstufe. Sie beeinflussen maßgeblich die Qualität und Geschwindigkeit der Suche.
Wofür eignet sich Simulated Annealing besonders?
SA eignet sich für Probleme mit vielen lokalen Optima und schwierigen Suchräumen wie TSP oder Graph-Partitionierung da es die Suche nicht auf lokale Verbesserungen beschränkt.
Wie kann die Nachbarschaft in SA angepasst werden?
Je nach Problem können Flip- Swap- oder Austauschoperationen gewählt werden. Eine kleinere Nachbarschaft führt zu schnellerer aber ggf. weniger effektiver Suche.
Was ist das Hauptprinzip der Tabu-Suche?
Tabu-Suche verhindert Wiederholungen indem sie kürzlich besuchte Zustände verbietet. Dadurch kann sie lokale Optima überwinden und den Suchraum breiter erkunden.
Was ist die Tabuliste?
Eine Datenstruktur die kürzlich durchgeführte Änderungen oder Zustände speichert die vorübergehend tabu sind um Zyklen zu vermeiden.
Was wird typischerweise in der Tabuliste gespeichert?
Statt vollständiger Lösungen werden meist sogenannte Tabuattribute gespeichert z. B. Variablenänderungen oder Züge.
Was ist die Best-Improvement-Schrittfunktion?
In jeder Iteration wird die beste erlaubte Nachbarlösung gewählt – auch wenn sie schlechter als die aktuelle Lösung ist. Dies hilft aus lokalen Optima herauszukommen.
Was ist das Aspirationskriterium?
Eine Regel die es erlaubt eine eigentlich verbotene Lösung zu akzeptieren z. B. wenn sie besser ist als alle bisher gefundenen.
Warum ist die Länge der Tabuliste wichtig?
Eine zu kurze Liste erlaubt Zyklen eine zu lange verhindert gute Bewegungen. Die richtige Länge ist entscheidend für eine effektive Suche.
Was ist Reactive Tabu Search?
Eine Variante der Tabu-Suche bei der sich die Tabulistenlänge dynamisch anpasst – etwa basierend auf Wiederholungen oder Fortschritt.
Wie wird die Nachbarschaft bei Tabu-Suche angepasst?
Die erlaubten Nachbarn sind diejenigen die keine verbotenen Attribute enthalten – außer das Aspirationskriterium greift.
Was sind typische Probleme für Tabu-Suche?
Schwierig zu optimierende Probleme wie das Graphfärbungsproblem -TSP- Scheduling oder kombinatorische Probleme mit vielen lokalen Optima.
Wie wird Diversifikation in Tabu-Suche erreicht?
Durch Variation der Nachbarschaften oder gezielte Bewegungen in weniger untersuchte Regionen.
Was ist das Grundprinzip evolutionärer Algorithmen?
Evolutionäre Algorithmen imitieren natürliche Selektion: Lösungen entwickeln sich durch Selektion' Rekombination und Mutation über viele Generationen.
Was versteht man unter Selektion?
Gute Lösungen haben eine höhere Chance` Eltern für neue Lösungen zu sein. Dies steigert die Qualität der Population über Zeit.
Wie funktioniert Roulette-Wheel-Selektion?
Jede Lösung bekommt eine Chance proportional zu ihrer Fitness. Bessere Lösungen werden häufiger ausgewählt` aber auch schlechtere können Eltern werden.
Was ist der Selektionsdruck?
Ein Maß für die Ungleichverteilung der Selektionswahrscheinlichkeit. Ein zu hoher Druck reduziert Vielfalt` ein zu niedriger verlangsamt die Suche.
Was ist Tournament-Selektion?
Mehrere Lösungen werden zufällig gewählt` und die beste davon wird selektiert. Das steuert den Selektionsdruck ohne Fitness-Skalierung.
Was ist der Zweck der Mutation?
Sie bringt neue zufällige Veränderungen ein und hilft die Population vielfältig zu halten und neue Regionen zu erkunden.
Was ist der Zweck der Rekombination?
Elternlösungen werden kombiniert` um neue Lösungen zu erzeugen` die gute Eigenschaften von beiden Eltern übernehmen.
Wie funktioniert 1-Point-Crossover bei Bitstrings?
Ein zufälliger Punkt wird gewählt`an dem die Eltern ihre Teile tauschen` um ein neues Individuum zu erzeugen.
Wie wird die Fitness bei Minimierungsproblemen angepasst?
Die Bewertungsfunktion wird skaliert oder transformiert` um sie für Selektion kompatibel zu machen`z. B. durch Umkehrung oder lineare Transformation.
Wie kann man evolutionäre Algorithmen verbessern?
Durch Kombination mit lokaler Suche (Memetische Algorithmen) oder Einsatz von problemspezifischen Mutations- und Rekombinationsoperatoren.
Last changed13 days ago