Dinamik Programlama

Bugün dinamik programlama hakkında bir örnek yapmaya karar verdim. İlk olarak dinamik programlamanın ne olduğundan bahsedeceğim. Daha sonra Fibonacci sayılarına dayanan örneği vereceğim.
Dinamik programlama problemleri tekrarlayan alt problemler şeklinde ele alıp çözen bir tekniktir. Bu yöntemde amaç tekrarlayan problem çözümlerini saklayarak, bu çözümleri gerektiğinde tekrar kullanmaktır. Her üretilen çözüm bir tabloda (veri yapısında) saklanarak gerektiğinde tekrar tekrar kullanılmaktadır.
Bu yöntemi en iyi Fibonacci sayılarıyla anlatabiliriz. Fibonacci sayıları aşağıdaki formülle özetlenebilecek bir seriyi tanımlar;

F(n) = F(n-1) + F(n-2)

Yukarıdaki formülü pozitif bir sayıya uyguladığımız zaman Fibonacci sayısını elde edebiliriz. Aşağıda 10 için Fibonacci elde etme incelenebilir:

0 1 1 2 3 5 8 13 21 34

En temel şekliyle Fibonacci sayılarını özyinelemeli yöntemle çözebiliriz:

F(n)
if n<=1 return n else return F(n-1) + F(n-2)

Yukarıdaki özyinelemeli yöntem küçük sayılar için ne kadar başarılı olsa da mesela 5 sayısını hesaplamak için 5 seviyeli bir ağaç oluşmasına neden olmaktadır. Ayrıca mesela F(2) yukarıdaki algoritmada 3 kere tekrar tekrar hesaplanmaktadır. Benim dizüstü F(50)'yi hesaplayamamakta, işlemcinin ısınması sonucu kendisini kapatmaktadır (:)). Bu algoritmanın başarım değerinin çift üssel olduğu yapılan analiz sonucu bulunabilir (bu yazının konusu değil :D )
Bu algoritmayı dinamik programlama yöntemiyle daha etkin bir şekilde yazabiliriz. Tekrar tekrar hesaplamak yerine hesapladığımız değeri saklayarak çözüme ulaşabiliriz:

F(n)
F[0] = 0
F[1] = 1
for i=2 to n do
F[i] = F[i-1]+F[i-2]
return F[n]

Bu iki algoritmayı karşılaştırmak için çok basit bir Java örneği yaptım (Kodunu en aşağıda bulabilirsiniz). Bilgisayarın kapanması nedeniyle sadece 10-20-30 ve 40 için Fibonacci sayı hesaplama sürelerini karşılaştırdım. Bu değerler bile ikinci algoritmanın başarısını göstermek için yeterlidir (Soldaki parantez içindeki özyinelemelinin süresi, sağdaki DP süresi):

[10]55(0) 55(0)
[20]6765(2) 6765(0)
[30]832040(130) 832040(0)
[40]102334155(2595) 102334155(0)

Hatta çok büyük sayıları problem yaşamadan DP algoritması ile bulabilirsiniz.

Bağlantılar:
http://kodveus.blogspot.com/2006/05/fibonacci-saylar-ve-pivolka.html
http://www.topcoder.com/tc?module=Static&d1=tutorials&d2=dynProg
http://en.wikipedia.org/wiki/Dynamic_programming

Kitap Önerisi:
Introduction to the Design and Analysis of Algorithms

Bağlantılar:
Introduction to Dynamic Programming

Kaynak Kod: (Biçimlendirme Serkan'ın önerisi ile Java2Html çevirici ile yapıldı ;))


package tekrei;
/**
* Bu sinifin amaci Devingen Programlamayi (Dynamic Programming) orneklemektir.
*
* @author emre
*
*/
public class DevingenProgramlama {
public static void main(String[] args) {
for (int i = 1; i < 5; i++) {
System.out.print("[" + i * 10 + "]");
long baslangic = System.currentTimeMillis();
System.out.print(fibRec(i * 10));
System.out.print("(" + (System.currentTimeMillis() - baslangic)
+ ")");
baslangic = System.currentTimeMillis();
System.out.print(" " + fibDP(i * 10));
System.out.println("(" + (System.currentTimeMillis() - baslangic)
+ ")");
}
System.out.println("Fib(1000):" + fibDP(100));
}

/**
* * Fibonnaci Sayilari: * F(n) = F(n-1) + F(n-2) {n>=2 için} {Baslangic
* Degerleri: F(0) = 0 F(1) = 1}
*
* Ornek bir seri: 0 1 1 2 3 5 8 13 21 34 55 .......
*/

/**
* Ozyineli olarak fibonacci sayisini hesaplayan metod
*/
private static long fibRec(int sayi) {
if (sayi <= 1)
return sayi;
return fibRec(sayi - 1) + fibRec(sayi - 2);
}

/** * Devingen programlama yontemiyle fibonacci sayisini * hesaplayan metod */
private static long fibDP(int sayi) {
long[] deger = new long[sayi + 1];
deger[0] = 0;
deger[1] = 1;
for (int i = 2; i < sayi + 1; i++) {
deger[i] = deger[i - 1] + deger[i - 2];
}
return deger[sayi];
}
}