AuK/Dynamisches Programmieren WS13-14
Aus ProgrammingWiki
Wiki-Quelltext dieser Seite.
<language>Scheme</language>
'''Autoren'''
[mailto:s3jeklin@stud.hszg.de Jens Klinger]
[mailto:s3dafran@stud.hszg.de Daniel Franke]
== Einführung ==
Das Prinzip "Teile und Herrsche" dient als Grundlage für viele Algorithmen: Um ein umfangreiches Problem zu lösen, zerlegt man es in kleinere Teilprobleme, die unabhängig voneinander gelöst werden können. In der dynamischen Programmierung wird dieses Prinzip aufgegriffen und weiterentwickelt. Im Gegensatz zu "Teile und Herrsche" wird das bottom-up-Verfahren angewendet. D.h. dynamische Programmierung führt dann zu einer Lösung, wenn das Optimierungsproblem aus vielen gleichartigen Teilproblemen besteht, und sich eine optimale Gesamtlösung des Problems aus optimalen Teillösungen zusammensetzt. Zu diesem Zweck werden alle Teilproblem "von-unten-her" berechnet und in eine Tabelle eingetragen um eine erneute Berechnung zu vermeiden.
Die Entwicklung eines dynamischen Programms kann in vier Schritte unterteilt werden:
# Charakterisierung der Struktur eines Programms.
# Definieren des Wertes einer optimalen Lösung rekursiv.
# Berechnung des Wertes einer optimalen Lösung durch den bottom-up-Ansatz.
# Konstruktion einer zugehörigen optimalen Lösung aus den schon berechneten Daten.
Bei der Anwendung der dynamischen Programmierung können immer folgende Schwierigkeiten auftreten:
* Es ist nicht immer möglich, die Lösungen kleinerer Probleme so zu kombinieren, dass sich die optimale Lösung eines größeren Problems ergibt.
* Die Anzahl der zu lösenden Teilprobleme kann unvertretbar groß werden.
* Die Zerlegung in unabhängige und überlappungsfreie Teilprobleme ist häufig Illussion.
Es gibt daher viele Probleme, für die die dynamische Programmierung nicht anwendbar bzw. ineffizienter ist als Standardalgorithmen. In diesem Wiki werden daher einige Probleme vorgestellt für die dynamische Programmierung sehr effizient ist.
Doch zunächst soll auf grundlegende Schwierigkeiten bei der dynamischen Programmierung hingewiesen werden.
==Rekursiver Lösungsansatz = rekursiver Algorithmus?==
In diesem Beispiel soll anhand der Berechnung der Fibonacci-Folge gezeigt werden, warum in der dynamischen Programmierung zumeist iterative Lösungsmethoden mit Bottom-up-Ansatz verwendet werden.
Zur Erinnerung, die Fibonacci-Folge ist eine unendliche Folge von Zahlen, bei der die Summe der beiden Vorgänger die unmittelbar folgende Zahl ergibt.
===Rekursive Definition===
$f(0) = 1$
$f(1) = 1$
$f(n) = f(n-1)+f(n-2), \text{mit n} \geq 2$
===Rekursive Lösung===
<code id="5278f5693cfdb">
(define fib
(lambda (n)
(if (< n 1)
1
(+ (fib (- n 1))(fib (- n 2))))))
</code>
<run>(fib 5)</run>
===Abschätzung der Laufzeit===
Die Funktion zur Berechnung der Fibonacci-Zahlen wächst exponentiell:
$f(n) = [\frac{1}{\sqrt{5}}(1,618...)]$
Wir müssen beachten, das wir mit einer rekursiv definierten Funktion, auch für die Abschätzung der Laufzeit eine Rekursionsgleichung erhalten!
Das sehen wir hier:
$T(n) = \text{Anzahl der Schritte zur Berechnung von } fib(n)$
$T(0) = 1$
$T(1) = 1$
$T(n) = T(n-1)+T(n-2)$
Wir sehen das die Formel zur Abschätzung der Laufzeit, identisch ist, mit der Formel zur Berechnung der Fibonacci-Zahl.
Daraus können wir wiederum Schlussfolgern, das es sich um einen exponentiellen Aufwand $\mathcal O(2n)$handelt.
===Baumdarstellung===
<popup>[[Bild:Fib(5).jpg]]</popup>
===Alternativen===
Aufgrund dieser Schwierigkeiten wird in der dynamischen Programmierung traditionell der iterative Lösungsansatz bevorzugt. Doch auch dieser hat Nachteile. Wie bereits erwähnt, müssen alle Teillösungen berechnet werden, auch diese, die nicht zur optimalen Lösung des Problems beitragen. Der größte Nachteil besteht jedoch darin, dass der rekursiv gebildete Top-down-Ansatz in einen iterativen Bottom-up-Algorithmus umgewandelt werden muss. Das ist sehr aufwändig, da der Algorithmus erst umgewandelt werden muss und sich bei dieser Umwandlung schnell Fehler einschleichen.
Doch auch aus dieses Problem lässt sich lösen. Eine Variante der Dynamischen Programmierung, die oft so effizient wie die traditionelle Methode ist, heißt Memisation (eng. memoizing). Im nächsten Abschnitt wird am 0/1 Rucksackproblem gezeigt, wie iterative und rekursive Lösungsansätze aussehen können.
== Lösung des 0/1 Rucksackproblems ==
Beim Rucksackproblem handelt es sich um ein Optimierungsproblem der Kombinatorik. Aus einer bestimmten Menge von Objekten, die jeweils ein Gewicht und einen Wert haben, soll eine Teilmenge ausgewählt werden, deren Gesamtgewicht ein vorgegebenes Gewichtslimit nicht überschreitet.
Hierbei gilt die Optimalitätsbedingung, denn die optimale Gesamtlösung lässt sich aus optimalen Teilproblemen zusammensetzen.
Bezogen auf das Rucksackproblem bedeutet das, Gegenstand i wird in den optimal gefüllten, auch leeren, Rucksack gelegt. D.h. alle zur Auswahl stehenden Gegenstände können solange in den Rucksack gelegt werden, solange sie noch Platz haben.
Für den optimalen gefüllten Rucksack gilt die rekursive Definition mit:
$i=\text{ Gegenstand }$
$g=\text{ Gewicht }$
$w=\text{ Wert des Gegenstands }$
$n = \text { Anzahl der Gegenstände }$
$K = \text{ Kapazität des Rucksacks }$
$wert(i,g) = \text{ Optimaler Wert für die Gegenstände }$
$wert(n,K)=\text{ Optimaler Gesamtwert }$
<math>$wert(i,g) = \begin{cases}
0, & wenn \ i =0 \\
wert(i-1, g), & wenn \ i > 0 \ und \ g-g_{i} < 0\\
max(wert(i-1,g), wert(i-1, g-g_{i})+w_{i}), & sonst \\
\end{cases}$</math>
Der Fall $wert(i,g) = wert(i-1,g)$ bezieht sich auf einen Gegenstand, der die Restkapazität des Rucksacks überschreiten würde. D.h. $wert(i-1,g)$ ist der Maximalwert aus 1,2,...,i-1 Gegenständen mit Bezug auf die Kapazität des Rucksacks. Der letzte Fall $wert(i,g) = max(wert(i-1,g), wert(i-1, g-g_{i})+w_{i})$ beschreibt die Maximierung des Werts in Berücksichtigung des Gewichts.
===Iterativer Algorithmus===
Der iterative Lösungsansatz lässt sich, wie bereits erwähnt, nicht mit einer rekursiven Vorschrift umsetzen. Jedoch ist es möglich die Überlegungen aus dieser Vorschrift zu verwenden und in einen iterativen Lösungsansatz umzuwandeln.
Das soll am folgenden Beispiel demonstriert werden:
<table border="1" bordercolor="#000000" style="background-color:#FFFFFF" width="20%" cellpadding="2" cellspacing="1">
<tr>
<td style="text-align: center;width: 5mm;" bgcolor="#D8D8D8"><math>$i$</math></td>
<td style="text-align: center;width: 5mm;">1</td>
<td style="text-align: center;width: 5mm;">2</td>
<td style="text-align: center;width: 5mm;">3</td>
<td style="text-align: center;width: 5mm;">4</td>
<td style="text-align: center;width: 5mm;">5</td>
</tr>
<tr>
<td style="text-align: center;width: 5mm;" bgcolor="#D8D8D8"><math>$g_i$</math></td>
<td style="text-align: center;width: 5mm;">2</td>
<td style="text-align: center;width: 5mm;">2</td>
<td style="text-align: center;width: 5mm;">6</td>
<td style="text-align: center;width: 5mm;">5</td>
<td style="text-align: center;width: 5mm;">4</td>
</tr>
<tr>
<td style="text-align: center;width: 5mm;" bgcolor="#D8D8D8"><math>$w_i$</math></td>
<td style="text-align: center;width: 5mm;">6</td>
<td style="text-align: center;width: 5mm;">3</td>
<td style="text-align: center;width: 5mm;">5</td>
<td style="text-align: center;width: 5mm;">4</td>
<td style="text-align: center;width: 5mm;">6</td>
</tr>
</table>
Zur Lösung wird die Gegenstandsliste, mit der Prozedur $gegenstaende$, auf Vektoren als Gewicht/Wert-Paar abgebildet. Auf das jeweilige Gewicht bzw. den jeweiligen Wert kann dann mittels der Prozeduren $gewicht$ und $wert$ zugegriffen werden. Die Prozedur $gesamtwert-iterativ$ füllt dann eine Tabelle mit den jeweils maximalen Gesamtwerten für die aktuell betrachteten Gegenstände (Zeile) und das darauf bezogene Gesamtgewicht (Spalte). Das Problem hierbei ist die Speicherung aller Werte in der Tabelle, was eine sehr hohe Speicherbelastung nach sich zieht. Für den hier dargestellten Fall, genügt es jedoch, wie in der rekursiven Vorschrift notiert, die jeweils letzten beiden Zeilen (zeileAlt und zeileNeu) zu speichern. D.h. die $i$-te Zeile, wird aus $i-1$-ten Zeile berechnet.
<code>
(define gegenstaende
(list->vector
'("dummy"
(2 . 6)
(2 . 3)
(6 . 5)
(5 . 4)
(4 . 6))))
;Liste wird auf Vektor abgebildet, hier von 0 bis 11, um die Nummerierung mit 1 zu starten, wird 0 nicht benutzt(dummy).
(define gewicht
(lambda(i)
(car (vector-ref gegenstaende i))))
;um auf das Gewicht zuzugreifen, wird auf das erste Element aus dem Vektor an der Position i zugegriffen.
(define wert
(lambda(i)
(cdr (vector-ref gegenstaende i))))
;um auf den Wert zuzugreifen, wird auf das erste Element aus dem Vektor an der Position i zugegriffen.
(define vector-copy
(lambda (v)
(let* ((l (vector-length v))
(v-duplikat (make-vector l)))
(do ((i 0 (+ i 1)))((= i l) v-duplikat)
(vector-set! v-duplikat i (vector-ref v i))))))
(define gesamtwert-iterativ
(lambda(n k)
(let ((zeileAlt (make-vector (+ k 1) 0))
(zeileNeu (make-vector (+ k 1) 0)))
(do ((z 1 (+ z 1))) ;Zeile
((> z n)(vector-ref zeileNeu k));Resultat
(set! zeileAlt (vector-copy zeileNeu))
(let ((gewicht-z (gewicht z)))
(do ((s 1 (+ s 1))) ;Spalte
((> s k))
(if (< s gewicht-z)
(vector-set! zeileNeu s (vector-ref zeileAlt s))
(vector-set! zeileNeu s
(max
(vector-ref zeileAlt s)
(+ (vector-ref
zeileAlt
(- s gewicht-z))
(wert z)))))))))))
</code>
<run>
(gesamtwert-iterativ 5 10)
</run>
Der Aufruf von (gesamtwert-iterativ 5 10) erzeugt folgende Tabelle:
<table border="1" bordercolor="#000000" style="background-color:#FFFFFF" width="40%" cellpadding="2" cellspacing="1">
<tr>
<td style="text-align: center;width: 5mm;" bgcolor="#D8D8D8"><math>$n/K$</math></td>
<td style="text-align: center;width: 5mm;" bgcolor="#D8D8D8"><math>$0$</math></td>
<td style="text-align: center;width: 5mm;" bgcolor="#D8D8D8"><math>$1$</math></td>
<td style="text-align: center;width: 5mm;" bgcolor="#D8D8D8"><math>$2$</math></td>
<td style="text-align: center;width: 5mm;" bgcolor="#D8D8D8"><math>$3$</math></td>
<td style="text-align: center;width: 5mm;" bgcolor="#D8D8D8"><math>$4$</math></td>
<td style="text-align: center;width: 5mm;" bgcolor="#D8D8D8"><math>$5$</math></td>
<td style="text-align: center;width: 5mm;" bgcolor="#D8D8D8"><math>$6$</math></td>
<td style="text-align: center;width: 5mm;" bgcolor="#D8D8D8"><math>$7$</math></td>
<td style="text-align: center;width: 5mm;" bgcolor="#D8D8D8"><math>$8$</math></td>
<td style="text-align: center;width: 5mm;" bgcolor="#D8D8D8"><math>$9$</math></td>
<td style="text-align: center;width: 5mm;" bgcolor="#D8D8D8"><math>$10$</math></td>
</tr>
<tr>
<td style="text-align: center;width: 5mm;" bgcolor="#D8D8D8"><math>$0$</math></td>
<td style="text-align: center;width: 5mm;">0</td>
<td style="text-align: center;width: 5mm;">0</td>
<td style="text-align: center;width: 5mm;">0</td>
<td style="text-align: center;width: 5mm;">0</td>
<td style="text-align: center;width: 5mm;">0</td>
<td style="text-align: center;width: 5mm;">0</td>
<td style="text-align: center;width: 5mm;">0</td>
<td style="text-align: center;width: 5mm;">0</td>
<td style="text-align: center;width: 5mm;">0</td>
<td style="text-align: center;width: 5mm;">0</td>
<td style="text-align: center;width: 5mm;">0</td>
</tr>
<tr>
<td style="text-align: center;width: 5mm;" bgcolor="#D8D8D8"><math>$1:(g_i=2; w_i=6)$</math></td>
<td style="text-align: center;width: 5mm;">0</td>
<td style="text-align: center;width: 5mm;">0</td>
<td style="text-align: center;width: 5mm;">6</td>
<td style="text-align: center;width: 5mm;">6</td>
<td style="text-align: center;width: 5mm;">6</td>
<td style="text-align: center;width: 5mm;">6</td>
<td style="text-align: center;width: 5mm;">6</td>
<td style="text-align: center;width: 5mm;">6</td>
<td style="text-align: center;width: 5mm;">6</td>
<td style="text-align: center;width: 5mm;">6</td>
<td style="text-align: center;width: 5mm;">6</td>
</tr>
<tr>
<td style="text-align: center;width: 5mm;" bgcolor="#D8D8D8"><math>$2:(g_i=2; w_i=3)$</math></td>
<td style="text-align: center;width: 5mm;">0</td>
<td style="text-align: center;width: 5mm;">0</td>
<td style="text-align: center;width: 5mm;">6</td>
<td style="text-align: center;width: 5mm;">6</td>
<td style="text-align: center;width: 5mm;">6</td>
<td style="text-align: center;width: 5mm;">9</td>
<td style="text-align: center;width: 5mm;">9</td>
<td style="text-align: center;width: 5mm;">9</td>
<td style="text-align: center;width: 5mm;">9</td>
<td style="text-align: center;width: 5mm;">9</td>
<td style="text-align: center;width: 5mm;">9</td>
</tr>
<tr>
<td style="text-align: center;width: 5mm;" bgcolor="#D8D8D8"><math>$3:(g_i=6; w_i=5)$</math></td>
<td style="text-align: center;width: 5mm;">0</td>
<td style="text-align: center;width: 5mm;">0</td>
<td style="text-align: center;width: 5mm;">6</td>
<td style="text-align: center;width: 5mm;">6</td>
<td style="text-align: center;width: 5mm;">9</td>
<td style="text-align: center;width: 5mm;">9</td>
<td style="text-align: center;width: 5mm;">9</td>
<td style="text-align: center;width: 5mm;">9</td>
<td style="text-align: center;width: 5mm;">11</td>
<td style="text-align: center;width: 5mm;">11</td>
<td style="text-align: center;width: 5mm;">14</td>
</tr>
<tr>
<td style="text-align: center;width: 5mm;" bgcolor="#D8D8D8"><math>$4:(g_i=5; w_i=4)$</math></td>
<td style="text-align: center;width: 5mm;">0</td>
<td style="text-align: center;width: 5mm;">0</td>
<td style="text-align: center;width: 5mm;">6</td>
<td style="text-align: center;width: 5mm;">6</td>
<td style="text-align: center;width: 5mm;">9</td>
<td style="text-align: center;width: 5mm;">9</td>
<td style="text-align: center;width: 5mm;">9</td>
<td style="text-align: center;width: 5mm;">10</td>
<td style="text-align: center;width: 5mm;">11</td>
<td style="text-align: center;width: 5mm;">13</td>
<td style="text-align: center;width: 5mm;">14</td>
</tr>
<tr>
<td style="text-align: center;width: 5mm;" bgcolor="#D8D8D8"><math>$5:(g_i=4; w_i=6)$</math></td>
<td style="text-align: center;width: 5mm;">0</td>
<td style="text-align: center;width: 5mm;">0</td>
<td style="text-align: center;width: 5mm;">6</td>
<td style="text-align: center;width: 5mm;">6</td>
<td style="text-align: center;width: 5mm;">9</td>
<td style="text-align: center;width: 5mm;">9</td>
<td style="text-align: center;width: 5mm;">12</td>
<td style="text-align: center;width: 5mm;">12</td>
<td style="text-align: center;width: 5mm;">15</td>
<td style="text-align: center;width: 5mm;">15</td>
<td style="text-align: center;width: 5mm;">15</td>
</tr>
</table>
====Aufwandsbetrachtung====
An der iterativen Prozedur kann man sehr gut erkennen, dass sich der Aufwand aus der Berechnung der Tabelle mit allen Spalten und Zeilen ergibt.
$\mathcal O(n\cdot K)\cdot\mathcal O(1)=\mathcal O(nK)$
Nimmt man nun an, dass $K$ eine Konstante ist, ergibt sich ein linearer Aufwand $\mathcal O(n)$. Doch da für alle $n$ Gegenstände gilt das $g_i \le K$ ist, lässt sich ein Zusammenhang zwischen $n$ und $K$ herstellen. Ein solcher Algorithmus heißt pseudopolynomiell und es muss die Eingabelänge der Werte einer beliebigen Instanz des 0/1 Rucksackproblems untersucht werden. Dazu müssen die Eingabewerte in Binärdarstellung umgewandelt und eine obere Schranke festlegt werden. Wir legen sozusagen die Eingabewerte auf das Band einer Turing-Maschine.
Für das 0/1 Rucksackproblem besteht die Eingabe aus $2n+1$ natürlichen Zahlen, also dem Gewicht ($g_1,g_2,...,g_n$), dem Wert ($w_1,w_2,...,w_n$), und der Gesamtkapazität $K$. Zusätzlich definieren wir einen
Maximalwert $\hat w = max\{w_1,w_2,...,w_n\}$.
Die Beschränkung der Eingabelänge muss folgendermaßen aussehen:
$\mathcal O(n\cdot(log_2 K+log_2 \hat w)+log_2 K)$ = $\mathcal O(n\cdot(log_2 K+log_2 \hat w))$.
Um nun die Rechenzeit des Algorithmus zu bestimmen müssen wir eine Länge für $K$ festlegen, z.B. $K=2^n$ und damit $\hat w \le 2^n$. Daraus folgt, dass die Rechenzeit bei $\mathcal O(n^2)$ liegt und der Algorithmus eine exponentielle Rechenzeit $\mathcal O(n\cdot 2^n)$ hat.
In diesem Fall lässt sich die polynomiale Rechenzeit nur erreichen wenn $K$ durch ein Polynom beschränkt wird. So z.B. $K \le n^{10}$, was zu einer Rechenzeit von $O(n^{11})$ führt. Eine solche Beschränkung ist jedoch unüblich, da die Größe und nicht die Bitlänge von $K$ in die Laufzeit eingeht.
===Rekursiver Algorithmus===
Die Lösung des 0/1 Rucksackproblems mittels Rekursion wird im Folgenden mit einer Prozedur gezeigt die im ersten Teil ohne memoizing und im zweiten Teil mit memoizing arbeitet.
====Ohne Memoizing====
<code id="527f50a078def" hidden>
(define gegenstaende
(list->vector
'("dummy"
(2 . 6)
(2 . 3)
(6 . 5)
(5 . 4)
(4 . 6))))
(define gewicht
(lambda (i)
(car (vector-ref gegenstaende i))))
(define wert
(lambda (i)
(cdr (vector-ref gegenstaende i))))</code>
<code id="527f50a078ed5">(define gesamtwert-rekursiv
(lambda (n k)
(let ((rek-aufrufe 0))
(letrec
((gesamtwert
(lambda (i g)
(set! rek-aufrufe (+ rek-aufrufe 1))
(cond
((= i 0) 0)
((> (gewicht i) g) (gesamtwert (- i 1) g))
(else
(max
(gesamtwert (- i 1) g)
(+ (gesamtwert (- i 1) (- g (gewicht i)))(wert i))))))))
(list (gesamtwert n k) rek-aufrufe)))))
</code>
<run id="527f50a0790c3">(gesamtwert-rekursiv 5 10)</run>
== Needleman-Wunsch-Algorithmus ==
//TODO Einleitung DNA / Sequenzanalyse / String Matching
===Problemstellung===
Der Needleman-Wunsch-Algorithmus berechnet das optimale globale Alignment von zwei Sequenzen. Er erstellt dabei eine Score zur Bewertung der Ähnlichkeit. Je größer die Score, umso größer die Ähnlichkeit. Das Alignment ist eine Folge von Editieroperationen, um die erste Sequenz in die zweite Sequenz zu überführen. Das soll an einem Beispiel gezeigt werden:
Gegeben sind zwei Proteinsequenzen, z.B. die Sequenzen MAEHTE und AEHREN. Gesucht wird nach der Ähnlichkeit. Werden diese Sequenzen
untereinander geschrieben, ist keine Übereinstimmung zu erkennen.
<p><tt><b>M A E H T E </b><br><b>A E H R E N</b></tt></p>
Durch Einfügen von Gaps werden nun Übereinstimmungen in Teilstücken erreicht:
<p><tt><b>M A E H T E _</b><br> <b> | | | |</b><br><b>_ A E H R E N</b></tt></p>
Der Abschnitt AEH bildet dabei die längste gemeinsame Teilsequenz, das Alignment. Die Länge der längsten Teilsequenz ist ein Maß für die Ähnlichkeit der Sequenzen. Das heißt, je mehr senkrechte Striche, umso größer die Ähnlichkeit. Die Anzahl der Nichtübereinstimmungen des Vergleichs wird als Editier-Distanz bezeichnet. Dieses Maß gibt an, wie viele Buchstabenänderungen, Einfügungen und Löschungen mindestens erforderlich sind, um eine Sequenz in die andere zu überführen. Im obigen Beispiel etwa lässt sich MAETHE in AEHREN überführen, indem das M gelöscht wird, das T in ein R geändert wird und am Schluss ein N eingefügt wird. Die Editierdistanz beträgt somit 3.
Noch genauer lässt sich die Ähnlichkeit bewerten, wenn die Übereinstimmung gewisser Buchstaben höher bewertet wird als die anderer. Ebenso wenn Nichtübereinstimmungen bestimmter Kombinationen anders bewertet werden und wenn Einfügen und Löschen eine eigene Bewertung bekommen. Im Beispiel wird jede Übereinstimmung mit 3, jede Nichtübereinstimmung mit 0 und jede Einfügung bzw. Löschung mit -1 bewertet. Dazu werden die Variablen $match$, $mismatch$ und $gappenalty$ eingeführt.
$match = 3$
$mismatch = 0$
$gappenalty = -1$
===Lösung===
Mit dem Needleman-Wunsch-Algorithmus wird erst das Maß der Ähnlichkeit und anschließend ein Alignment berechnet. Gegeben sind zwei Sequenzen $x$ und $y$. Die Längen der Sequenzen werden mit $m\times$$n$ bezeichnet. Bei der Berechnung wird die Funktion $equal$ benutzt, die $i$ und $y$ miteinander vergleicht. Der Funktionswert $equal(i,j)$ ist gleich $match$, wenn das $i$-te Zeichen von $x$ mit dem $j$-ten Zeichen von $y$ übereinstimmt, und sonst gleich $mismatch$:
<math>
$equal(i,j)=\left\{
\begin{array}{ll}
match,\text{ falls $x_{i}=y_{j}$;}\\
mismatch,\text{ sonst.}
\end{array}
\right.$
</math>
$\text{für alle i in {0, ..., m-1 }, j in {0, ..., n-1}}$
Es wird nun eine $m\times$$n$-Matrix $a$ nach folgender Vorschrift ausgefüllt:
<math>
$a_{0, 0} = 0 \\
{0, j} = a_{0, j-1}+gappenalty \\
{i, 0} = a_{i-1, 0}+gappenalty \\
{i, j} = max(a_{i-1, j}+gappenalty, a_{i, j-1}+gappenalty, a_{i-1, j-1}+gappenalty)$
</math>
$\text{für alle i in {1, ..., m-1}, j in {1, ..., n-1}}$
Für das Beispiel ergibt sich folgende Matrix:
<table border="1" bordercolor="#000000" style="background-color:#FFFFFF" width="20%" cellpadding="1" cellspacing="1">
<tr>
<td style="text-align: center;width: 5mm;" bgcolor="#D8D8D8"></td>
<td style="text-align: center;width: 5mm;" bgcolor="#D8D8D8">$</td>
<td style="text-align: center;width: 5mm;" bgcolor="#D8D8D8">A</td>
<td style="text-align: center;width: 5mm;" bgcolor="#D8D8D8">E</td>
<td style="text-align: center;width: 5mm;" bgcolor="#D8D8D8">H</td>
<td style="text-align: center;width: 5mm;" bgcolor="#D8D8D8">R</td>
<td style="text-align: center;width: 5mm;" bgcolor="#D8D8D8">E</td>
<td style="text-align: center;width: 5mm;" bgcolor="#D8D8D8">N</td>
</tr>
<tr>
<td style="text-align: center;width: 5mm;" bgcolor="#D8D8D8">$</td>
<th style="text-align: center;width: 5mm;">0</th>
<td style="text-align: center;width: 5mm;">-1</td>
<td style="text-align: center;width: 5mm;">-2</td>
<td style="text-align: center;width: 5mm;">-3</td>
<td style="text-align: center;width: 5mm;">-4</td>
<td style="text-align: center;width: 5mm;">-5</td>
<td style="text-align: center;width: 5mm;">-6</td>
</tr>
<tr>
<td style="text-align: center;width: 5mm;" bgcolor="#D8D8D8">M</td>
<th style="text-align: center;width: 5mm;">-1</th>
<td style="text-align: center;width: 5mm;">0</td>
<td style="text-align: center;width: 5mm;">-1</td>
<td style="text-align: center;width: 5mm;">-2</td>
<td style="text-align: center;width: 5mm;">-3</td>
<td style="text-align: center;width: 5mm;">-4</td>
<td style="text-align: center;width: 5mm;">-5</td>
</tr>
<tr>
<td style="text-align: center;width: 5mm;" bgcolor="#D8D8D8">A</td>
<td style="text-align: center;width: 5mm;">-2</td>
<th style="text-align: center;width: 5mm;">2</th>
<td style="text-align: center;width: 5mm;">1</td>
<td style="text-align: center;width: 5mm;">0</td>
<td style="text-align: center;width: 5mm;">-1</td>
<td style="text-align: center;width: 5mm;">-2</td>
<td style="text-align: center;width: 5mm;">-3</td>
</tr>
<tr>
<td style="text-align: center;width: 5mm;" bgcolor="#D8D8D8">E</td>
<td style="text-align: center;width: 5mm;">-3</td>
<td style="text-align: center;width: 5mm;">1</td>
<th style="text-align: center;width: 5mm;">5</th>
<td style="text-align: center;width: 5mm;">4</td>
<td style="text-align: center;width: 5mm;">3</td>
<td style="text-align: center;width: 5mm;">2</td>
<td style="text-align: center;width: 5mm;">1</td>
</tr>
<tr>
<td style="text-align: center;width: 5mm;" bgcolor="#D8D8D8">H</td>
<td style="text-align: center;width: 5mm;">-4</td>
<td style="text-align: center;width: 5mm;">0</td>
<td style="text-align: center;width: 5mm;">4</td>
<th style="text-align: center;width: 5mm;">8</th>
<td style="text-align: center;width: 5mm;">7</td>
<td style="text-align: center;width: 5mm;">6</td>
<td style="text-align: center;width: 5mm;">5</td>
</tr>
<tr>
<td style="text-align: center;width: 5mm;" bgcolor="#D8D8D8">T</td>
<td style="text-align: center;width: 5mm;">-5</td>
<td style="text-align: center;width: 5mm;">-1</td>
<td style="text-align: center;width: 5mm;">3</td>
<td style="text-align: center;width: 5mm;">7</td>
<th style="text-align: center;width: 5mm;">8</th>
<td style="text-align: center;width: 5mm;">7</td>
<td style="text-align: center;width: 5mm;">6</td>
</tr>
<tr>
<td style="text-align: center;width: 5mm;" bgcolor="#D8D8D8">E</td>
<td style="text-align: center;width: 5mm;">-6</td>
<td style="text-align: center;width: 5mm;">-2</td>
<td style="text-align: center;width: 5mm;">2</td>
<td style="text-align: center;width: 5mm;">6</td>
<td style="text-align: center;width: 5mm;">7</td>
<th style="text-align: center;width: 5mm;">11</th>
<th style="text-align: center;width: 5mm;">10</th>
</tr>
</table>
Die Zahl in der rechten unteren Ecke ist das Maß für die Ähnlichkeit der beiden Sequenzen. Das Alignment lässt sich konstruieren, indem man ausgehend vom rechten unteren Feld in die Richtung geht, aus der das Maximum kommt. Diese Felder sind in der Matrix fett gekennzeichnet. Wird nach links gegangen, entspricht das einer Einfügung in der Sequenz $x$. Wird nach oben gegangen, entspricht das einer Einfügung in die Sequenz $y$. Wird diagonal nach links oben gegangen, entspricht das einer Übereinstimmung, wenn der Wert des aktuellen Feldes und der Wert des linken oberen Nachbarfeldes sich um $match$ unterscheidet und sonst einer Nichtübereinstimmung. So kommt das folgende Alignment zustande:
<p><tt><b>M A E H T E _</b><br> <b> | | | |</b><br><b>_ A E H R E N</b></tt></p>
== Aufwandsbetrachtung und Einsatzgebiete ==
== Fazit ==