Ana içeriğe atla

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];
}
}

Yorumlar

Serkan Güneş dedi ki…
Selam Emre,

Kaynak kodlarını daha okunabilir hale getirmek istersen, aşağıdaki sitedeki aracı kullanabilirsin. Yapman gereken sadece kaynak kodunu bu aracın giriş bölümüne yapıştırmakç Daha sonra araç otomatik olarak java kodunu eclipse tabanlı bir html dokümanı haline getirecektir.

Aracın adresi:
http://www.java2html.de/

Serkan Güneş
Tahir Emre KALAYCI dedi ki…
Çok sağol Serkan, böyle bir aracın eksikliğini ciddi anlamda hissediyordum. En az 15 dakika nasıl güzel gösterebilirim şeklinde kasıyordum her yazıda :)
mehmet dedi ki…
Merhaba ben big. müh. de okuyorum.hocamız rekursive fonksiyonlar konusunda hanoi kulelerini ödev olarak verdi.Hanoi kulelerinin çözülmesi satrançtaki gibi hamleler teker teker sınanarak mı belirenir?kafama takıldı bir türlü ilerleyemiyorum yardımcı olursanız sevinirim.
Tahir Emre KALAYCI dedi ki…
Merhaba,

Özyineli olarak Hanoi kulelerinin çözümüyle ilgili olarak kaynağını önerebilirim.
Adsız dedi ki…
dinamik olarak yapılan fibonacci serisinde bir sorun yok mu
deger[0]=1 olması gerekmez mi?
T. E. Kalaycı dedi ki…
Fibonnaci serisinde 0. sayı 0'a eşittir. Bkz. http://tr.wikipedia.org/wiki/Fibonacci_dizisi
Tolpp dedi ki…
Buradan dinamik programlama hakkında bilgiye ve Rod-Cutting probleminin dinamik programlama ile çözümüne ulaşabilirsiniz.