In der Ausgabe 09/2013 der dotnetpro habe ich einen Artikel (Flotte Magie, Seite 45-51) über den Ansatz der Dynamischen Programmierung zur Lösung von Berechnungsproblemen veröffentlicht. Leider konnte ich zu dem Zeitpunkt nicht den gesamten Beispielcode dazu legen. Mal davon abgesehen, dass ich das Beispielprojekt, das ich hätte dabei legen können, auch noch vergessen habe. Beides möchte ich nun mit diesem Blogbeitrag nachholen.

Fehlendes Beispielprojekt

Zunächst einmal möchte ein das fehlende Beispielprojekt als Download (Twainsoft.DNP.Articles.DP) nachreichen und ein paar Unklarheiten beseitigen, die mich über Twitter erreicht haben. Das Beispielprojekt ist eine Visual Studio 2012 Solution, die als zip-Archiv über den genannten Link heruntergeladen werden kann. Normalerweise veröffentliche ich Code immer über ein Repository auf GitHub. Ich fand aber, dass das in diesem Zusammenhang nicht so viel Sinn ergeben hätte. Vielleicht ändere ich meine Meinung dazu irgendwann noch einmal.

Unklarheiten

Carsten König hat meinen Beitrag aufmerksam gelesen und mir über Twitter einige Fragen gestellt. Die möchte ich gerne beantworten.

Die erste Frage bezieht sich auf das zweite Listing (Abbildung 1).

Abb. 1: Erste Frage von Carsten König.

Nach einer kurzen Diskussion war der vermeintliche Fehler aber glücklicherweise doch keiner, sondern nur ein Missverständnis. Erfreulicherweise, denn während der Entwicklung hatte ich genau so ein Problem, das aber durch die Unit-Tests abgefangen werden konnte. Deshalb bin ich hier zunächst hellhörig geworden, weil ich die Befürchtung hatte, dass mir doch etwas durchgerutscht sein könnte.

Die zweite Frage bezieht sich auf das direkt nachfolgende Listing Nummer drei (Abbildung 2).

Abb. 2: Zweite Frage von Carsten König.

Dieses dritte Listing, dass auf Seite 47 zu sehen ist, zeigt einen Ausschnitt zur Fibonacci-Berechnung mit Memoisation. Aufgrund von Platzmangel in den Artikeln, und zur besseren Übersichtlichkeit, übernehme ich des Öfteren nur Ausschnitte von Methoden oder Klassen in einen Artikel. Das habe ich auch hier gemacht. Beispielsweise fehlt die Deklaration der Eigenschaft FibonacciNumbers, die alle bereits berechneten Fibonacci-Zahlen als Array speichert. Leider habe ich im Artikel den Hinweis vergessen, dass es sich eben um einen Ausschnitt handelt. Hinzu kommt, dass auch das Beispielprojekt fehlt, was das Listing 3 etwas nutzlos macht. Das tut mir leid. Ich selber mag es nicht, wenn Beispiele unvollständig und nicht direkt ausprobiert werden können. Ob in einem Blog oder Fachmagazin ist dabei völlig egal. Werden Beispiele angeboten, müssen diese lauffähig sein. Der entsprechende Code befindet sich in der Klasse Fib des Projekts Twainsoft.DNP.Articles.DP.Fibonacci.

Berechnung der Levenshtein-Distanz

Ein weiterer Anwendungsfall, den ich im Artikel beschrieben haben, ist die Levenshtein-Distanz. Dazu hatte ich, vor einiger Zeit im Studium, eine Beispielanwendung implementiert. Auch davon konnte ich lediglich ein paar Screenshots zeigen, aber noch kein vollständiges Projekt mitliefern.

Mittlerweile befindet sich dieser Code in der Solution für die Blog-Beispiele. Diese sind im Repository Twainsoft.Blog.Examples auf GitHub zu finden. Die Änderungen, für dieses Beispiel, konzentrieren sich auf den Branch Levenshtein-Distance. Abbildung 3 zeigt die vollständige Anwendung. Gegenüber der Version aus dem Artikel hat sich allerdings nicht allzu viel geändert. Lediglich einige Code-Stellen wurden überarbeitet, ReSharper in Version 8 hat noch mal seinen Dienst getan und das Ergebnis des Backtrackings, das Orange markiert ist, wird nicht mehr auf der Konsole sondern in der Oberfläche angezeigt.

Abb. 3: Beispielanwendung zur Levenshtein-Distanz.

Wie schon im Artikel erwähnt, hat sich während der Implementierung gezeigt, dass die Berechnung und die Darstellung getrennt werden sollten. Eigentlich logisch und ich weiß das auch. Passiert ist es hier aber trotzdem. Die Tabelle, die zur Berechnung der Werte dient, ist auch gleichzeitig Grundlage für die Anzeige. Die zusätzlichen Elemente, wie die beiden Zeichenketten am linken und oberen Rand, sind ebenfalls in der Tabelle gespeichert. Das macht die Berechnung unnötig komplex, da die korrekte Verschiebung und Berechnung der Indizes berücksichtigt werden muss.

Ebenfalls von Carsten König sind zwei weiterführende Links zum Thema Dynamische Programmierung, die viele zusätzliche Infos enthalten und sich mit der abstrakten Seite dieses Ansatzes beschäftigen. Wer dieses Vorgehen interessant findet, sollte auf jeden Fall einen Blick riskieren:

• Algebraische Dynamische Programmierung (YouTube-Video, Janis Voigtländer)
• Algebraic Dynamic Programming (Paper von Robert Giegerich und Carsten Meyer)

Fazit

Das die Dynamische Programmierung gut ist und es Anwendungsfälle gibt, bei der dieser Ansatz sehr viel Sinn ergibt, möchte ich hier nicht weiter ausführen. Das habe ich im Artikel in der dotnetpro schon genug gemacht, denke ich. Bei Interesse am Thema kann ich einen Blick in das Heft nur empfehlen.

Die Ungereimtheiten im Code und das fehlende Beispielprojekt sind ärgerlich. Ich hoffe, in Zukunft passiert das nicht noch einmal. Falls jemand auf solche Fehler aufmerksam wird, freue ich mich immer über eine Nachricht über die üblichen Kontaktwege. Dann habe ich die Möglichkeit, die Fragen zu klären und im Zweifel einen Blogbeitrag wie diesen zu schreiben.