Algorithme de distance d'édition (variante de la plus longue sous-séquence commune)

Question

Je travaille sur une affectation scolaire qui est définie comme une variante du plus long problème de sous-séquence commun et qui est présentée dans le contexte de la programmation dynamique.

Le problème est défini comme suit:

Supposons que vous fassiez un vérificateur de sorts avec des suggestions de mots mal orthographiés. Vous aimeriez pouvoir trouver les mots les plus proches de la chaîne de lettres non mot d'un utilisateur.

Ces mots peuvent différer de la chaîne tapée par

1. Manquer une lettre
2. Avoir une lettre supplémentaire
3. Avoir une lettre remplacée par une autre lettre

Les coûts sont:

$ c_i $, le coût d'un insert

$ c_d $, le coût d'une suppression

$ c_r $, le coût d'un remplacement

Avec l'intention de commencer par une approche récursive qui peut être convertie en un programme dynamique, l'idée est de se développer à partir de sous-chaînes.

let T(j,k) denote minimum cost to transform 
substring A[1...j] to substring B[1...k]. 

then there are four ways to convert A[1...j] 
into B[1...k]

1. delete the jth character of A[1...j] and 
convert the first j-1 characters of A into the 
first k characters of B.  This equals cost cd + 
T(j-1, k)

2. convert the first j characters of A into the 
first k-1 characters of B, and insert a kth 
character into B[1...k-1].  This equals cost ci 
+ T(j, k-1)

3. replace the jth character of A with the kth 
character of B and convert the first j-1 
characters of A into the first k-1 characters 
of B.  This equals cost cr + T(j-1,k-1)

4. If characters A[j] = B[k], just convert 
A[1..(j-1)] into B[1..(k-1)]
This has cost T(j-1,k-1)


This can be written as a recursion equation, 
taking the minimum over all four alternatives 
at each step:

T(j,k) = minimum of:
    {    T(j-1, k) + cd
         T(j,k-1) + ci
        T(j-1,k-1) if A[j] = B[k]
      T(j-1, k-1) + cr if A[j] != B[k]
    }

La question est la suivante: supposons que nous ajoutions une fonction "échanger" qui corrige deux lettres qui sont tapées dans le mauvais ordre. Comment modifierions-nous l'eatiation pour le coût de la modification de la chaîne A en chaîne B si le coût d'un swap est $ C_s $?

Ma pensée est:

T(j-1, k+1) if A[j,k] = B[k,j] ?