1
Q
Beschreib die dynamische Programmierung
A
2
Q
Was sind die Entwicklungsschritte der dynamischen Programmierung?
A
- Charakterisiere die Struktur einer optimalen Lösung
- Definiere den Wert einer optimalen Lösung rekursiv (Die Umsetzung in einen rekursiven Algorithmus würde zu einem Top-Down-Ansatz führen)
- Berechne den Wert einer optimalen Lösung mit einem Bottom-Up- Ansatz (Speichere dabei die bereits berechneten Teillösungen)
- Konstruiere eine zugehörige optimale Lösung
3
Q
Welche Eigenschaften müssen Probleme für die dynamische Programmierung haben?
A
- Optimale Teilstruktur :Optimale Lösung kann ausoptimalen Teillösungen konstruiert werden. Die optimalen Teillösungen können unabhängig voneinander bestimmt werden.
- Überlappende Teilprobleme: Es gibt eine (polynomielle) Anzahl von Teilproblemen, deren Lösungen immer wieder zur Lösung größerer Teilprobleme herangezogen werden.
