Dynamic Programming(Dinamik Programlama) - Nedir?

Bir problemi alt problemlere bölerek, tekrarlanan problemleri bir daha çözmemek için alt problemlerin çözümlerini hafızada tutulup kullanılmasıdır.

Dinamik Programlama

Bir problemi tekrarlanan alt problemlere bölerek, tekrarlanan problemleri bir daha çözmemek için alt problemlerin çözümlerini hafızada tutup kullanılmasıdır. Bu problemlerde önemli noktalardan birisi çözülmek istenilen problemin alt problemlere bölünebilmesidir.

Fibonacci Örneği

Fibonacci serisi üreten algoritma için dinamik programlama yaklaşımı kullanılarak tekrarlanan altproblemlerin hesaplanmadan kullanılıp daha hızlı sonuç üretilmesini sağlar. Fibonnaci serisi aşağıdaki gibi bir yapıda ilerler.

0, 1, 1, 2, 3, 5, 8, 13, 21, 34, 55, 89, 144, 233, 377, 610, 987

A-) Dinamik Programlama Kullanılmadan

Fibonacci Serisi N’ninci Elamanını Hesaplama

Aşağıdaki java kodu dinamik programalama kullanmadan fibonacci serisinindeki n’ninci elemanı hesaplamaktadır.

1
2
3
4
5
6
7
8
9
    static int fibonacci(int n) {
        if (0 == n) {
            return 0;
        } else if (1 == n) {
            return 1;
        } else {
            return fibonacci(n - 2) + fibonacci(n - 1);
        }
    }

Kodun Analizi

Bu kod çalıştığında aşağıdaki gibi bir sonuç üretmektedir. Bu sonuça göre aynı alt problemleri birden fazla kez tekrardan çözdüğümüzü görebiliriz.

1
2
3
4
5
6
7
8
9
fibonacci(4)
fibonacci(2)
fibonacci(0)
fibonacci(1)
fibonacci(3)
fibonacci(1)
fibonacci(2)
fibonacci(0)
fibonacci(1)

Aşağıda hangi alt problem çözümünün kaç defa çağrıltığını görebiliriz.

1
2
3
4
5
fibonacci(4) // 1 Defa Çağrıldı.
fibonacci(2) // 2 Defa Çağrıldı.
fibonacci(0) // 2 Defa Çağrıldı.
fibonacci(1) // 3 Defa Çağrıldı.
fibonacci(3) // 1 Defa Çağrıldı.

B-) Dinamik Programlama ile Fibonacci Çözümü

Fibonacci Serisi N’ninci Elamanını Dinamik Programlama İle Hesaplama

Aşağıdaki kod bu problemin çözümü için dinamik programalama yöntemini kullanmıştır. Her bir alt problemin çözümü hafızada tutulur ve bir sonraki çözüm için kullanılır.

1
2
3
4
5
6
7
8
9
10
11
12
13
14
static int fibonacciDynamicProgramming(int n) {

		int arraySize = n+1;

		int[] fibonacci = new int[arraySize];
		fibonacci[0] = 1;
		fibonacci[1] = 1;

		for (int i = 2; i < arraySize; i++) {
				fibonacci[i] = fibonacci[i - 1] + fibonacci[i - 2];
		}

		return fibonacci[n-1]; // Index 0'dan başlar
}

C-) Performans ve Hafıza Farkları

Aşağıda verilen iki farklı çözümün çalışma zamanları arasında çok büyük farklılıklar vardır. Dinamik programalama kullanılmayan ve rekürsif bir çözüm yapan yöntem 8 saniyenin üstünde bir çalışma zamanına sahiptir, dinamik programalama kullanılan yöntem ise 1 milisaniyenin altında çözümü yapmaktadır. Hafıza farkları olarak ise dinamik programlama kullanılan yöntem çözülmek istenen fibonacci elemanı kadar ekstra bir diziye ihtiyaç duyar yani burada integer olarak tuttuğumuz bu değer de her n’ninci eleman için 32*(n+1) byte kadar kadar ekstra alana ihtiyaç duymaktadır.

1
2
        System.out.println(fibonacci(46));
        System.out.println(fibonacciDynamicProgramming(46));

Sonuç

Bu yazımda dinamik programlamanın ne olduğu ve dinamik programlamının fibonacci serisi çözümünde ne kadar avantajlı bir çalışma zamanına sahip olduğunu örneklerle gösterdim. Okuduğunuz için teşekkür ederim.

Referanslar:

1. https://tr.wikipedia.org/wiki/Dinamik_programlama
2. https://www.geeksforgeeks.org/program-for-nth-fibonacci-number/
3. https://medium.com/geekculture/how-to-solve-fibonacci-sequence-using-dynamic-programming-b7cd784ee10d

1. Dynamic Programming(Dinamik Programlama) - Nedir?
2. Big O notation Nedir ve Örnekler