Dynamische Programmierung ist keine schwarze Magie

Dynamische Programmierung ist keine Magie

• Dynamische Programmierung ist eine Technik zum Lösen komplexer Probleme, bei der man sie in kleinere Teilprobleme zerlegt.
• Diese Technik ist etwas Natürliches, und viele gängige Algorithmen wenden bei bestimmten Problemen dynamische Programmierung an.
• Um das Verständnis dynamischer Programmierung zu erleichtern, wird eine einfachere Einführung und eine ausführliche Erklärung geboten.

Klage

• Software Engineering ist bei der Benennung oft miserabel.
• Begriffe wie „Bootstrap“, „Daemon“, „Cascading Style Sheets“, „Cookie“ und „Künstliche Intelligenz“ sind vage oder irreführend.
• Auch der Begriff „dynamische Programmierung“ hat an sich nichts mit „dynamisch“ zu tun, sondern bezeichnet in Wirklichkeit eine Idee für den Entwurf von Algorithmen.

Grundlegendes Caching

• Wenn man versucht, ein Problem in kleine, ähnliche Teilprobleme zu zerlegen und so zu lösen, kann es passieren, dass dieselben kleinen Probleme mehrfach gelöst werden müssen.
• Am Beispiel der Fibonacci-Folge sieht man, dass eine einfache rekursive Funktion dieselben Berechnungen mehrfach wiederholt.
• Indem man Ergebnisse cacht (oder Memoization verwendet), lassen sich doppelte Berechnungen vermeiden.

Optimiertes Caching

• Mit Memoization bleibt die Rekursion erhalten, aber es wird nur das berechnet, was gerade benötigt wird.
• Stattdessen kann man auch so vorgehen, dass alles Benötigte im Voraus berechnet wird.
• Dieser Ansatz löst das Problem ohne rekursive Aufrufe, und genau das ist dynamische Programmierung.

Edit-Distanz

• Die Edit-Distanz zwischen zwei Strings ist die minimale Anzahl von Bearbeitungen, die nötig ist, um einen String in den anderen zu verwandeln.
• Die Edit-Distanz kann anhand von Zeichenersetzungen, Einfügungen und Löschungen berechnet werden und lässt sich mit dynamischer Programmierung effizient lösen.
• Man muss einen Weg finden, aus den Lösungen der kleinen Teilprobleme die Gesamtlösung abzuleiten.

Advent of Code, Tag 12

• In der Advent-of-Code-Aufgabe vom 12. Dezember 2023 muss ein 1D-Nonogramm gelöst werden.
• Das lässt sich per Brute Force lösen, hat aber exponentielle Komplexität.
• Stattdessen kann man dynamische Programmierung anwenden und das Problem effizient lösen.

Fazit

• Dynamische Programmierung ist nicht einfach, aber für die meisten Programmierer nicht unerreichbar.
• Wenn man versteht, wie sich ein Problem in kleinere Teilprobleme zerlegen lässt, kann man Memoization in vielen Situationen einsetzen, was gegenüber einer naiven Implementierung eine große Verbesserung bedeutet.
• Wer dynamische Programmierung beherrscht, versteht eine ganze Klasse von Algorithmen, kann Trade-offs besser einschätzen und weitere Optimierungen ermöglichen.

Meinung von GN⁺

• Dynamische Programmierung ist eine wichtige Technik, um komplexe Probleme effizient zu lösen. Statt rekursiver Ansätze werden Lösungen kleiner Teilprobleme gecacht, um doppelte Berechnungen zu vermeiden und die Performance deutlich zu verbessern.
• Dieser Artikel ist für Einsteiger im Software Engineering, die die Grundkonzepte dynamischer Programmierung verstehen möchten, sehr nützlich.
• Die Beispiele mit der Fibonacci-Folge und der Edit-Distanz helfen beim Verständnis der Konzepte und bieten einen guten Ausgangspunkt für die Anwendung auf reale Probleme.

[GN⁺]

Hacker-News-Kommentare

• Es ist gut, dass der Artikel Algorithmen der dynamischen Programmierung (DP) als Caching von Rekursion erklärt.

  • Eine rekursive Lösung zu finden, ist der beste Ausgangspunkt, um eine DP-Lösung zu finden.
  • Das Memoisieren einer rekursiven Lösung kann die Geschwindigkeit erheblich verbessern.
  • Wichtig ist nicht, dass der Aufrufbaum eine große Zahl von Teilproblemen hat, sondern dass es eine relativ kleine Zahl eindeutiger Teilprobleme gibt.

• Mir gefällt, dass der Artikel das Problem zuerst rekursiv angeht, dann schrittweise Caching hinzufügt und es anschließend auf die tatsächlich benötigte Cache-Größe reduziert.

  • Ich habe schon erlebt, dass ich festhing oder sehr viel Aufwand brauchte, wenn ich versucht habe, direkt eine Lösung mit dynamischer Programmierung zu finden.
  • Künftig werde ich mich zwingen, diesen schrittweisen Ansatz zu befolgen.

• Eine großartige Anwendung der dynamischen Programmierung ist das paarweise Alignment von Nukleinsäure-/Proteinsequenzen.

  • Beispiele sind Sequence Alignment, der Needleman-Wunsch-Algorithmus und der Smith-Waterman-Algorithmus.

• Es wird eine Erfahrung mit einem außergewöhnlich guten Professor für Algorithmen geteilt.

  • Der Professor hat an der UCLA studiert, und seine Vorlesung über dynamische Programmierung war herausragend.
  • Er begann mit einem einfachen Problem mit exponentieller Komplexität, zerlegte es in kleinere Probleme, reduzierte die Komplexität auf polynomial und wandte dann Memoization an, um sie auf lineare Komplexität zu senken.
  • Ich wünschte, ich könnte mich an die verwendeten Probleme erinnern.

• Es wird ein Link zu dem Artikel Dynamic Programming Is Not Black Magic geteilt.

  • Der Artikel ist wegen sehr vieler Zugriffe schwer erreichbar geworden (Hug of Death).

• Jemand, der Programmieren größtenteils autodidaktisch gelernt hat, sagt, dass er bei der Jobsuche nicht gewusst hätte, was gemeint ist, wenn man ihn im Vorstellungsgespräch aufgefordert hätte, dynamische Programmierung zu verwenden.

  • Zum Glück ist das nicht passiert, und weil er die Technik kannte, konnte er sie in mehreren Interviews einsetzen.

• Der Name „dynamische Programmierung“ wirkt möglicherweise nicht so, als stamme er aus dem Bereich Programmierung.

  • Tatsächlich hat er mit Optimierung zu tun und ist eine Methode zum Lösen von Entscheidungsproblemen in diskreter Zeit.
  • Dynamische Programmierung ist eine Methode, die durch die Definition der Wertfunktion V* die Dimensionalität eines Optimierungsproblems stark reduziert.

• Es wird die Frage aufgeworfen, ob es falsch ist, bei „dynamischer Programmierung“ nur an „Memoization“ zu denken.

  • Der fehlende Teil könnte sein, das Problem so geschickt zu zerlegen, dass Memoization effektiv eingesetzt werden kann.

• Dynamische Programmierung ist keine Black Magic; schwierig ist es, zu zeigen, dass sich etwas damit dynamisch programmieren lässt, und seine Korrektheit zu beweisen.

  • Genau wie bei Greedy-Algorithmen ist ein formaler Beweis mit mathematischer Induktion nötig.

• Zum Meistern der dynamischen Programmierung werden das DPV-Algorithmenbuch und der Udacity-Kurs des Georgia Institute of Technology empfohlen.

  • Durch das Üben mit konkreten Problemen kann man dynamische Programmierung lernen.