Zeichenketten, Komplexität

18.08.2014, 01:23	evinda	Auf diesen Beitrag antworten »
Zeichenketten, Komplexität Hallo!!! Wir haben zwei Zeichenketten $\begin{eqnarray} A=[1 \dots m] \end{eqnarray}$ und $\begin{eqnarray} B[1 \dots n] \end{eqnarray}$ und die folgenden 3 Operationen sind erlaubt: - Einen Buchstaben eingeben,mit Komplexität $\begin{eqnarray} c_i \end{eqnarray}$ - Einen Buchstaben löschen,mit Komplexität $\begin{eqnarray} c_d \end{eqnarray}$ - Einen Buchstaben ersetzen,mit Komplexität $\begin{eqnarray} c_r \end{eqnarray}$ Wir suchen nach der optimalen Folge der Operationen(Folge der Operationen mit der geringsten Komplexität),für die Umwandlung der Zeichenkette A zur Zeichenkette B. $\begin{eqnarray} T(i,j)=\text{ Die geringste Komplexität der Umwandlung von } A[1 \dots i] \text{ in } B[1 \dots j], 1 \leq i \leq m, 1 \leq j \leq n<br /> \end{eqnarray}$ In meinen Notizen steht,dass: $\begin{eqnarray} T(i,j)=\min \left\{\begin{matrix}<br /> T(i-1,j)+c_d & \text{ // wir löschen den i-ten Buchstaben von A}\\ <br /> T(i,j-1)+c_i & \text{ // wir geben den j-ten Buchstaben von B ein } \\ <br /> T(i-1,j-1) & \text{wenn } A[i]=B[j]\\ <br /> T(i-1,j-1)+c_r & \text{wenn } A[i] \neq B[j] <br /> \end{matrix}\right. \end{eqnarray}$ Warum gilt aber diese Formel? Könntet ihr mir erklären,wie man sie gefunden hat?

1

Verwandte Themen

Die Beliebtesten »

Die Größten »

Die Neuesten »