Algoritma Tasarımı ve Analizi VI (Algorithm Design and Analysis VI)

Dinamik Programlama Nedir?

Dinamik programlama karışık problemlerin daha basit düzeylere indirilerek çözülmesini esas alan bir optimizasyon yöntemidir. Optimizasyondaki amaç, problemdeki kısıtlayıcı koşullar altında bu problemle ilgili en iyi kararı sağlamaktır. Bir problem üzerinde dinamik programlama uygulayabilmek için o problemin alt problemlere parçalanabilir veya bir önceki problemin karakteristiğini koruyacak şekilde çözümü daha kolay başka probleme dönüştürülebilir olması yeterlidir

Yönteme göre optimum çözüm başlangıç durumundan bağımsız olarak diğer çözümler ile çözüm sonuçlarına göre optimum çözümlerin ardışık olmasıdır. Yani, başlangıçta alt problemlerin çözümü bulunup elde edilen verilerle daha büyük alt problemler çözüldüğünde problemin kendisi de çözülmüş olur.

Dinamik programlama, aynı çözümlü küçük problemlere parçalanabilen tüm problemler için uygulanabilir. Fakat brute-force ile exponential zamanda çözülebilen problemlerde gerçek değerini gösterir. En basitinden fibonacci dizisinin hesabı O(2n) zaman karmaşıklığına sahipken, dinamik programlama ile problem O(n) zamanda çözülebilmektedir.

Dinamik Programlama ile çözülebilecek bazı problemler:

1.     Çubuk Kesme Problemi (Rod Cutting Problem)

2.     Knapsack Problem

3.     Zincir Matris Çarpım Problemi (Matrix Chain Multiplication Problem)

4.     Assembly Line Scheduling Problem

5.     En Uzun Ortak Alt Dizi (Longest Common Subsequence(LCS))

Hatırlatma (Memoization)

İhtiyaç duyulan bir değerin sürekli olarak hesaplanması yerine bir kere hesaplanıp ihtiyaç duyulduğunda bu değerin yeniden kullanılmasına denir. Bir fonksiyonel programlama dili olan haskell dilinde memoization işlemi otomatik gerçekleştirilmektedir. Memorization ile karıştırılmaması gerekir. Bir anlamıyla da hatırlama denebilir.

Bir problem için dinamik programlama algoritması yapmak için aşağıdaki dört adım uygulanır.

1.     En iyi çözümün karakteristiğinin belirlenmesi

2.     En iyi çözümün özyinelemeli tanımı

3.     En iyi çözümün değerini top-down veya bottom-up yaklaşımdan birini kullanarak hesaplanması

4.     Hesaplanmış verileri kullanarak en iyi çözümü bul

Bu adımlardan ilk 3’ü dinamik programlamanın temelidir. Eğer optimal çözümün yalnızca değerine ihtiyaç olursa bu temel adımları kullanmak yeterli olacaktır.

En Uzun Ortak Alt Dizi (Longest Common Subsequence(LCS))

X ve Y gibi iki string verilirse:

Birbirlerine benzerlikleri farklı şekillerde ifade edilebilir:

1. Birisi diğerinin substring’i ise benzerdir.

2. Birisi diğerine dönüştürmek için gerekli olan değişiklik azaldıkça benzerlikleri artar.

3. Her ikisinden oluşturulan bir Z string’in her ikisinde de aynı  sırada yer alması(yan yana olması gerekmez) benzerlikleri gösterir. Z’nin boyutu arttıkça X ve Y’nin benzerlikleri artar.

Farklı canlılar için DNA sıralamasının benzerliklerinin araştırılmasında kullanılır.

Yazım kontrolü (spell checkers) yapılmasında kullanılır.

Z,  X’in alt sırasıdır, eğer X’te bazı karakterleri atlayarak ya da atlamayarak oluşturulabiliyorsa:

Egzersiz

X = ”ACGGTTA”

Y= “CGTAT” stringleri tanımlansın.

LCS(X,Y) = “CGTA” ya da LCS(X,Y) = “CGTT”

Genetik Mutasyon Uygulamaları (Genetic Mutation Applications)

Optimal Çözüm Bulunması

Z boş olarak alınır, X_m = “x₁x₂x₃…x_m” ve Y_n = “y₁y₂y₃…y_n” stringlerinin sonuna kadar kontrol edilir.

1. Eğer x_m = y_n ise bu sembol Z dizisine eklenir ve LCS (X_m-1,Y_n-1) alt probleminin çözümü kullanılır.

2. Eğer x_m = y_n ise X veya Y stringlerinden bir karakter atlanır ve LCS(X_m, Y_n-1) ve LCS(X_m-1,Y_n)’den büyük olan alınır.

Egzersiz
X = "CHIMPANZEE" 
Y = "HUMAN" stringleri tanımlansın. Buna göre bu stringlerin en uzun ortak dizisi LCS(X,Y) ne olur?

Level I

Level II

Level III

Level IV

Level V

Level VI

Level VII

Level VIII

Level IX

Level X

Level XI

         H U M A N

     C H I M P A N Z E E

package LongestCommonSubsequence;

public class LongestCommonSubsequence {

    public static int find(char[] A, char[] B) {
        int[][] LCS = new int[A.length + 1][B.length + 1];
        String[][] solution = new String[A.length + 1][B.length + 1];
        // başlangıçta 0 olan satır doldurulur
        for (int i = 0; i <= B.length; i++) {
            LCS[0][i] = 0;
            solution[0][i] = "0";
        }

        // başlangıçta 0 olan sütun doldurulur
        for (int i = 0; i <= A.length; i++) {
            LCS[i][0] = 0;
            solution[i][0] = "0";
        }

        for (int i = 1; i <= A.length; i++) {
            for (int j = 1; j <= B.length; j++) {
                if (A[i - 1] == B[j - 1]) {
                    LCS[i][j] = LCS[i - 1][j - 1] + 1;
                    solution[i][j] = "diagonal";
                } else {
                    LCS[i][j] = Math.max(LCS[i - 1][j], LCS[i][j - 1]);
                    if (LCS[i][j] == LCS[i - 1][j]) {
                        solution[i][j] = "top";
                    } else {
                        solution[i][j] = "left";
                    }
                }
            }
        }
        // sonucu yazdırmak icin
        String x = solution[A.length][B.length];
        String answer = "";
        int a = A.length;
        int b = B.length;
        while (x != "0") {
            if (solution[a][b] == "diagonal") {
                answer = A[a - 1] + answer;
                a--;
                b--;
            } else if (solution[a][b] == "left") {
                b--;
            } else if (solution[a][b] == "top") {
                a--;
            }
            x = solution[a][b];
        }
        System.out.println(answer);

        for (int i = 0; i <= A.length; i++) {
            for (int j = 0; j <= B.length; j++) {
                System.out.print(" " + LCS[i][j]);
            }
            System.out.println();
        }
        return LCS[A.length][B.length];
    }

    public static void main(String[] args) {
        String A = "HUMAN";
        String B = "CHIMPANZEE";
        System.out.println("LCS :" + find(A.toCharArray(), B.toCharArray()));
    }
}

Bir sonraki yazımda görüşmek üzere...