Dynamische Programmierung

Question 1

Beschreib die dynamische Programmierung

Answer 1

Question 2

Was sind die Entwicklungsschritte der dynamischen Programmierung?

Answer 2

1. Charakterisiere die Struktur einer optimalen Lösung
2. Definiere den Wert einer optimalen Lösung rekursiv (Die Umsetzung in einen rekursiven Algorithmus würde zu einem Top-Down-Ansatz führen)
3. Berechne den Wert einer optimalen Lösung mit einem Bottom-Up- Ansatz (Speichere dabei die bereits berechneten Teillösungen)
4. Konstruiere eine zugehörige optimale Lösung

Question 3

Welche Eigenschaften müssen Probleme für die dynamische Programmierung haben?

Answer 3

• 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.