En uzun Ortak Küme (longest common subsequence, Lcs)

yazan : Şadi Evren ŞEKER

İki küme arasındaki ortak elamanların (sıralı olmak şartıyla) en uzun ortaklığını arar. Örnek:
A-> {X,M,J,Y,A,U}
B-> {M,Z,J,A,W,X,U}
olarak verilmiş olsun. Bu iki kümenin, sırası bozulmadan ortak olan en uzun alt kümesi:
LCS -> {M,J,A,U} olarak bulunur.

Bu problem karmaşıklık açısından NP-hard problemlere bir örnektir. Aynı zamanda çözüm için önerilen yöntemler incelendiğinde dinamik programlamanın anlaşılması için ideal bir örnektir.

Örnek bir çözüm yöntemini inceleyelim:
Problemin ilk akla gelen ve en basit çözümü kümelerden birisini ana küme seçerek, bu kümedeki elemanları teker teker diğer küme ile sınamak olabilir.
Örneğin A kümesi seçilmiş olsun. A kümesinin ilk elemanından son elemanına kadar ortak elemanlara bakılacaktır. Bu durumda ilk eleman X, B kümesinde aranacaktır, daha sonra X ile birlikte U aranacaktır. ihtimallerin sonuna gelindiğinde bu ikili bırakılıp yeni bir ihtimal denenecektir:
Örnek çalışma:
A kümesinden X seçilir. B kümesinde sınanır. Karşılığı bulununca LCS1 olarak kaydedilir. devamı olan harflerden uygun olan seçilir (bu örnekte U) LCS1’e eklenir.
LCS1->{X,U}
LCS2->{M,J,A,U}
LCS3->{J,A,U}
LCS4->Y’nin eşi diğer kümede yok
LCS5->{A,U}
LCS6->{U}

yukarıdaki yönteme göre A, kümesinin bütün elemanları başlangıç elemanı olarak denenmiştir. Fakat dinamik programlama yaklaşımı incelenecek olursa bu işlemin çok daha kısa zamanda yapılabileceği görülür:
Aşağıda bir çözüm yöntemi olarak tablo kullanılması önerilmiştir. Buna göre tablodaki her hücre, ilgili satır ve sütün başlığına kadar olan en uzun ortak kümeyi tutmaktadır:

yukarıdaki şekilde örnek bir tablo verilmiştir. Buna göre verilen problemdeki en uzun ortak kümeyi bulmak hedeflenmektedir. Tablonun sağ alt köşesinde bulunan bu küme sorunun cevabıdır. Sorunun çözümünde tablo oluşturulurken her hücre kendisinin bir üstündeki veya bir solundaki hücreyi aynen kopyalamakta, ve üzerine satır ve sütün ismini şayet ortaksa yazmaktadır. Örneğin son oluşturulan sağ alt köşedeki küme, solundaki ve tepesindeki kümelerin kopyalanması ile oluşur. Bu kopyalama işlemine U elemanı ilave edilir çünkü bu hücrenin bulunduğu sütun ile satır ismi aynıdır.
Bu işlem yapılırken karşılaşılabilecek bir problem de solundaki bilgi ile tepesindeki bilginin aynı olmamasıdır. Bu durum kırmızı çember içerisinde gösterilmiştir. Bu durumda daha uzun bir küme elde edilince kısa kalan küme bırakılarak, uzun küme ile yola devam edilir. (problemin en uzun kümeyi bulmak olduğunu hatırlayınız).
Bu işlem sonunda aşağıdaki ortak küme uzunluklarını gösteren tablo elde edilir:

     | 0 1 2 3 4 5 6 7
     |   M Z J A W X U
-----|-----------------
0    | 0 0 0 0 0 0 0 0
1  X | 0 0 0 0 0 0 1 1
2  M | 0 1 1 1 1 1 1 1
3  J | 0 1 1 2 2 2 2 2
4  Y | 0 1 1 2 2 2 2 2
5  A | 0 1 1 2 3 3 3 3
6  U | 0 1 1 2 3 3 3 4

Buna göre her seferinde kendinden önceki elemanlara bakılması önlenmiş olur. Yani örneğin tablonun 4,5 hücresine bakıldığında A harfleri kontrol edilmektedir. Bu kontrol sırasında kendisinden önceki harflerin kontrolüne gerek kalmaz. (tekrar B kümesinin MZJ harflerine bakılmaz), bu sayede ortak yapılan işlemler, dinamik programlama ilkesine uygun olarak elenmiş olur.