Optimalisasi mikro untuk perhitungan jarak edit: apakah valid?

Di Wikipedia , implementasi untuk skema pemrograman dinamis bottom-up untuk jarak edit diberikan. Itu tidak mengikuti definisi sepenuhnya; sel-sel dalam dihitung sebagai berikut:

if s[i] = t[j] then  
  d[i, j] := d[i-1, j-1]       // no operation required
else
  d[i, j] := minimum
             (
               d[i-1, j] + 1,  // a deletion
               d[i, j-1] + 1,  // an insertion
               d[i-1, j-1] + 1 // a substitution
             )
}

Seperti yang Anda lihat, algoritme selalu memilih nilai dari tetangga kiri atas jika ada kecocokan, menghemat beberapa akses memori, operasi ALU, dan perbandingan.

Namun, penghapusan (atau penyisipan) dapat menghasilkan nilai yang lebih kecil , sehingga algoritme tersebut salah secara lokal, yakni rusak dengan kriteria optimalitas. Tapi mungkin kesalahannya tidak mengubah hasil akhirnya - mungkin dibatalkan.

Apakah optimasi mikro ini valid, dan mengapa (tidak)?

Saya tidak berpikir bahwa algoritma ini cacat. Jika dua string cocok, pertama-tama kita membandingkan dua karakter terakhirnya (dan kemudian berulang). Jika sama, kita bisa mencocokkannya untuk mendapatkan perataan yang optimal. Misalnya, perhatikan senar testdan testat. Jika Anda tidak cocok dengan dua yang terakhir t, maka salah satu dari titu tetap tidak cocok, karena jika tidak, pasangan Anda akan terlihat seperti ini:

Ini tidak mungkin, karena panah tidak diperbolehkan untuk "menyeberang". Yang cocok tmenginduksi beberapa sisipan (kotak hijau pada gambar), seperti yang digambarkan di sebelah kiri:

Tapi kemudian Anda bisa menemukan keberpihakan yang sama baiknya, digambarkan di sebelah kanan. Dalam kedua kasus Anda cocok dengan tdan Anda memiliki dua sisipan.

Argumen untuk substitusi salah satu yang terakhir tadalah sama. Jadi jika Anda mengganti salah satu yang terakhir t, maka Anda dapat mencocokkan dua t terakhir, dan mendapatkan keselarasan yang lebih baik (lihat gambar).