Yazan: Şadi Evren ŞEKER

Bir problem tahlil ve çözüm yöntemi olan dinamik programlama yapı olarak parçala fethet yöntemine benzer. Tek farkı problemi parçalara böldükten sonra aynı problemin tekrarı olan parçaları bir kerede çözüp her tekrar için ayrı bir çözüm yapmamasıdır.

Örneğin fibonacci serilerini ele alalım, Bu seriyi üreten örnek kod aşağıda verilmiştir:

int fibonacci(int n)
{
if (0 == n) {
return 0;
} else if (1 == n) {
return 1;
} else {
return fibonacci(n - 2) + fibonacci(n - 1);
}
}


Yukarıda verilen bu recursive (kendi kendini çağıran) koda bakıldığında ve kodun tahlili yapıldığında aşağıdaki fonksiyon iç içe çağırma ağacı (recursion tree ) fark edilir:

fibonacci(4)
   +------------------------------
   |                             |
fibonacci(2)                 fibonacci(3)
   +-----------------            +---------------
   |                |            |              |
fibonacci(0)   fibonacci(1)  fibonacci(1)  fibonacci(2)
                                                +-----------
                                                |          |
                                           fibonacci(0) fibonacci(1)

yani yukarıdaki örnekte, fibonacci(4) fonksiyonu için çağırma işlemleri sırasıyla gösterilmiştir. Dikkat edilirse fonksiyonlar açıldğında kendisinden önceki iki sayının toplamını bulmakta, bu işlemi yaparken de ortak elemanlar kullanmaktadır. Örneğin fibonacci(2) fonksiyonu ağacın iki farklı yerinde bulunmaktadır ve iki farklı kere içi hesaplanmıştır. İşte dinamik programlamada amaç bunu kaldırarak bir kerede çözüme ulaşmaktır.

Dinamik programlamada aşağıdaki adımlar takip edilebilir:
Verimli bir çözüm için problemin yapsınının çıkarılması
Kendini çağıran bir şekilde (Recursive) verimli çözüme değer atanması
Verimli çözümün değerini aşağıdan yukarı (bottom-up) olarak hesaplanması
Hesaplanan bu çözümle daha verimli bir çözüm varsa aranıp üretilmesi

(4. adım şayet tek çözüm varsa kullanılmaz)

Örnek problemler:
En uzun Ortak Küme (longest common subsequence, Lcs)

—————————

906 views