E-Commerce

1. Optimale Unterstruktur: Ein Problem hat eine optimale Unterstruktur, wenn eine optimale Lösung des Problems Teiloptima seiner Teilprobleme umfasst. Dies bedeutet, dass die Lösung eines größeren Problems sich direkt aus den Lösungen seiner Teilprobleme zusammensetzt.

2. Überlappende Teilprobleme: Im Gegensatz zum reinen "Divide and Conquer", wo die aufgeteilten Probleme unabhängig voneinander sind (z.B. bei der Mergesort-Sortierung), sind die Teilprobleme bei der dynamischen Programmierung nicht unabhängig. Das gleiche Teilproblem kommt in der Berechnung mehrmals vor. Deshalb ist das Speichern (Caching) der Lösungen essenziell.

3. Memoisierung (Top-Down-Ansatz): Bei diesem Ansatz wird meistens ein rekursives Vorgehen gewählt. Sobald eine Lösung eines Teilproblems berechnet wird, speichert man diese in einer Tabelle (oder einem anderen Speicherformat), um zu verhindern, dass die Lösung bei einem weiteren Auftreten nochmals berechnet wird.

4. Tabellierung (Bottom-Up-Ansatz): Hier fängt man mit den kleinsten Teilproblemen an und verwendet deren Lösungen, um größere Teilprobleme zu lösen. Dieser Ansatz führt zur Iteration über die Teilproblemgrößen und füllt Stück für Stück eine Tabelle mit den Lösungen.

Ein zusätzlicher wichtiger Punkt zur dynamischen Programmierung ist, dass sie nicht nur dazu verwendet wird, den Wert einer optimalen Lösung zu finden, sondern auch dazu, die Lösung selbst zu rekonstruieren. Nachdem die Tabelle mit den Problemlösungen erstellt wurde, kann oft durch Rückverfolgung (Backtracking) innerhalb dieser Tabelle die Entscheidungskette oder das Objekt, das die optimale Lösung repräsentiert, rekonstruiert werden.

Die Wahl zwischen Top-Down- und Bottom-Up-Ansätzen hängt von verschiedenen Faktoren ab, darunter die spezifische Problemstellung und die persönliche Präferenz des Entwicklers. Manchmal kann die Bottom-Up-Methode schneller sein, da sie repetitive Funktionsaufrufe vermeidet, die beim rekursiven Top-Down-Ansatz auftreten können.

Die Effektivität der dynamischen Programmierung macht sie zu einem wichtigen Werkzeug im Bereich des algorithmischen Designs und in vielen praktischen Anwendungen wie in der Bioinformatik (z.B. bei der Sequenzalignment), der Optimierung, in der Netzwerktheorie und vielen anderen Feldern.